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)

Full work available at URL https://doi.org/10.1016/S0019-9958(77)90512-5

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)

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

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)