Descriptional and computational complexity of finite automata -- a survey
From MaRDI portal
Publication:553312
DOI10.1016/j.ic.2010.11.013zbMath1217.68130OpenAlexW2000290048WikidataQ56431188 ScholiaQ56431188MaRDI QIDQ553312
Publication date: 27 July 2011
Published in: Information and Computation (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ic.2010.11.013
surveycomputational complexitydeterminismfinite automatanondeterminismalternationdescriptional complexity
Related Items
State complexity of permutation on finite languages over a binary alphabet ⋮ Scattered Factor-Universality of Words ⋮ State Complexity of Kleene-Star Operations on Trees ⋮ Descriptional Complexity of Input-Driven Pushdown Automata ⋮ COMPLEXITY IN UNION-FREE REGULAR LANGUAGES ⋮ The complexity of intersecting finite automata having few final states ⋮ On the semantics of atomic subgroups in practical regular expressions ⋮ Problems on finite automata and the exponential time hypothesis ⋮ Complexity of suffix-free regular languages ⋮ Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers* ⋮ The intersection problem for finite monoids ⋮ State Complexity of Prefix Distance ⋮ Checking Whether an Automaton Is Monotonic Is NP-complete ⋮ On linear languages recognized by deterministic biautomata ⋮ Absent Subsequences in Words ⋮ State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ Unnamed Item ⋮ State complexity of inversion operations ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Converting finite width AFAs to nondeterministic and universal finite automata ⋮ State complexity of the concatenation of regular tree languages ⋮ Cellular Automata: Descriptional Complexity and Decidability ⋮ Existential and universal width of alternating finite automata ⋮ Complexity of exclusive nondeterministic finite automata ⋮ Distributed graph problems through an automata-theoretic lens ⋮ On the computational complexity of problems related to distinguishability sets ⋮ Nondeterministic state complexity of star-free languages ⋮ A hitchhiker's guide to descriptional complexity through analytic combinatorics ⋮ Unnamed Item ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ On the expressive power of stateless ordered restart-delete automata ⋮ Walking on data words ⋮ Simple picture processing based on finite automata and regular grammars ⋮ Parametric runtime verification is NP-complete and coNP-complete ⋮ A multi-parameter analysis of hard problems on deterministic finite automata ⋮ Consensus String Problem for Multiple Regular Languages ⋮ NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS ⋮ LIMITED AUTOMATA AND REGULAR LANGUAGES ⋮ Complexity of universality and related problems for partially ordered NFAs ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Unnamed Item ⋮ Alternation in two-way finite automata ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ State complexity of deletion and bipolar deletion ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Minimal and Hyper-Minimal Biautomata ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ State Complexity of Suffix Distance ⋮ Consensus string problem for multiple regular languages ⋮ Transducing reversibly with finite state machines ⋮ Quasi-Distances and Weighted Finite Automata ⋮ Comparing the notions of opacity for discrete-event systems ⋮ State Complexity of Prefix Distance of Subregular Languages ⋮ Problems on Finite Automata and the Exponential Time Hypothesis ⋮ On Some Decision Problems for Stateless Deterministic Ordered Restarting Automata ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Constant-space, constant-randomness verifiers with arbitrarily small error ⋮ Undecidability of state complexity ⋮ Worst Case Branching and Other Measures of Nondeterminism ⋮ Structural properties of NFAs and growth rates of nondeterminism measures ⋮ State complexity of prefix distance
Cites Work
- The complexity of computing the permanent
- On equations for regular languages, finite automata, and sequential networks
- A lower bound technique for the size of nondeterministic finite automata
- \(NC^ 1\): The automata-theoretic viewpoint
- Minimizing finite automata is computationally hard
- Finite-automaton aperiodicity is PSPACE-complete
- On NFAs where all states are final, initial, or both
- Detecting palindromes, patterns and borders in regular languages
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- Succinct representation of regular languages by Boolean automata. II
- The method of forced enumeration for nondeterministic automata
- Finite automata and unary languages
- On counting and approximation
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Lower bounds on the size of sweeping automata
- Observations on the complexity of regular expression problems
- Succinct representation of regular languages by Boolean automata
- Classification of finite monoids: the language approach
- A note on the space complexity of some decision problems for finite automata
- The parallel complexity of finite-state automata problems
- Intersection and union of regular languages and state complexity
- A very hard log-space counting class
- Hierarchies of complete problems
- Space-bounded reducibility among combinatorial problems
- On the equivalence, containment, and covering problems for the regular and context-free languages
- Follow automata.
- Dot-depth of star-free events
- On uniformity within \(NC^ 1\)
- Optimal Simulations between Unary Automata
- Parity, circuits, and the polynomial-time hierarchy
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Constructions for alternating finite automata∗
- The Tractability Frontier for NFA Minimization
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Decision Problems for Convex Languages
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Complexity of some problems from the theory of automata
- Finite monoids and the fine structure of NC 1
- Nondeterministic Space is Closed under Complementation
- Alternation
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- On Equivalence and Containment Problems for Formal Languages
- Computational Parallels between the Regular and Context-Free Languages
- Complexity of automaton identification from given data
- Minimal NFA Problems are Hard
- Parallel complexity of iterated morphisms and the arithmetic of small numbers
- The emptiness problem for intersections of regular languages
- On finite monoids having only trivial subgroups
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Mathematical Foundations of Computer Science 2003
- A note on undecidable properties of formal languages
- Classes of languages and linear-bounded automata
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- STACS 2005
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
