scientific article; zbMATH DE number 4028926

MaRDI QIDQ3769982zbMATH OpenFDO

Authors Juhani Karhumäki

Publication date 1987

zbMATH Keywords

bibliographyD0L sequence equivalence problemEhrenfeucht conjectureEquality languagesformal languagemorphismPost correspondence problemsurvey

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Semigroups in automata theory, linguistics, etc. (20M35) Research exposition (monographs, survey articles) pertaining to computer science (68-02) Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 4090810
• A new bound for the D0L language equivalence problem
• scientific article; zbMATH DE number 3868642
• scientific article; zbMATH DE number 1512077
• Bounds for the D0L language equivalence problem

Cited in

(17)

• Prefix and equality languages of rational functions are co-context-free
• Multiplicities: A deterministic view of nondeterminism
• On the size of independent systems of equations in semigroups
• Flatwords and Post Correspondence Problem
• Modern aspects of complexity within formal languages
• scientific article; zbMATH DE number 3868642 (Why is no real title available?)
• Elementariness of a finite set of words is co-NP-complete
• Large Simple Binary Equality Words
• scientific article; zbMATH DE number 4037247 (Why is no real title available?)
• scientific article; zbMATH DE number 4039335 (Why is no real title available?)
• scientific article; zbMATH DE number 4090810 (Why is no real title available?)
• On the size of independent systems of equations in semigroups
• Polynomial size test sets for context-free languages
• Efficient constructions of test sets for regular and context-free languages
• Equations over finite sets of words and equivalence problems in automata theory
• The equivalence problem of multitape finite automata
• New techniques for proving the decidability of equivalence problem

This page was built for publication:

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