43629107
On the Separating Power of Eol Systems
39400225
On Subword Complexities of Homomorphic Images of Languages
— The subword complexity of a language K is the function nK on positive integer s such that nK (n) equals the number of different subwords of length n appearing in words of X. We investigate the relationship between nk(K) and nK where Kis a language and h is a homorphism. This study is aiso carried out for the special case when Kis a DOL language. Resumé. — La complexité des facteurs d'un langage K est la fonction nK définie sur les entiers positifs telle que nK (n) est le nombre de facteurs distincts de longueur n apparaissant dans les mots de K. Nous étudions les relations existant entre KH(K) et nKi où K est un langage et h est un homomorphisme. Cette étude est menée également dans le cas particulier où Kest un DOL langage.
43370814
Boundary NLC Graph Grammars-Basic Definitions, Normal Forms, and Complexity
Node label controlled (NLC) grammars are graph grammars (operating on node labeled undirected graphs) which rewrite single nodes only and establish connections between the embedded graph and the neighbors of the rewritten node on the basis of the labels of the involved nodes only. They define (possibly infinite) languages of undirected node labeled graphs (or, if we just omit the labels, languages of unlabeled graphs). Here we consider a restriction of NLC grammars, so-called boundary NLC (BNLC) grammars , distinguished by the property that whenever in a graph already generated two nodes may be rewritten, then these nodes are not adjacent. The graph languages generated by this type of grammars are called BNLC languages . Although we show that this restriction leads to a smaller class of languages, still enough generative power remains to define interesting graph languages. For example, trees, complete bipartite graphs, maximal outerplanar graphs, k -trees, graphs of bandwidth ⩽ k , graphs of cyclic bandwidth ⩽ k , graphs of binary tree bandwidth ⩽ k , graphs of cutwidth ⩽ k (always for a fixed positive integer k ) turn out all to be BNLC languages. We prove a number of normal forms for BNLC grammars and then we indicate their usefulness by various applications. In particular, we show that for connected graphs of bounded degree the membership problem for BNLC languages is solvable in deterministic polynomial time.
1753130
Conditions Enforcing Regularity of Context-Free Languages
39682467
On the Active and Full Use of Memory in Right-Boundary Grammars and Push-Down Automata
Abstract A coordinated pair system ( cp system for short) consists of a pair of grammars, the first of which is right-linear ( rl ) and the second is right-boundary ( rb ). A right-boundary grammar is like a right-linear grammar except that one does not distinguish between terminal and nonterminal symbols—still, the rewriting is applied to the last symbol of a string only (and erasing productions are allowed). A rewriting in a cp system consists of a pair of rewritings: one in the first and one in the second grammar—such a rewriting is possible if the pair of productions involved is in the finite set of rewrites given with the system. Is is easily seen that cp systems correspond very closely to (are another formulation of) push-down automata: the right-linear component models the input and the finite state control while the rb component models the push-down store. An rb grammar G transforms (rewrites) strings which are stored in a one-way (potentially infinite) tape. If one observes during a derivation δ the use of a fixed n th cell of the tape and one notes the symbol stored there, each time that (the contents of) the cell is rewritten, then one gets the n-active record of δ; the set of all n -active records for all successful derivations δ forms the n -active language of G , denoted ACT n ( G ). It is proved that, for each rb grammar G and each n ϵ N + , ACT n ( G ) is regular and moreover, for each M ⊆ N + , ∪ nϵM ACT n ( G ) is regular. Another way to register the use of memory during a derivation δ is to record the contents of (a fixed) n th cell during all consecutive steps of δ—in this way one gets the n-full record of δ. The set of all n -full records for all successful derivations δ forms the n -full record language of G , denoted FR n ( G ). It is proved that, as in the case of active records, ∪ nϵM FR n ( G ) does not have to be regular even if M = N + (actually, one can get arbitrarily complex languages in this way). Then we provide a representation theorem allowing one to represent a cp system by an rb grammar and using this theorem we transfer the above results on the use of memory to cp systems.
2026601
Elementary Net Systems
13303483
Theory of Traces
Abstract The theory of traces , originated by A. Mazurkiewicz in 1977, is an attempt to provide a mathematical description of the behavior of concurrent systems. Its aim is to reconcile the sequential nature of observations of the system behavior on the one hand and the nonsequential nature of causality between the actions of the system on the other hand. One can see the theory of traces to be rooted in formal string language theory with the notion of partial commutativity playing the central role. Alternatively one can see the theory of traces to be rooted in the theory of labeled acyclic directed graphs (or even in the theory of labeled partial orders). This paper attempts to present a major portion of the theory of traces in a unified way. However, it is not a survey in the sense that a number of new notions are introduced and a number of new results are proved. Although traditionally most of the development in the theory of traces follows the string-language-theoretic line, we try to demonstrate to the reader that the graph-theoretic point of view may be more appropriate. The paper essentially consists of two parts. The first one (Sections 1 through 4) is concerned with the basic theory of traces. The second one (Section 5) presents applications of the theory of traces to the theory of the behavior of concurrent systems, where the basic system model we have chosen is the condition/event system introduced by C.A. Petri.
28657554
Hypergraph Systems and Their Extensions
The notion of a graph is a natural generalization of the notion of a string. Using one graph (the transition graph ofafinite automaton) one can define a language {the language of a given automaton). This well-known idea is generalized as follows: the notion of a hypergraph is a natural generalization of the notion of a graph. Using one hypergraph (equipped with an additional graph structure) one can define a graph language (a set ofgraphs). Several variants of graph grammars based on this idea are introduced in this paper together withformalism needed to investigate them and illustrating examples. The generating power of various graph-language-generating Systems is compared. Résumé. — La notion de graphe est une généralisation naturelle de la notion de mot. En utilisant un graphe {le graphe de transition d'un automate fini) on définit un langage {le langage accepté par l'automate). Cette idée est généralisée comme suit ; la notion de hypergraphe est une généralisation naturelle de la notion de graphe. Avec un hypergraphe (muni d'une structure de graphe supplémentaire) on peut définir un langage (un ensemble) de graphes. Dans cet article on introduit diverses variantes des grammaires de graphes basées sur cette idée; on donne le formalisme nécessaire pour les étudier, et on les illustre par des exemples. La puissance générative de divers systèmes engendrant des langages de graphes est comparée.
6414809
Developmental systems and languages
Developmental systems were introduced (Lindenmayer, 1968, 1971) in order to model morphogenetic (pattern-generating) processes in growing, multicellular, filamentous organisms. These systems were originally conceived as linear arrays of interconnected finite automata, each automaton corresponding to a living cell, with the possibility that new automata can be added to the array (cells divide) or be deleted from the array (cells die).
 Each cell in the array is supposed to have the same state-transition and output functions. As required by biological considerations these functions must be applied to all cells in the array simultaneously at each time step. Thus one obtains infinite sequences of arrays once the functions and the initial arrays are specified. Simplified constructs are defined (and used in this paper) by considering the states and outputs to be identical and thus omitting the output functions. Such filamentous developmental systems have been called “Lindenmayer models” Herman, 1969, 1970) or “L-systems” (Van Dalen, 1971).
34528489
Reductions for Primitive 2-Structures
A subset X of a 2-structure (a reversible edge-colored directed graph) g is a clan, if X cannot be distinguished by colors from outside of X. We show that if g is primitive, i.e. it has no nontrivial clans, then there exists an edge e or an end vertex x such that when e or x is removed from g, the resulting 2-structure g′ remains primitive. We also present a composition result for the unstable 2-structures, which are those primitive 2-structures where a removal of any edge results in a nonprimitive 2-structure.
9443958
Dynamic change within workflow systems
Dynamic change is a large and pervasive unsolved problem which surfaces within office systems as well as within software engineering, manufacturing, and numerous other domains. Procedural changes, performed in an ad hoc manner, can cause inefficiencies, inconsistencies, and catastrophic breakdowns within offices. This paper is concerned with dynamic change to procedures in the context of workflow systems. How can we make workflow systems more flexible and open? We believe that part of the answer lies in the study and solution of the dynamic change problem. In this paper, we use a Petri net formalism to analyze structural change within office procedures. As an example, we define a class of change called “synthetic cut-over change”, and apply our formalism to prove that this class maintains correctness when downsizing occurs.