An Infinite Automaton Characterization of Double Exponential Time

DOI10.1007/978-3-540-87531-4_5MaRDI QIDQ3540169zbMATH OpenOpenAlexFDO

Authors Salvatore La Torre, Parthasarathy Madhusudan, Gennaro Parlato

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)

Recommendations

• scientific article; zbMATH DE number 3309210
• Problems on finite automata and the exponential time hypothesis
• Problems on finite automata and the exponential time hypothesis
• Two double-exponential gaps for automata with a limited pushdown
• Two double-exponential gaps for automata with a limited pushdown
• Infinite time extensions of Kleene's \({\mathcal O}\)
• A note on the decomposition of infinite automata
• A Survey of Infinite Time Turing Machines
• General exponential dichotomies: from finite to infinite time
• On MITL and alternating timed automata over infinite words

Cites work

• scientific article; zbMATH DE number 1670555 (Why is no real title available?)
• scientific article; zbMATH DE number 3664335 (Why is no real title available?)
• scientific article; zbMATH DE number 1223729 (Why is no real title available?)
• scientific article; zbMATH DE number 1929936 (Why is no real title available?)
• scientific article; zbMATH DE number 2087217 (Why is no real title available?)
• scientific article; zbMATH DE number 1834676 (Why is no real title available?)
• scientific article; zbMATH DE number 2102748 (Why is no real title available?)
• scientific article; zbMATH DE number 803291 (Why is no real title available?)
• Alternating tree automata
• Alternation
• Computer Aided Verification
• Context-Bounded Analysis of Concurrent Queue Systems
• Context-Sensitive Languages, Rational Graphs and Determinism
• FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
• Formal Reductions of the General Combinatorial Decision Problem
• Linearly bounded infinite graphs
• The synchronized graphs trace the context-sensitive languages
• The theory of ends, pushdown automata, and second-order logic
• Traces of Term-Automatic Graphs
• Visibly pushdown languages

Cited in

(9)

• Reachability of scope-bounded multistack pushdown systems
• On the complexity of intersecting regular, context-free, and tree languages
• Emptiness of Multi-pushdown Automata Is 2ETIME-Complete
• Some properties of the Fibonacci sequence on an infinite alphabet
• Games on Multi-stack Pushdown Systems
• Emptiness of ordered multi-pushdown automata is 2ETIME-complete
• The complexity of model checking multi-stack systems
• Realizability of concurrent recursive programs
• Reachability of multistack pushdown systems with scope-bounded matching relations

Describes a project that uses

Uses Software

• Bebop

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

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