An Infinite Automaton Characterization of Double Exponential Time
From MaRDI portal
Publication:3540169
DOI10.1007/978-3-540-87531-4_5zbMATH Open1157.68040OpenAlexW1566306817MaRDI QIDQ3540169FDOQ3540169
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
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
Formal languages and automata (68Q45) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Cites Work
- Title not available (Why is that?)
- Formal Reductions of the General Combinatorial Decision Problem
- Visibly pushdown languages
- Alternation
- Title not available (Why is that?)
- Title not available (Why is that?)
- Context-Bounded Analysis of Concurrent Queue Systems
- Title not available (Why is that?)
- The theory of ends, pushdown automata, and second-order logic
- Computer Aided Verification
- Alternating tree automata
- FST TCS 2003: Foundations of Software Technology and Theoretical Computer Science
- Title not available (Why is that?)
- Title not available (Why is that?)
- The synchronized graphs trace the context-sensitive languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- Context-Sensitive Languages, Rational Graphs and Determinism
- Linearly bounded infinite graphs
- Traces of Term-Automatic Graphs
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
Uses Software
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)
