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

DecidabilityHomomorphismEquivalence ProblemDol SystemsElementary LanguageRecognition By Automata

Mathematics Subject Classification ID

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

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

(40)

• Reachability via cooperating morphisms
• Bispecial factors in circular non-pushy D0L languages
• Decidable problems in substitution shifts
• Checking sets, test sets, rich languages and commutatively closed languages
• A bound for theω-equivalence problem of polynomial D0L systems
• 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
• Recognizability of morphisms
• Test sets and checking words for homomorphism equivalence
• Maximal codes with bounded deciphering delay
• Marked D0L systems and the 2n-conjecture
• A new bound for the D0L sequence equivalence problem
• On the simplification of infinite morphic words
• On the defect theorem and simplifiability
• Equality sets of binary D0L sequences
• Defect theorems with compatibility relations.
• Bounds for the D0L language equivalence problem
• The language equivalence problem for HD0L systems having D0L growths
• Compatibility relations on codes and free monoids
• REMARKS CONCERNING THE D0L ω-EQUIVALENCE PROBLEM
• On a bound for the DOL sequence equivalence problem
• ON THE POWER OF COOPERATING MORPHISMS VIA REACHABILITY PROBLEMS
• 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 minimum substring cover 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
• The Minimum Substring Cover Problem
• An algorithm for enumerating all infinite repetitions in a D0L-system
• On D0L power series
• A characterization of free pairs of upper triangular free monoid morphisms
• On the deficit of a finite set of words
• D0L sequence equivalence is inPfor fixed alphabets
• THE D0L ω-EQUIVALENCE PROBLEM
• Characterization of circular D0L-systems
• A periodicity property of iterated morphisms
• On a generalization of abelian equivalence and complexity of infinite words
• Easy cases of the D0L sequence equivalence 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)