Elementary homomorphisms and a solution of the DOL sequence equivalence problem
From MaRDI portal
Publication:1258182
DOI10.1016/0304-3975(78)90047-6zbMath0407.68085OpenAlexW2074488484MaRDI QIDQ1258182
Andrzej Ehrenfeucht, Grzegorz Rozenberg
Publication date: 1978
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0304-3975(78)90047-6
Related Items (40)
The equivalence problem for DF0L languages and power series. ⋮ On the defect theorem and simplifiability ⋮ Equality sets of binary D0L sequences ⋮ Representations of language families by homomorphic equality operations and generalized equality sets ⋮ A new bound for the D0L sequence equivalence problem ⋮ A bound for theω-equivalence problem of polynomial D0L systems ⋮ Bounds for the D0L language equivalence problem ⋮ Elementariness of a finite set of words is co-NP-complete ⋮ On a generalization of abelian equivalence and complexity of infinite words ⋮ A characterization of free pairs of upper triangular free monoid morphisms ⋮ Recognizability of morphisms ⋮ Decidable problems in substitution shifts ⋮ 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 ⋮ Bispecial factors in circular non-pushy D0L languages ⋮ Compatibility relations on codes and free monoids ⋮ The decidability of the DOL-DTOL equivalence problem ⋮ Maximal codes with bounded deciphering delay ⋮ An algorithm for enumerating all infinite repetitions in a D0L-system ⋮ The minimum substring cover problem ⋮ REMARKS CONCERNING THE D0L ω-EQUIVALENCE PROBLEM ⋮ Defect theorems with compatibility relations. ⋮ The language equivalence problem for HD0L systems having D0L growths ⋮ Characterization of circular D0L-systems ⋮ Easy cases of the D0L sequence equivalence problem ⋮ A periodicity property of iterated morphisms ⋮ The Minimum Substring Cover Problem ⋮ On the simplification of infinite morphic words ⋮ Reachability via Cooperating Morphisms ⋮ ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS ⋮ On the deficit of a finite set of words ⋮ EQUALITY SETS OF MORPHIC WORD SEQUENCES ⋮ On D0L power series ⋮ Checking sets, test sets, rich languages and commutatively closed languages ⋮ THE D0L ω-EQUIVALENCE PROBLEM ⋮ An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet ⋮ The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
Cites Work
This page was built for publication: Elementary homomorphisms and a solution of the DOL sequence equivalence problem
