The decidability of the equivalence problem for DOL-systems
From MaRDI portal
Publication:4140409
DOI10.1016/S0019-9958(77)90512-5zbMath0365.68074MaRDI QIDQ4140409
Publication date: 1977
Published in: Information and Control (Search for Journal in Brave)
Formal languages and automata (68Q45) Free semigroups, generators and relations, word problems (20M05) Semigroups in automata theory, linguistics, etc. (20M35) Genetics and epigenetics (92D10) General biology and biomathematics (92B05)
Related Items (43)
The equivalence problem for DF0L languages and power series. ⋮ The equivalence of finite valued transducers (on HDT0L languages) is decidable ⋮ Equality sets of binary D0L sequences ⋮ Balance of many-valued transductions and equivalence problems ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ A new bound for the D0L sequence equivalence problem ⋮ On the subword equivalence problem for morphic words ⋮ Interactive L systems with a fast local growth ⋮ Bounds for the D0L language equivalence problem ⋮ On some decidability problems for HDOL systems with nonsingular Parikh matrices ⋮ Elementariness of a finite set of words is co-NP-complete ⋮ Systems of equations over a finite set of words and automata theory ⋮ Test sets and checking words for homomorphism equivalence ⋮ On a bound for the DOL sequence equivalence problem ⋮ D0L sequence equivalence is inPfor fixed alphabets ⋮ Marked D0L systems and the \(2n\)-conjecture ⋮ Every two equivalent DOL systems have a regular true envelope ⋮ New techniques for proving the decidability of equivalence problem ⋮ The decidability of the DOL-DTOL equivalence problem ⋮ On infinite words obtained by iterating morphisms ⋮ Equations over finite sets of words and equivalence problems in automata theory ⋮ REMARKS CONCERNING THE D0L ω-EQUIVALENCE PROBLEM ⋮ The language equivalence problem for HD0L systems having D0L growths ⋮ Easy cases of the D0L sequence equivalence problem ⋮ On infinite words generated by polynomial D0L systems ⋮ The decidability of v-local catenativity and of other properties of DOL systems ⋮ Lindenmayer grammars and symbolic testing ⋮ A Survey on Decidable Equivalence Problems for Tree Transducers ⋮ On the decidability of homomorphism equivalence for languages ⋮ Some decidability results about regular and pushdown translations ⋮ The decidability of the FOL-DOL equivalence problem ⋮ A homomorphic characterization of time and space complexity classes of languages† ⋮ The equivalence problem for languages defined by transductions on D0L languages ⋮ Elementary homomorphisms and a solution of the DOL sequence equivalence problem ⋮ Homomorphism equivalence on etol languages† ⋮ EQUALITY SETS OF MORPHIC WORD SEQUENCES ⋮ Dominoes over a free monoid ⋮ Systems of equations over a free monoid and Ehrenfeucht's conjecture ⋮ THE D0L ω-EQUIVALENCE PROBLEM ⋮ An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet ⋮ On binary equality sets and a solution to the test set conjecture in the binary case ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids ⋮ On test sets for checking morphism equivalence on languages with fair distribution of letters
This page was built for publication: The decidability of the equivalence problem for DOL-systems
