An Infinite Automaton Characterization of Double Exponential Time

DOI10.1007/978-3-540-87531-4_5zbMath1157.68040OpenAlexW1566306817MaRDI QIDQ3540169

Salvatore La Torre, Gennaro Parlato, P. Madhusudan

Publication date: 20 November 2008

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://eprints.soton.ac.uk/272460/1/fulltext.pdf

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (9)

Some properties of the Fibonacci sequence on an infinite alphabet ⋮ Realizability of concurrent recursive programs ⋮ On the Complexity of Intersecting Regular, Context-Free, and Tree Languages ⋮ The complexity of model checking multi-stack systems ⋮ Emptiness of Multi-pushdown Automata Is 2ETIME-Complete ⋮ Reachability of scope-bounded multistack pushdown systems ⋮ Emptiness of Ordered Multi-Pushdown Automata is 2ETIME-Complete ⋮ Games on Multi-stack Pushdown Systems ⋮ Reachability of Multistack Pushdown Systems with Scope-Bounded Matching Relations

Uses Software

• Bebop

Cites Work

• Linearly bounded infinite graphs
• Alternating tree automata
• The theory of ends, pushdown automata, and second-order logic
• Traces of Term-Automatic Graphs
• Visibly pushdown languages
• Alternation
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Context-Sensitive Languages, Rational Graphs and Determinism
• Computer Aided Verification
• Context-Bounded Analysis of Concurrent Queue Systems
• Formal Reductions of the General Combinatorial Decision Problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: An Infinite Automaton Characterization of Double Exponential Time