Problems on finite automata and the exponential time hypothesis
From MaRDI portal
Publication:1662614
DOI10.3390/a10010024zbMath1461.68101OpenAlexW2586499659WikidataQ59864887 ScholiaQ59864887MaRDI QIDQ1662614
Publication date: 20 August 2018
Published in: Algorithms (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3390/a10010024
finite automataexponential time hypothesisequivalence problemuniversality problememptiness of intersection
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
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 ⋮ Semicomputable points in Euclidean spaces ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Approximate NFA universality motivated by information theory
Uses Software
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
