Problems on finite automata and the exponential time hypothesis

DOI10.3390/A10010024zbMath1461.68101DBLPjournals/algorithms/FernauK17OpenAlexW2586499659WikidataQ59864887 ScholiaQ59864887MaRDI QIDQ1662614

Andreas Krebs, Henning Fernau

Publication date: 20 August 2018

Published in: Algorithms (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.3390/a10010024

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 (11)

On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection ⋮ Synchronizing words and monoid factorization, yielding a new parameterized complexity class? ⋮ On minimizing regular expressions without Kleene star ⋮ Learning from positive and negative examples: dichotomies and parameterized algorithms ⋮ Approximate NFA universality and related problems motivated by information theory ⋮ Constrained synchronization and commutativity ⋮ Unnamed Item ⋮ On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract) ⋮ Semicomputable points in Euclidean spaces ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Approximate NFA universality motivated by information theory

Uses Software

• Antichains

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial kernels for weighted problems
• Fundamentals of parameterized complexity
• Decision problems for convex languages
• Descriptional and computational complexity of finite automata -- a survey
• Exact exponential algorithms.
• Finite-automaton aperiodicity is PSPACE-complete
• Boundary sets of regular and context-free languages
• Finite automata and unary languages
• The parallel complexity of finite-state automata problems
• Hierarchies of complete problems
• On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
• Intractability of decision problems for finite-memory automata
• Which problems have strongly exponential complexity?
• Explicit estimates of some functions over primes
• Polynomial complete problems in automata theory
• A multi-parameter analysis of hard problems on deterministic finite automata
• Regular expressions for data words
• Characterization and complexity results on jumping finite automata
• Scanning Pictures the Boustrophedon Way
• Problems on Finite Automata and the Exponential Time Hypothesis
• A Survey on Picture-Walking Automata
• Commutative grammars: The complexity of uniform word problems
• On the Complexity of Intersecting Regular, Context-Free, and Tree Languages
• Recognizable vs. Regular Picture Languages
• Linear FPT reductions and computational lower bounds
• Fast FAST
• Complexity of some problems from the theory of automata
• The membership problem in aperiodic transformation monoids
• JUMPING FINITE AUTOMATA
• Some results concerning two-dimensional turing machines and finite automata
• The emptiness problem for intersections of regular languages
• Hardness Results for Intersection Non-Emptiness
• Complexity of Problems of Commutative Grammars
• Analytical approach to parallel repetition
• On finite monoids having only trivial subgroups
• Parameterized Algorithms
• Antichains: A New Algorithm for Checking Universality of Finite Automata
• Theory Is Forever

This page was built for publication: Problems on finite automata and the exponential time hypothesis