Linear Orders in the Pushdown Hierarchy

DOI10.1007/978-3-642-14162-1_8zbMATH Open1288.68150OpenAlexW154015193MaRDI QIDQ3587429FDOQ3587429

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

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

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)

Cited In (6)

• Title not available (Why is that?)
• Title not available (Why is that?)
• An undecidable property of context-free linear orders
• Word-mappings of level 2
• 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)