A language measure for supervisory control

This paper formulates a signed real measure for sublanguages of regular languages based on the principles of automata theory and real analysis. The measure provides total ordering on the controlled behavior of a finite-state automaton plant under different supervisors. Total variation of the measure serves as a metric for the infinite-dimensional vector space of the sublanguages of a regular language over the finite field GF(2). The computational complexity of the language measure is of polynomial order in the number of plant states.     

A Language for Teaching Discrete-event Simulation

Courses which teach discrete-event simulation are based on many different simulation languages. The requirements for a language to support teaching simulation are discussed. In particular, it is recommended that such languages separate into distinct modules those aspects of simulation which are taught as separate topics. Implementation of the separation is discussed. The SEESIM language, developed as a teaching aid, is described, and examples of its use are given. Straightforward use of SEESIM can be learned quickly, yet the language provides facilities for a staged introduction to advanced concepts of simulation.     

Regular Component Splittable Languages

Every infinite regular language contains a regular subset of the formuv+w for some words u, v, w, where v is not the empty word. The regularsubsets of the above form are called regular components. Some well-knowncontext-free languages, such as the Dyck language and the balanced language(over an alphabet X with |X| = 2), are decomposed as disjointunions of disjunctive languages. In this paper, we investigate thedecompositions of some of the regular languages and the context-freelanguages as disjoint unions of regular components. An infinite language iscalled regular component splittable if it can be expressed as a disjointunion of regular components and a finite set. We show that the Dycklanguage, the balanced language and some disjunctive context-free splittablelanguages are regular component splittable. We also present an example toshow that there is a disjunctive context-free language which is not regularcomponent splittable.     

Infinitesimal Perturbation Analysis: A Tool for Simulation

Perturbation analysis is a technique that expedites the process of performing experiments on discrete-event simulation models. This makes it possible to derive sensitivity estimates from one computer execution of a simulation model. Infinitesimal perturbation analysis (IPA) is one class of algorithms used in perturbation analysis. In this paper, the techniques and algorithms used in simulation to perform infinitesimal perturbation analysis are examined. Each algorithm is discussed in detail, with comments concerning implementation problems and examples with experimental results for serial transfer lines. The results of this paper show that for simple systems, IPA can be easily implemented in a general-purpose simulation language such as SIMAN. Unfortunately, for any given system, parameter or performance measure, the algorithm used to generate the gradient may vary. Additionally, algorithms for more complex classes of problems do not yet exist. This problem hampers the current possibility of incorporating IPA into general-purpose simulation languages.     

关于Fuzzy正则语言的一些性质

在定义Fuzzy正则语言,Fuzzy有理语言等的基础上,研究Fuzzy正则语言相关的一些性质,得到Fuzzy正则语言与Fuzzy有理语言间的对应关系,对Fuzzy有限状态自动机的简化具有应用价值。     

Control extension in a recursive language

Techniques for language extension are of interest today as a means for language design experimentation without language proliferation. Attention thus far has been focused on methods for data structure definition and manipulation. The problem of program control extensibility has been recognized by workers in the field but less thoroughly treated. This paper outlines an approach to control extensibility applicable on the source language level to appropriate programming languages.Using the recursive language LISP as an example, extensions are defined that provide call by name function parameters, generator functions (as in IPL-V), non-deterministic functions, and general coroutines. LISP facilitates this exercise by features including dynamic scope of variables, source programs manipulatable as data, simplicity of program state representations, and control over context of function evaluation. The results of this paper suggest criteria for evaluating base languages in extensible programming systems, as well as a possible insight into formal program analysis.     

A cryptanalytic observation concerning systems based on language theory

This note discusses a cryptanalytic method applicable to some public-key cryptosystems based on the theory of formal languages. Essentially, the method uses the fact that the image of a regular language under an inverse finite substitution is accepted by a finite automation of the same size as the automaton accepting the original regular language. In particular, systems based on iterated morphisms and repeated finite substitutions, [2,3], will be discussed.     

Finite turns and the regular closure of linear context-free languages

Turn bounded pushdown automata with different conditions for beginning a new turn are investigated. Their relationships with closures of the linear context-free languages under regular operations are studied. For example, automata with an unbounded number of turns that have to empty their pushdown store up to the initial symbol in order to start a new turn are characterized by the regular closure of the linear languages. Automata that additionally have to re-enter the initial state are (almost) characterized by the Kleene star closure of the linear languages. For both a bounded and an unbounded number of turns, requiring to empty the pushdown store is a strictly stronger condition than requiring to re-enter the initial state. Several new language families are obtained which form a double-stranded hierarchy. Closure properties of these families under AFL operations are derived. The regular closure of the linear languages share the strong closure properties of the context-free languages, i.e., the family is a full AFL. Interestingly, three natural new language families are not closed under intersection with regular languages and inverse homomorphism. Finally, an algorithm is presented parsing languages from the new families in quadratic time.     

On a bi-dimensional dynamic alternative routing method

The analysis of a bi-dimensional dynamic routing model for alternative routing telecommunication networks led to the identification of an instability problem in the synchronous path selection associated with the complex interdependencies among the coefficients of the objective functions and the computed paths for every node pair. In this paper an analytical model enabling to make explicit this problem and evaluate its effects in terms of two global network criteria, is presented. Also a heuristic procedure dedicated to overcome this instability problem and select “good” compromise solutions in terms of network performance is developed. Finally the performance of the proposed routing method using the heuristic is compared by recurring to discrete-event simulation with a reference dynamic routing method (Real Time Network Routing) for some test networks.     

Language-theoretic complexity of disjunctive sequences

