The decidability of the equivalence problem for DOL-systems

DOI10.1016/S0019-9958(77)90512-5MaRDI QIDQ4140409zbMATH OpenFDO

Authors Karel II Culik, Ivan Friš

Publication date 1977

Published in Information and Control (Search for Journal in Brave)

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Genetics and epigenetics (92D10) General biology and biomathematics (92B05) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35)

Cited in

(43)

• REMARKS CONCERNING THE D0L ω-EQUIVALENCE PROBLEM
• On binary equality sets and a solution to the test set conjecture in the binary case
• Equality sets of binary D0L sequences
• THE D0L ω-EQUIVALENCE PROBLEM
• On test sets for checking morphism equivalence on languages with fair distribution of letters
• Every two equivalent DOL systems have a regular true envelope
• The decidability of the FOL-DOL equivalence problem
• A survey on decidable equivalence problems for tree transducers
• Equality sets of morphic word sequences
• Some decidability results about regular and pushdown translations
• Systems of equations over a free monoid and Ehrenfeucht's conjecture
• On the subword equivalence problem for morphic words
• On infinite words generated by polynomial D0L systems
• Marked D0L systems and the \(2n\)-conjecture
• Systems of equations over a finite set of words and automata theory
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• New techniques for proving the decidability of equivalence problem
• The language equivalence problem for HD0L systems having D0L growths
• Balance of many-valued transductions and equivalence problems
• The equivalence of finite valued transducers (on HDT0L languages) is decidable
• Equations over finite sets of words and equivalence problems in automata theory
• Elementary homomorphisms and a solution of the DOL sequence equivalence problem
• Lindenmayer grammars and symbolic testing
• A new bound for the D0L sequence equivalence problem
• A homomorphic characterization of time and space complexity classes of languages†
• Homomorphism equivalence on etol languages†
• The decidability of the DOL-DTOL equivalence problem
• The equivalence problem for DF0L languages and power series.
• Test sets and checking words for homomorphism equivalence
• On the decidability of homomorphism equivalence for languages
• Easy cases of the D0L sequence equivalence problem
• Interactive L systems with a fast local growth
• Representations of language families by homomorphic equality operations and generalized equality sets
• On infinite words obtained by iterating morphisms
• D0L sequence equivalence is inPfor fixed alphabets
• On a bound for the DOL sequence equivalence problem
• Elementariness of a finite set of words is co-NP-complete
• Dominoes over a free monoid
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• Bounds for the D0L language equivalence problem
• On some decidability problems for HDOL systems with nonsingular Parikh matrices
• The decidability of v-local catenativity and of other properties of DOL systems
• The equivalence problem for languages defined by transductions on D0L languages

This page was built for publication: The decidability of the equivalence problem for DOL-systems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4140409)