scientific article; zbMATH DE number 3569855
From MaRDI portal
Publication:4140407
zbMath0365.68072MaRDI QIDQ4140407
Arto Salomaa, Grzegorz Rozenberg
Publication date: 1976
Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Related Items
Recurrent words and simultaneous growth in T0L systems, On coordinated selective substitutions: Towards a unified theory of grammars and machines, Pattern selector grammars and several parsing algorithms in the context- free style, Applications of scheduling theory to formal language theory, On erasing in E0L forms, Context dependent table matrix L systems, Concerning two-adjacent context-free languages, String grammars with disconnecting or a basic root of the difficulty in graph grammar parsing, A powerful abelian square-free substitution over 4 letters, The equivalence of finite valued transducers (on HDT0L languages) is decidable, Periodic D0L languages, Balance of many-valued transductions and equivalence problems, Remarks on arbitrary multiple pattern interpretations, Bounded D0L languages, On a public-key cryptosystem based on iterated morphisms and substitutions, The Dyck language \(D_ 1^{'*}\) is not generated by any matrix grammar of finite index, C-tree systolic automata, On the length of word chains, Sur l'ensemble normal des substitutions de longueur quelconque. (On the normal set of substitutions of arbitrary length), The finiteness of synchronous, tabled picture languages is decidable, A defect property of codes with unbounded delays, A representation of recursively enumerable languages by two homomorphisms and a quotient, A cryptanalytic observation concerning systems based on language theory, On the subword complexity of m-free DOL languages, Bounds for the D0L language equivalence problem, On some decidability problems for HDOL systems with nonsingular Parikh matrices, On commutative DTOL systems, Observations concerning a public-key cryptosystem based on iterated morphisms, On the degree of synchronization of k1TOL and k1ETOL systems, The generating function of the number of subpatterns of a DOL sequence, Many-to-one simulation in EOL forms is decidable, Persistent ETOL systems, Mots sans carre et morphismes iterés, Synchronized and desynchronized EOL forms, Towards bridging two cell-inspired models: P systems and R systems, Test sets and checking words for homomorphism equivalence, On ambiguity in EOL systems, A \(P\) system model with pure context-free rules for picture array generation, Sur les séries associees à certains systèmes de Lindenmayer, Marked D0L systems and the \(2n\)-conjecture, On the emptiness of the intersection of two DOS languages problem, On pure, terminal invariant and nonterminal invariant interpretations of EOL forms, Periodic string division generated by deterministic L systems, Bispecial factors in circular non-pushy D0L languages, New techniques for proving the decidability of equivalence problem, A model for developmental systems. I: Generating word without any operating system, An algorithm for enumerating all infinite repetitions in a D0L-system, On almost cylindrical languages and the decidability of the D0L and PWD0L primitivity problems, Structural equivalence and ET0L grammars, Quasi-deterministic 0L systems and their representation, Pattern systems, Multi-pattern languages, Completeness results concerning systolic tree automata and E0L languages, A decision method for Parikh slenderness of context-free languages, Comparison of some descriptional complexities of 0L systems obtained by a unifying approach, On equality between fuzzy context-free and fuzzy adult 0L languages, Equations over finite sets of words and equivalence problems in automata theory, On the union of 0L languages, The minimum substring cover problem, Pure 2D picture grammars and languages, Decidability of operation problems for T0L languages and subclasses, Descriptional and computational complexity of finite automata -- a survey, The generative capacity of block-synchronized context-free grammars, The bounded degree problem for NLC grammars is decidable, Basic tree transducers, Regularity of sets of initial strings of periodic D0L-systems, The goodness of \(\{S,a\}\)-EOL forms is decidable, Hierarchical resolution of power spectra, A new pumping lemma for indexed languages, with an application to infinite words, The effective entropies of some extensions of context-free languages, The class of HDT0L sequences is closed with respect to rational functions, Systems of equations over a free monoid and Ehrenfeucht's conjecture, L codes and number systems, Studies in uniformity, On simulation and propagating EOL forms, Stability of desynchronized 0L-systems, Homomorphic images of sentential form languages defined by semi-Thue systems, Synchronized EOL forms, On binary equality sets and a solution to the test set conjecture in the binary case, On subword complexity functions, On inherently ambiguous E0L languages, The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids, On the subword complexity of DOL languages with a constant distribution, Code properties and homomorphisms of DOL systems, Hierarchies of hyper-AFLs, An inverse homomorphic characterization of full principal AFL, On k-repetition freeness of length uniform morphisms over a binary alphabet, On a family of L languages resulting from systolic tree automata, Inverse morphic equivalence on languages, On test sets for checking morphism equivalence on languages with fair distribution of letters, Fair derivations in E0L systems, Extended macro grammars and stack controlled machines, Periodicity and ultimate periodicity of D0L systems, Decidability of structural equivalence of E0L grammars, On standard locally catenative L schemes, Test sets for morphisms with bounded delay, The undecidability of form equivalence for context-free and EOL forms, On the power of synchronization in parallel computations, On the equivalence problem of compositions of morphisms and inverse morphisms on context-free languages, Adherences of DOL languages, The equivalence problem for DF0L languages and power series., Some analytic features of algebraic data, Automatic graphs and D0L-sequences of finite graphs, A Kleene-like characterization of languages accepted by systolic tree automata, Formal languages defined by uniform substitutions, On the power of membrane division in P systems, A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\), Languages of colonies, On generalized DT0L systems and their fixed points, On developmental systems: Multilevel and parallel development, Equality sets of binary D0L sequences, Slender 0L languages, On the Kleijn-Rozenberg k-adjacent languages, Dynamical systems arising from random substitutions, Inflation word entropy for semi-compatible random substitutions, On the splicing operation, Discrete Watson-Crick dynamical systems, On Lindenmayerian algebraic power series, On Lindenmayerian algebraic sequences, Simple splicing systems, The Euclidean traveling salesman problem and a space-filling curve, Functions and sequences generated by reaction systems, Watson-Crick D0L systems: The power of one transition, On three variants of rewriting P systems, Languages, D0L-systems, sets of curves, and surface automorphisms., Power and size of extended Watson-Crick \(L\) systems., On images of D0L and DT0L power series., Tissue P systems., Decidability results for Watson-Crick D0L systems with nonregular triggers., Sturmian images of non Sturmian words and standard morphisms, Context-free like restrictions on selective rewriting, Recursion and pumping in L forms, Endomorphic presentations of branch groups., The inclusion of D0L in multi-reset, On the subword complexity of square-free DOL languages, Decidability and density in two-symbol grammar forms, A three-restricted normal form theorem for ETOL languages, On form-equivalence of deterministic pure grammar forms, Table systems with unconditional transfer, A note on the similarity depth, Subword balance, position indices and power sums, Basic formulas and languages. I: The theory, Basic formulas and languages. II: Applications to EOL systems and forms, The decidability of the DOL-DTOL equivalence problem, On infinite words obtained by iterating morphisms, Finite DOL languages and codes, Watson-Crick D0L systems: Generative power and undecidable problems., Forbidding ET0L grammars., On the subword complexity of locally catenative DOL languages, Systolic trees and systolic language recognition by tree automata, DOL schemes and the periodicity of string embeddings, The string generating power of context-free hypergraph grammars, Machine characterization of (E0L-E0L) array languages, Defining families of trees with E0L grammars, Iterated stack automata and complexity classes, On the rank of the subsets of a free monoid, Relationships between bounded languages, counter machines, finite-index grammars, ambiguity, and commutative regularity, Simple reductions between \(D0L\) language and sequence equivalence problems, The language equivalence problem for HD0L systems having D0L growths, Explicit test sets for iterated morphisms in free monoids and metabelian groups, The behavioral properties of homogeneous structures, On the decidability of the sequence equivalence problem for DOL-systems, New squeezing mechanisms for L systems, On complements of unary L languages, A note on DOL length sets, EOL languages are not codings of FPOL languages, A note on language equations involving morphisms, On the structure of derivations in deterministic ETOL systems, A note on asynchronous cellular automata, On finite-index indexed grammars and their restrictions, The decidability of the FOL-DOL equivalence problem, Dynamically controlled cooperating/distributed grammar systems, Elementary homomorphisms and a solution of the DOL sequence equivalence problem, The undecidability of some equivalence problems concerning ngsm's and finite substitutions, Team behaviour in eco-grammar systems, Characterizations of recursively enumerable languages by means of insertion grammars, Normal form of extended table matrix L systems, Manipulating derivation forests by scheduling techniques, Morphismes unispectraux. (Unispectral morphisms), On a possible classification of real-time constructed sequences, Coupled map lattices dynamics on a variable space for the study of development: A general discussion on Caenorhabditis elegans, Repetitiveness of languages generated by morphisms, On D0L power series, On cube-free \(\omega\)-words generated by binary morphisms, Context free normal systems and ETOL systems, Dominoes over a free monoid, Variable-length codes independent or closed with respect to edit relations, Computing with membranes, Grouped partial ET0L systems and parallel multiple context-free grammars, An inequality for non-negative matrices, Decidability results concerning \(k\)-limited ED0L systems, Language-theoretic aspects of DNA complementarity, Topics in the theory of DNA computing., A guide to membrane computing., Universal computation with Watson-Crick D0L systems., On D0L systems with immigration, Some methods for generating infinite sequences, An algebraic characterization of the set of succession rules, Uni-transitional Watson-Crick D0L systems, Decidability of EDT0L structural equivalence, Active symbols in grammars with valuations, A note on emptiness for alternating finite automata with a one-letter alphabet, Unnamed Item, The monadic second-order logic of graphs. I: Recognizable sets of finite graphs, The equality problem for infinite words generated by primitive morphisms, Unnamed Item, Deletion operations on deterministic families of automata, A characterization of free pairs of upper triangular free monoid morphisms, Numerical networks of cells, MULTIPLICATION TABLES AND WORD-HYPERBOLICITY IN FREE PRODUCTS OF SEMIGROUPS, MONOIDS AND GROUPS, Chomsky-Schützenberger Type Characterizations of Poly-Slender and Parikh Slender Context-Free Languages1 1Work supported by the Grants-in Aid for Scientific Research No. 1 0440034, Japan Society for the Promotion of Sciences and the Dirección General de Enseñanza Superior e Investigación Cientifica, SB 97-00110508, EDT0L solutions to equations in group extensions, Languages generated by numerical P systems with thresholds, Using \textsc{edt0l} systems to solve some equations in the solvable Baumslag-Solitar groups, On elimination of erasing rules from E0S grammars, Flip-pushdown automata with \(k\) pushdown reversals and E0L systems are incomparable, An infinite hierarchy induced by depth synchronization, Cancellation and periodicity properties of iterated morphisms, A Note on Parallel Splicing on Images, Parallel communicating limited and uniformly limited 0L systems, Substitutions and interval exchange transformations of rotation class, On Parikh slender context-free languages, Watson-Crick D0L systems with regular triggers, Logical string rewriting, Fuzzy \(L\) languages, On the synchronized derivation depth of context-free grammars, Two collapsing hierarchies of subregularly tree controlled languages, Characterization of circular D0L-systems, Easy cases of the D0L sequence equivalence problem, Non acceptability criteria and closure properties for the class of languages accepted by binary systolic tree automata, On infinite words generated by polynomial D0L systems, Operations and language generating devices suggested by the genome evolution, Towards a proof of the decidability of the momentary stagnation of the growth function of D0L systems, On the equivalence problem for succession rules, An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet, On infinite words determined by L systems