A sequence over an alphabet ∑ is called disjunctive if it contains all possible finite strings over ∑ as its substrings. Disjunctive sequences have been recently studied in various contexts. They abound in both category and measure senses. In this paper we measure the complexity of a sequence x by the complexity of the language P(x) consisting of all prefixes of x. The languages P(x) associated to disjunctive sequences can be arbitrarily complex. We show that for some disjunctive numbers x the language P(x) is context-sensitive, but no language P(x) associated to a disjunctive number can be context-free. We also show that computing a disjunctive number x by rationals corresponding to an infinite subset of P(x) does not decrease the complexity of the procedure, i.e. if x is disjunctive, then P(x) does not have an infinite context-free subset. This result reinforces, in a way, Chaitin's thesis (1969) according to which perfect sets, i.e. sets for which there is no way to compute infinitely many of its members essentially better (simpler/quicker) than computing the whole set, do exist. Finally we prove the existence of the following language-theoretic complexity gap: There is no x ε ∑^w such that P(x) is context-free but not regular. If S(x), the set of all finite substrings of a sequence x ε ∑^w, is slender, then the set of all prefixes of x is regular, that is P(x) is regular if and only if S(x) is slender.     

Usability aware secret protection with minimum cost

In this paper we study a cybersecurity problem of protecting system’s secrets with multiple protections and a required security level, while minimizing the associated cost due to implementation/maintenance of these protections as well as the affected system usability. The target system is modeled as a discrete-event system (DES) in which there are a subset of marker states denoting the services/functions provided to regular users, a subset of secret states, and multiple subsets of protectable events with different security levels. We first introduce usability-aware cost levels for the protectable events, and then formulate the security problem as to ensure that every system trajectory that reaches a secret state contains a specified number of protectable events with at least a certain security level, and the highest usability-aware cost level of these events is minimum. We first provide a necessary and sufficient condition under which this security problem is solvable, and when this condition holds we propose an algorithm to solve the problem based on the supervisory control theory of DES. Moreover, we extend the problem to the case of heterogeneous secrets with different levels of importance, and develop an algorithm to solve this extended problem. Finally, we demonstrate the effectiveness of our solutions with a network security example.     

Supervisory Control of Extended Timed Event Graphs

This paper describes the dynamic behavior of extended timed event graphs related to place delay in the dioid framework. By Cofer and Garg‘s supervisory control theory, we address control problems of extended timed event graphs. Supervisory control of extended timed event graphs (a class of discrete event dynamic systems) is studied in the dioid framework, a necessary and sufficient condition for the ideals of the set of firing time sequences of transitions to be controllable is presented. We prove all the strongly controllable subsets can form a complete lattice,     

146号初等元胞自动机的演化语言的复杂性

Symbolic dynamics of cellular automata is introduced by coarse-graining the temporal evolution orbits. Evolution languages are defined. By using the theory of formal languages and automata, the complexity of evolution languages of the elementary cellular automaton of rule 146 is studied and it is proved that its width 1-evolution language is regular, but for every n ≥ 2 its width n-evolution language is not context-free but context-sensitive. Also, the same results hold for the equivalent （under conjugation） elementary cellular automaton of rule 182.     

Linear splicing and syntactic monoid

Splicing systems were introduced by Head in 1987 as a formal counterpart of a biological mechanism of DNA recombination under the action of restriction and ligase enzymes. Despite the intensive studies on linear splicing systems, some elementary questions about their computational power are still open. In particular, in this paper we face the problem of characterizing the proper subclass of regular languages which are generated by finite (Paun) linear splicing systems. We introduce here the class of marker languages L, i.e., regular languages with the form L=L₁[x]₁L₂, where L₁,L₂ are regular languages, [x] is a syntactic congruence class satisfying special conditions and [x]₁ is either equal to [x] or equal to [x]∪{1}, 1 being the empty word. Using classical properties of formal language theory, we give an algorithm which allows us to decide whether a regular language is a marker language. Furthermore, for each marker language L we exhibit a finite Paun linear splicing system and we prove that this system generates L.     

Recognizing splicing languages: Syntactic monoids and simultaneous pumping

We use syntactic monoid methods, together with an enhanced pumping lemma, to investigate the structure of splicing languages. We obtain an algorithm for deciding whether a regular language is a reflexive splicing language, but the general question remains open.     

Preface

The following morphic characterization of EOL languages is established. The family of EOL languages equals the family of all languages of the form h(L∩R) where h is a morphism, R is a regular language and L is the maximal solution of an equation $\text{?(X) = g(X)}$, where ? is a morphism, g is a coding and X is a language variable. It is shown that if g is allowed to be a weak coding, then a larger family of languages is obtained, which however is strictly contained in the family of ETOL languages.     

Restorations of punctured languages and similarity of languages

Punctured languages are languages whose words are partial words in the sense that the letters at some positions are unknown. We investigate to which extent restoration of punctured languages is possible if the number of unknown positions or the proportion of unknown positions per word, respectively, is bounded, and we study their relationships for different boundings. The considered restoration classes coincide with similarity classes according to some kind of similarity for languages. Thus all results we can also formulate in the language of similarity. We show some hierarchies of similarity classes for each class from the Chomsky hierarchy and prove the existence of linear languages which are not δ ‐similar to any regular language for any δ < ½. For δ ≥ ½ this is unknown but it could only be possible in the case of non‐slender linear languages. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Design of a small conversational system

The main features of a time-sharing system for a minicomputer are outlined. An interpretive language LAX plays a central role in the system both as a base for the languages seen by the user and for implementing part of the system. The system is open-ended, new subsystems can be plugged in easily, and a variety of error and interrupt behavior can be obtained.