scientific article; zbMATH DE number 5074397

MaRDI QIDQ3409982zbMATH OpenFDO

Authors Juhani Karhumäki, Vesa Halava, Tero Harju

Publication date 21 November 2006

zbMATH Keywords

\(\omega\)-languagesinfinite Post correspondence problem

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Undecidability and degrees of sets of sentences (03D35)

Recommendations

• Beyond $\omega$-Regular Languages
• Undecidability of the equivalence of finite substitutions on regular language
• A classification of \(\omega\)-regular languages
• Publication:4734777
• Inferring regular languages and \(\omega\)-languages
• scientific article; zbMATH DE number 871236
• Developments in Language Theory
• scientific article; zbMATH DE number 4043282
• Complexity of topological properties of regular \(\omega\)-languages
• Complexity of Topological Properties of Regular ω-Languages

Cited in

(11)

• scientific article; zbMATH DE number 4033715 (Why is no real title available?)
• The determinacy strength of pushdownω-languages
• On Post correspondence problem for letter monotonic languages
• The exact complexity of the infinite Post Correspondence Problem
• Hierarchy and equivalence of multi-letter quantum finite automata
• Three applications to rational relations of the high undecidability of the infinite Post correspondence problem in a regular \(\omega\)-language
• scientific article; zbMATH DE number 871236 (Why is no real title available?)
• From decidability to undecidability by considering regular sets of instances
• scientific article; zbMATH DE number 3976343 (Why is no real title available?)
• Two decidability problems for infinite words
• scientific article; zbMATH DE number 2087488 (Why is no real title available?)

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 Q3409982)