Problems on finite automata and the exponential time hypothesis

DOI10.3390/A10010024MaRDI QIDQ1662614zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Henning Fernau, A. Krebs

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license File:Creative commons license with attribution.png Creative Commons Attribution 4.0 International

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

zbMATH Keywords

emptiness of intersectionequivalence problemexponential time hypothesisfinite automatauniversality problem

Mathematics Subject Classification ID

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

Review text

Summary: We study several classical decision problems on finite automata under the (Strong) Exponential Time Hypothesis. We focus on three types of problems: universality, equivalence, and emptiness of intersection. All these problems are known to be CoNP-hard for nondeterministic finite automata, even when restricted to unary input alphabets. A different type of problems on finite automata relates to aperiodicity and to synchronizing words. We also consider finite automata that work on commutative alphabets and those working on two-dimensional words.

Recommendations

• Problems on finite automata and the exponential time hypothesis
• scientific article; zbMATH DE number 459363
• Complexity of some problems from the theory of automata
• A multi-parameter analysis of hard problems on deterministic finite automata
• Minimal NFA Problems are Hard

Cites work

• 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
• 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?)
• 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

(21)

• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Approximate NFA universality motivated by information theory
• On minimizing regular expressions without Kleene star
• Learning from positive and negative examples: dichotomies and parameterized algorithms
• Lengths of words accepted by nondeterministic finite automata
• Constrained synchronization and commutativity
• Problems on finite automata and the exponential time hypothesis
• An Infinite Automaton Characterization of Double Exponential Time
• scientific article; zbMATH DE number 4026835 (Why is no real title available?)
• On the Fine Grained Complexity of Finite Automata Non-emptiness of Intersection
• Synchronizing words and monoid factorization, yielding a new parameterized complexity class?
• scientific article; zbMATH DE number 7559442 (Why is no real title available?)
• Semicomputable points in Euclidean spaces
• scientific article; zbMATH DE number 3294598 (Why is no real title available?)
• 200 Problems on Languages, Automata, and Computation
• Approximate NFA universality and related problems motivated by information theory
• On pumping preserving homomorphisms and the complexity of the pumping problem (extended abstract)
• Subset mapping problems in solvable automata
• Languages given by finite automata over the unary alphabet
• Incremental algorithms for solving regular expression intersection non-emptiness
• Languages given by finite automata over the unary alphabet

Describes a project that uses

Uses Software

• Antichains

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)