On frontiers of regular trees

DOI10.1051/ITA/1986200403711zbMath0639.68071OpenAlexW187140616MaRDI QIDQ3780462

Wolfgang Thomas

Publication date: 1986

Published in: RAIRO - Theoretical Informatics and Applications (Search for Journal in Brave)

Full work available at URL: https://eudml.org/doc/92265

zbMATH Keywords

generalized wordsautomata on infinite treesequivalence of countable word- or order-typesmodel theory of linear orderings

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (16)

Order-theoretic Trees: Monadic Second-order Descriptions and Regularity ⋮ Two equational theories of partial words ⋮ Automata on linear orderings ⋮ Axiomatizing omega and omega-op powers of words ⋮ Regularity Equals Monadic Second-Order Definability for Quasi-trees ⋮ Büchi context-free languages ⋮ An undecidable property of context-free linear orders ⋮ Unnamed Item ⋮ Isomorphism of Regular Trees and Words ⋮ The equational theory of regular words ⋮ Tree Automata and Automata on Linear Orderings ⋮ Infinite hypergraphs. I: Basic properties ⋮ A KLEENE THEOREM FOR LANGUAGES OF WORDS INDEXED BY LINEAR ORDERINGS ⋮ 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

• Fundamental properties of infinite trees
• The monadic theory of order
• On the elementary theory of linear order
• Decidability of Second-Order Theories and Automata on Infinite Trees
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On frontiers of regular trees