The decidability of the equivalence problem for DOL-systems

DOI10.1016/S0019-9958(77)90512-5zbMATH Open0365.68074MaRDI QIDQ4140409FDOQ4140409

Publication date: 1977

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

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
Lindenmayer grammars and symbolic testing
A new bound for the D0L sequence equivalence problem
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
Homomorphism equivalence on etol languages†
On the decidability of homomorphism equivalence for 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†
The equivalence problem for languages defined by transductions on D0L languages
New techniques for proving the decidability of equivalence problem
Dominoes over a free monoid
Balance of many-valued transductions and equivalence problems
On infinite words generated by polynomial D0L systems
On test sets for checking morphism equivalence on languages with fair distribution of letters
A survey on decidable equivalence problems for tree transducers
Systems of equations over a finite set of words and automata theory
On the subword equivalence problem for morphic words
D0L sequence equivalence is inPfor fixed alphabets
On infinite words obtained by iterating morphisms
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)