Problems on Finite Automata and the Exponential Time Hypothesis

DOI10.1007/978-3-319-40946-7_8zbMath1475.68152OpenAlexW2506511039MaRDI QIDQ2830210

Andreas Krebs, Henning Fernau

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

zbMATH Keywords

finite automataexponential time hypothesisequivalence problemuniversality problememptiness of intersection

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (4)

Problems on finite automata and the exponential time hypothesis ⋮ Fine-grained complexity of safety verification ⋮ On the Complexity of Bounded Context Switching. ⋮ Characterization and complexity results on jumping finite automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Descriptional and computational complexity of finite automata -- a survey
• Finite-automaton aperiodicity is PSPACE-complete
• Finite automata and unary languages
• The parallel complexity of finite-state automata problems
• Hierarchies of complete problems
• Which problems have strongly exponential complexity?
• Polynomial complete problems in automata theory
• A multi-parameter analysis of hard problems on deterministic finite automata
• Characterization and complexity results on jumping finite automata
• Scanning Pictures the Boustrophedon Way
• Complexity of some problems from the theory of automata
• The membership problem in aperiodic transformation monoids
• JUMPING FINITE AUTOMATA
• Complexity of Problems of Commutative Grammars
• On finite monoids having only trivial subgroups
• Parameterized Algorithms

This page was built for publication: Problems on Finite Automata and the Exponential Time Hypothesis