scientific article

Publication date: 1981

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

decidability context-free languages regular languages morphisms codes recursively enumerable language equality sets coloring of graphs DOL-systems elementary morphisms grammatical families language families families of graphs morphic representations DOL equivalence problem finite power property restriction of the star height sentential forms of context-free languages Thue's problem

Mathematics Subject Classification ID

Introductory exposition (textbooks, tutorial papers, etc.) pertaining to computer science (68-01) Formal languages and automata (68Q45) Research exposition (monographs, survey articles) pertaining to computer science (68-02)

Related Items

Repetition-free words, Truncations of infinite matrices and algebraic series associated with some CF grammars, A property of three-element codes, On morphic generation of regular languages, On syntactic nuclei of rational languages, A powerful abelian square-free substitution over 4 letters, Square-free words with one possible mismatch, Morphic congruences and D0L languages, Semiretracts of a free monoid, Exponential upper and lower bounds for the order of a regular language, Periodic D0L languages, On purely morphic characterizations of context-free languages, Bounded D0L languages, On a public-key cryptosystem based on iterated morphisms and substitutions, Thin and slender languages, Representations of language families by homomorphic equality operations and generalized equality sets, Context-free languages consisting of non-primitive words, On the subword equivalence problem for morphic words, A defect property of codes with unbounded delays, Decidability of the problem of semantic equivalence of words in the class of syntax-directed translations, On the subword complexity of m-free DOL languages, A necessary condition for the rationality of the zeta function of a regular language, The meet operation in the lattice of codes, Probabilistic Parallel Communicating Grammar Systems, Growth problems for avoidable words, On CD-systems of stateless deterministic R-automata with window size one, Generalization of the Ginsburg-Rice Schuetzenberger fixed-point theorem for context-sensitive and recursive-enumerable languages, A homomorphic characterization of regular languages, Growth, unavoidable words, and M. Sapir's conjecture for semigroup varieties., Permutations are not context-free: An application of the interchange lemma, On infinite words obtained by iterating morphisms, Some algorithms for equivalent transformation of nondeterministic finite automata, Refining the hierarchy of blind multicounter languages and twist-closed trios., A note on morphic characterization of languages, Density of grammar forms. part I, Density of grammar forms part II, Time varying finite automata, Fibonacci morphisms and Sturmian words, Bounded delay L codes, Languages and P0L schemes, Polynomial growth in semigroup varieties., Language-theoretic problems arising from Richelieu cryptosystems, Efficient constructions of test sets for regular and context-free languages, Relatively free semigroups of intermediate growth, Marked PCP is decidable, On characterisation of language families in terms of inverse morphisms, Fuzzy \(L\) languages, Regularity of sets of initial strings of periodic D0L-systems, On the subword complexity of iteratively generated infinite words., On combinatorial properties of the Arshon sequence, Operations and language generating devices suggested by the genome evolution, TYPES OF GROWTH AND IDENTITIES OF SEMIGROUPS, Morphisms and almost-periodicity, Sticker systems, MEMBERSHIP AND FINITENESS PROBLEMS FOR RATIONAL SETS OF REGULAR LANGUAGES, THE EXISTENCE OF A PATTERN WHICH IS 5-AVOIDABLE BUT 4-UNAVOIDABLE, Morphismes unispectraux. (Unispectral morphisms), Monomial algebras, It is decidable whether or not a permutation-free morphism is an l code, On cube-free \(\omega\)-words generated by binary morphisms, A homomorphic characterization of principal semi AFLs without using intersection with regular sets, On repetition-free binary words of minimal density, Some remarks on non-algebraic adherences, L codes and number systems, On the size of the alphabet and the subword complexity of square-free DOL languages, Globally deterministic CD-systems of stateless R-automata with window size 1, Unique representation in number systems and L codes, Homomorphic characterizations of recursively enumerable languages with very small language classes, On the regularity of languages generated by context-free evolutionary grammars, A complete inference system for a class of regular behaviours, Topics in the theory of DNA computing., Infinite arrays and controlled deterministic table 0L array systems, 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, A characterization of overlap-free morphisms, On k-repetition freeness of length uniform morphisms over a binary alphabet, Complexity of normal form grammars, On regularity of languages generated by copying systems, A homomorphic characterization of recursively enumerable languages, Homomorphisms of 3-chromatic graphs, A characterization of power-free morphisms, On three-element codes, Feedback automata and their languages, Many aspects of formal languages, On infinite words obtained by selective substitution grammars, Test sets for morphisms with bounded delay, Inferring regular languages by merging nonterminals, The commutation of finite sets: A challenging problem, SE-SYSTEMS, TIMING MECHANISMS, AND TIME-VARYING CODES, Adherences of DOL languages