Linear Orders in the Pushdown Hierarchy

DOI10.1007/978-3-642-14162-1_8MaRDI QIDQ3587429zbMATH OpenOpenAlexFDO

Authors Laurent Braud, Arnaud Carayol

Publication date 7 September 2010

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-14162-1_8

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Total orders (06A05) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• scientific article; zbMATH DE number 3882490
• A construction for recursive linear orderings
• Tree-definable linear orders
• A recursion principle for linear orderings
• Linear orderings of low degree
• Decidable discrete linear orders
• Hierarchy among automata on linear orderings
• Acyclic sets of linear orders
• Linearization of definable order relations
• Lexicographic order and linearity

Cited in

(8)

• An undecidable property of context-free linear orders
• Word-mappings of level 2
• scientific article; zbMATH DE number 3880666 (Why is no real title available?)
• scientific article; zbMATH DE number 68156 (Why is no real title available?)
• The structure of trees in the pushdown hierarchy
• Automatic structures and the problem of natural well-orderings
• A new pumping lemma for indexed languages, with an application to infinite words
• Regular sets over extended tree structures

This page was built for publication: Linear Orders in the Pushdown Hierarchy

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