Elementary homomorphisms and a solution of the DOL sequence equivalence problem

DOI10.1016/0304-3975(78)90047-6MaRDI QIDQ1258182zbMATH OpenOpenAlexFDO

Authors 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

zbMATH Keywords

DecidabilityDol SystemsElementary LanguageEquivalence ProblemHomomorphismRecognition By Automata

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Formal languages and automata (68Q45)

Cites work

• scientific article; zbMATH DE number 3644504 (Why is no real title available?)
• scientific article; zbMATH DE number 3569855 (Why is no real title available?)
• Subword complexities of various classes of deterministic developmental languages without interactions
• The decidability of the equivalence problem for DOL-systems

Cited in

(42)

• On the simplification of infinite morphic words
• On the defect theorem and simplifiability
• Representations of language families by homomorphic equality operations and generalized equality sets
• Test sets and checking words for homomorphism equivalence
• On a bound for the DOL sequence equivalence problem
• Every two equivalent DOL systems have a regular true envelope
• The decidability of the DOL-DTOL equivalence problem
• Maximal codes with bounded deciphering delay
• On D0L power series
• Equality sets of binary D0L sequences
• The language equivalence problem for HD0L systems having D0L growths
• On the deficit of a finite set of words
• Checking sets, test sets, rich languages and commutatively closed languages
• The equivalence problem for DF0L languages and power series.
• Characterization of circular D0L-systems
• A characterization of free pairs of upper triangular free monoid morphisms
• Defect theorems with compatibility relations.
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• Equality sets of morphic word sequences
• REMARKS CONCERNING THE D0L ω-EQUIVALENCE PROBLEM
• THE D0L ω-EQUIVALENCE PROBLEM
• Elementariness of a finite set of words is co-NP-complete
• D0L sequence equivalence is inPfor fixed alphabets
• Compatibility relations on codes and free monoids
• ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS
• On a generalization of abelian equivalence and complexity of infinite words
• Marked D0L systems and the 2n-conjecture
• Bispecial factors in circular non-pushy D0L languages
• A bound for theω-equivalence problem of polynomial D0L systems
• An algorithm for enumerating all infinite repetitions in a D0L-system
• Reachability via cooperating morphisms
• A periodicity property of iterated morphisms
• The Minimum Substring Cover Problem
• Easy cases of the D0L sequence equivalence problem
• Bounds for the D0L language equivalence problem
• Recognizability of morphisms
• Decidable problems in substitution shifts
• The post correspondence problem and equalisers for certain free group and monoid morphisms
• Recognizability in S-adic shifts
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• A new bound for the D0L sequence equivalence problem
• The minimum substring cover problem

This page was built for publication: Elementary homomorphisms and a solution of the DOL sequence equivalence problem

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