On the equivalence problem for binary DOL systems

DOI10.1016/S0019-9958(81)90367-3MaRDI QIDQ3962486zbMATH OpenFDO

Authors Juhani Karhumäki

Publication date 1981

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

Full work available at URL https://doi.org/10.1016/S0019-9958(81)90367-3

zbMATH Keywords

characterization of equality languagesDOL equivalence problem

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42) Formal languages and automata (68Q45)

Cited in

(12)

• Fibonacci morphisms and Sturmian words
• Equality sets of binary D0L sequences
• Explicit test sets for iterated morphisms in free monoids and metabelian groups
• A simple undecidable problem: the inclusion problem for finite substitutions on \(ab^* c\)
• An \(n^2\)-bound for the ultimate equivalence problem of certain D0L systems over an \(n\)-letter alphabet
• Equality sets of morphic word sequences
• D0L sequence equivalence is inPfor fixed alphabets
• Marked D0L systems and the 2n-conjecture
• Easy cases of the D0L sequence equivalence problem
• Bounds for the D0L language equivalence problem
• The Ehrenfeucht conjecture: A compactness claim for finitely generated free monoids
• A new bound for the D0L sequence equivalence problem

This page was built for publication: On the equivalence problem for binary DOL systems

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