Problems on finite automata and the exponential time hypothesis
DOI10.1007/978-3-319-40946-7_8zbMATH Open1475.68152OpenAlexW2506511039MaRDI QIDQ2830210FDOQ2830210
Authors: Henning Fernau, A. Krebs 
Publication date: 9 November 2016
Published in: Implementation and Application of Automata (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-40946-7_8
Recommendations
exponential time hypothesisfinite automataequivalence problemuniversality problememptiness of intersection
Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Which problems have strongly exponential complexity?
- Complexity of some problems from the theory of automata
- Lower bounds based on the exponential time hypothesis
- Parameterized algorithms
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- Polynomial complete problems in automata theory
- Finite-automaton aperiodicity is PSPACE-complete
- Hierarchies of complete problems
- The membership problem in aperiodic transformation monoids
- Title not available (Why is that?)
- Descriptional and computational complexity of finite automata -- a survey
- Finite automata and unary languages
- Complexity of problems of commutative grammars
- The parallel complexity of finite-state automata problems
- Tightening the complexity of equivalence problems for commutative grammars
- A multi-parameter analysis of hard problems on deterministic finite automata
- Characterization and complexity results on jumping finite automata
- Scanning pictures the boustrophedon way
- Jumping finite automata
Cited In (8)
- Fine-grained complexity of safety verification
- 200 Problems on Languages, Automata, and Computation
- Problems on finite automata and the exponential time hypothesis
- An Infinite Automaton Characterization of Double Exponential Time
- Characterization and complexity results on jumping finite automata
- On the Complexity of Bounded Context Switching.
- Title not available (Why is that?)
- Title not available (Why is that?)
This page was built for publication: Problems on finite automata and the exponential time hypothesis
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2830210)
