An undecidable property of context-free linear orders

DOI10.1016/j.ipl.2010.10.018zbMath1260.68202OpenAlexW2072374415MaRDI QIDQ1944046

Zoltán Ésik

Publication date: 4 April 2013

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.10.018

zbMATH Keywords

decidabilitycontext-free languageformal languageslexicographic ordering

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

ORDINAL AUTOMATA AND CANTOR NORMAL FORM ⋮ Unnamed Item ⋮ Isomorphisms of scattered automatic linear orders ⋮ The Order Type of Scattered Context-Free Orderings of Rank One Is Computable ⋮ Isomorphism of Regular Trees and Words ⋮ ON CONTEXT-FREE LANGUAGES OF SCATTERED WORDS ⋮ The ordinal generated by an ordinal grammar is computable ⋮ The isomorphism problem on classes of automatic structures with transitive relations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A representation of trees by languages. II
• The equational theory of regular words
• Automaticity of ordinals and of homogeneous graphs
• ALGEBRAIC LINEAR ORDERINGS
• Linear Orders in the Pushdown Hierarchy
• Regular and Algebraic Words and Ordinals
• On frontiers of regular trees
• Algebraic Ordinals
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Mathematical Foundations of Computer Science 2003

This page was built for publication: An undecidable property of context-free linear orders