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

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

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

(6)

• scientific article; zbMATH DE number 3880666 (Why is no real title available?)
• scientific article; zbMATH DE number 68156 (Why is no real title available?)
• An undecidable property of context-free linear orders
• A new pumping lemma for indexed languages, with an application to infinite words
• Word-mappings of level 2
• 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)