Problems on finite automata and the exponential time hypothesis
From MaRDI portal
Publication:1662614
Recommendations
Cites work
- scientific article; zbMATH DE number 3823146 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 1735642 (Why is no real title available?)
- scientific article; zbMATH DE number 1775632 (Why is no real title available?)
- scientific article; zbMATH DE number 3222112 (Why is no real title available?)
- A multi-parameter analysis of hard problems on deterministic finite automata
- A survey on picture-walking automata
- Analytical approach to parallel repetition
- Antichains: A New Algorithm for Checking Universality of Finite Automata
- Boundary sets of regular and context-free languages
- Characterization and complexity results on jumping finite automata
- Commutative grammars: The complexity of uniform word problems
- Complexity of problems of commutative grammars
- Complexity of some problems from the theory of automata
- Decision problems for convex languages
- Descriptional and computational complexity of finite automata -- a survey
- Exact exponential algorithms.
- Explicit estimates of some functions over primes
- Fast FAST
- Finite automata and unary languages
- Finite-automaton aperiodicity is PSPACE-complete
- Fundamentals of parameterized complexity
- Hardness results for intersection non-emptiness
- Hierarchies of complete problems
- Intractability of decision problems for finite-memory automata
- Jumping finite automata
- Linear FPT reductions and computational lower bounds
- Lower bounds based on the exponential time hypothesis
- On finite monoids having only trivial subgroups
- On the complexity of intersecting finite state automata and \(\mathcal{NL}\) versus \(\mathcal{NP}\)
- On the complexity of intersecting regular, context-free, and tree languages
- On the possibility of faster \textsc{SAT} algorithms
- Parameterized algorithms
- Polynomial complete problems in automata theory
- Problems on finite automata and the exponential time hypothesis
- Recognizable vs. Regular Picture Languages
- Regular expressions for data words
- Scanning pictures the boustrophedon way
- Some results concerning two-dimensional turing machines and finite automata
- The emptiness problem for intersections of regular languages
- The membership problem in aperiodic transformation monoids
- The parallel complexity of finite-state automata problems
- Theory Is Forever
- Tightening the complexity of equivalence problems for commutative grammars
- Which problems have strongly exponential complexity?
Cited in
(17)- Constrained synchronization and commutativity
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- 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?
- Learning from positive and negative examples: dichotomies and parameterized algorithms
- On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
- On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)
- Semicomputable points in Euclidean spaces
- scientific article; zbMATH DE number 3294598 (Why is no real title available?)
- scientific article; zbMATH DE number 4026835 (Why is no real title available?)
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)
