Problems on finite automata and the exponential time hypothesis
DOI10.3390/A10010024zbMATH Open1461.68101DBLPjournals/algorithms/FernauK17OpenAlexW2586499659WikidataQ59864887 ScholiaQ59864887MaRDI QIDQ1662614FDOQ1662614
Authors: Henning Fernau, A. Krebs 
Publication date: 20 August 2018
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a10010024
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
- Fundamentals of parameterized complexity
- Exact exponential algorithms.
- Which problems have strongly exponential complexity?
- Complexity of some problems from the theory of automata
- Lower bounds based on the exponential time hypothesis
- On the possibility of faster \textsc{SAT} algorithms
- Parameterized algorithms
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- Polynomial complete problems in automata theory
- Antichains: A New Algorithm for Checking Universality of Finite Automata
- Finite-automaton aperiodicity is PSPACE-complete
- Analytical approach to parallel repetition
- Title not available (Why is that?)
- Fast FAST
- Hierarchies of complete problems
- On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
- A survey on picture-walking automata
- The membership problem in aperiodic transformation monoids
- Title not available (Why is that?)
- The emptiness problem for intersections of regular languages
- Descriptional and computational complexity of finite automata -- a survey
- Linear FPT reductions and computational lower bounds
- Finite automata and unary languages
- Commutative grammars: The complexity of uniform word problems
- Title not available (Why is that?)
- Intractability of decision problems for finite-memory automata
- Explicit estimates of some functions over primes
- Complexity of problems of commutative grammars
- The parallel complexity of finite-state automata problems
- Decision problems for convex languages
- Some results concerning two-dimensional turing machines and finite automata
- Theory Is Forever
- Boundary sets of regular and context-free languages
- Recognizable vs. Regular Picture Languages
- On the complexity of intersecting regular, context-free, and tree languages
- Tightening the complexity of equivalence problems for commutative grammars
- Hardness results for intersection non-emptiness
- 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
- Title not available (Why is that?)
- Jumping finite automata
Cited In (17)
- Constrained synchronization and commutativity
- Title not available (Why is that?)
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Approximate NFA universality motivated by information theory
- 200 Problems on Languages, Automata, and Computation
- On minimizing regular expressions without Kleene star
- Lengths of words accepted by nondeterministic finite automata
- Problems on finite automata and the exponential time hypothesis
- An Infinite Automaton Characterization of Double Exponential Time
- Approximate NFA universality and related problems motivated by information theory
- Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- Learning from positive and negative examples: dichotomies and parameterized algorithms
- On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)
- Semicomputable points in Euclidean spaces
- Title not available (Why is that?)
- Title not available (Why is that?)
Uses Software
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 Q1662614)
