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.
34951842
Primitivity is Hereditary for 2-Structures
Abstract It is proved that each primitive 2-structure on n elements ( n ⩾3) contains a primitive substructure on either ( n −1) or ( n −2) elements.
37770747
Transitivity of local complementation and switching on graphs
Abstract The operations complementation C , local complementation λ x , and switching σ x for the vertices x of a finite undirected graph are considered. The operation λ x complements the subgraph induced by the neighbourhood of x in the given graph, and the switching σ x changes the neighbourhood of x to its complement vertex set. It is proved that the compositions δ x = λ x C (for vertices x ∈ D ) generate a transitive group on the graphs with vertex set D , that is, for any two graphs g and h on D , there exists a composition α of operations δ x such that h = α ( g ). It is also shown that the compositions τ x = λ x σ x (for x ∈ D ) generate a transitive group on the graphs.
12269815
Angular 2-Structures
The theory of 2-structures forms a convenient framework for investigating graphs. In this paper we investigate the class of angular 2-structures which results by requiring that the primitivity is forbidden on the lowest possible level, i.e. it is required that no substructure on three elements is primitive. The paper presents the basic theory of angular 2-structures and, in particular, the theory of primitive angular 2-structures. We demonstrate that the notion of an angular 2-structure is a well-chosen generalization of the notions of a symmetric graph and a partial order.
39431424
Incremental construction of 2-structures
Abstract A labeled 2-structure g is an edge-labeled directed graph with a reversibility condition on the labels. Each labeled 2-structure g can be represented as a tree, the prime tree of g. We characterize a labeled 2-structure h in terms of the prime tree of a labeled 2-structure g which results from h by removing one element from h. This leads to an O(n3) algorithm for the construction of the prime tree.
40876494
Theory of 2-Structures
The process according to the present invention relates to the production of ferrovanadium alloys. The process comprises melting a charge containing iron and vanadium with a subsequent reduction of iron and vanadium to give a metal melt. In accordance with the present invention, iron and vanadium are reduced substantially completely. The resulting metal melt is poured into a converter and then purged, through the converter bottom, by means of oxygen blowing at a supply rate of oxygen and for a period of time sufficient to produce a slag containing at least 35% by weight of vanadium pentoxide. Thereafter, the metal melt is discharged from the converter, while vanadium and iron are reduced from the resulting slag by the metallothermal method.
37152120
Transition Systems, Event Structures and Unfoldings
A subclass of transition systems called elementary transition systems can be identified with the help of axioms based on a structural notion called regions. Elementary transition systems have been shown to be the transition system model of a basic system model of net theory called elementary net systems. Here we show that by smoothly strengthening the regional axioms for elementary transition systems, one obtains a subclass called occurrence transition system. We then prove that occurrence transition systems are the transition system model of yet another basic model of concurrency, namely, prime event structures. We then propose an operation of unfolding elementary transition systems into occurrence transition systems, We prove that it is "correct" in a strong categorical sense.
44960163
Restrictions on NLC Graph Grammars
Several models of ‘graph grammars’ have been studied with the objective of generating graphs from graphs using a finite set of derivation rules. In this way, possibly infinite sets of graphs (called graph languages) can be finitely defined. One aspect that must be addressed in any such model is the ‘embedding problem’, that is: When a production is applied, how does the new subgraph get reconnected to the original graph? Node-label controlled (NLC) grammars solve this problem in an elegant way that depends only on the labels of nodes in the new and original graphs. This paper examines certain restrictions on NLC grammars similar to the Chomsky or Greibach normal forms for context-free string grammars. For example, one restriction we consider requires each production to produce a terminal labeled node—similar to Greibach normal form. We also consider restrictions on the form which the embedding mechanism can take. Our result is that each of the restrictions we examine causes a reduction in generating power for the grammars. Finally, we discuss some directions for future research on NLC grammars.
36510403
On Coordinated Selective Substitutions: Towards a Unified Theory of Grammars and Machines
Abstract The notion of a coordinated table selective substitution system (a cts system ) is introduced. It provides a unifying framework for both grammars and machines (automata) and hence a really broad framework for formal language theory. An extensive number of examples is given which illustrate how a quite considerable number of grammars and automata considered in the literature may be ‘naturally’ interpreted as special instances (subclasses of the class) of cts systems.
5113046
FPOL Systems Generating Counting Languages
— Counting languages are the languages of the form {axa\.. .a n t\ t^2, n^ 1} where au ..., atare letters no two consécutive ofwhich are identical. They possess a "clean structure" in the sensé that if an arbitrary wordfrom such a language is eut in t subwords ofequal length then no two consécutive subwords contain an occurrence of the same letter, It is shown that whenever an FPOL system G is such that Us language contains a "dense enough" subset of a counting language then the whole language ofG cannot have such a clean structure. Résumé. — Les langages « comptants » sont les langages de la forme { a" a\. . . a" \t ^ 2, n ̂ 1} , où au ..., at sont des lettres, et deux lettres consécutives étant différentes. Ils possèdent une « bonne structure », en ce sens que si un mot quelconque d'un tel langage est divisé en t facteurs de même longueur, alors deux facteurs consécutifs ne contiennent pas d'occurrence d'une même lettre. On montre que, si un System FPOL G est tel que son langage contient un sous-ensemble d'un langage comptant qui est « assez dense » alors le langage de G complet ne peut pas avoir cette « bonne structure ».
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.