Descriptional and computational complexity of finite automata -- a survey
From MaRDI portal
Publication:553312
DOI10.1016/J.IC.2010.11.013zbMATH Open1217.68130OpenAlexW2000290048WikidataQ56431188 ScholiaQ56431188MaRDI QIDQ553312FDOQ553312
Authors: Markus Holzer, Martin Kutrib 
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
Recommendations
- Descriptional and Computational Complexity of Finite Automata
- scientific article; zbMATH DE number 2068876
- Descriptional and computational complexity of the circuit representation of finite automata
- Descriptional Complexity of Nondeterministic Finite Automata
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Descriptional complexity of limited automata
- Self-verifying finite automata and descriptional complexity
surveycomputational complexitydescriptional complexitydeterminismfinite automatanondeterminismalternation
Cites Work
- Title not available (Why is that?)
- Title not available (Why is that?)
- The complexity of computing the permanent
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- On uniformity within \(NC^ 1\)
- State complexity of regular languages
- Complexity of some problems from the theory of automata
- Title not available (Why is that?)
- Nondeterministic Space is Closed under Complementation
- Alternation
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Title not available (Why is that?)
- Parity, circuits, and the polynomial-time hierarchy
- Title not available (Why is that?)
- On finite monoids having only trivial subgroups
- The method of forced enumeration for nondeterministic automata
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Minimal NFA Problems are Hard
- Title not available (Why is that?)
- Classification of finite monoids: the language approach
- Dot-depth of star-free events
- Complexity of automaton identification from given data
- Finite-automaton aperiodicity is PSPACE-complete
- Detecting palindromes, patterns and borders in regular languages
- Hierarchies of complete problems
- Follow automata.
- Finite monoids and the fine structure of NC 1
- The emptiness problem for intersections of regular languages
- The Tractability Frontier for NFA Minimization
- Finite automata and unary languages
- A lower bound technique for the size of nondeterministic finite automata
- Title not available (Why is that?)
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- On counting and approximation
- A very hard log-space counting class
- Title not available (Why is that?)
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On equations for regular languages, finite automata, and sequential networks
- A note on the space complexity of some decision problems for finite automata
- Lower bounds on the size of sweeping automata
- Intersection and union of regular languages and state complexity
- On the equivalence, containment, and covering problems for the regular and context-free languages
- Optimal simulations between unary automata
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- 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
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- Title not available (Why is that?)
- Title not available (Why is that?)
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Minimizing finite automata is computationally hard
- Succinct representation of regular languages by Boolean automata
- Constructions for alternating finite automata∗
- Title not available (Why is that?)
- On NFAs where all states are final, initial, or both
- Space-bounded reducibility among combinatorial problems
- Succinct representation of regular languages by Boolean automata. II
- Observations on the complexity of regular expression problems
- The parallel complexity of finite-state automata problems
- Decision Problems for Convex Languages
- Title not available (Why is that?)
- Title not available (Why is that?)
- On Equivalence and Containment Problems for Formal Languages
- Title not available (Why is that?)
- Computational Parallels between the Regular and Context-Free Languages
- Title not available (Why is that?)
- Parallel complexity of iterated morphisms and the arithmetic of small numbers
- Mathematical Foundations of Computer Science 2003
- On emptiness and counting for alternating finite automata
- A note on undecidable properties of formal languages
- Classes of languages and linear-bounded automata
- STACS 2005
- \(NC^ 1\): The automata-theoretic viewpoint
Cited In (76)
- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- Comparing the notions of opacity for discrete-event systems
- The complexity of intersecting finite automata having few final states
- The state complexity of permutations on finite languages over binary alphabets
- Title not available (Why is that?)
- Descriptional complexity -- an introductory survey
- State complexity of the concatenation of regular tree languages
- On the expressive power of stateless ordered restart-delete automata
- State complexity bounds for the commutative closure of group languages
- State complexity of permutation on finite languages over a binary alphabet
- Simple picture processing based on finite automata and regular grammars
- Lower bounds for the size of deterministic unranked tree automata
- On the semantics of atomic subgroups in practical regular expressions
- On the complexity of decision problems for some classes of machines and applications
- State complexity of deletion and bipolar deletion
- Complexity of universality and related problems for partially ordered NFAs
- Nondeterministic state complexity of star-free languages
- Nondeterministic state complexity of star-free languages
- Descriptional complexity of unambiguous input-driven pushdown automata
- Alternation in two-way finite automata
- STACS 2004
- The intersection problem for finite monoids
- Descriptive set theoretic methods in automata theory. Decidability and topological complexity
- State complexity of prefix distance of subregular languages
- Descriptional and Computational Complexity of Finite Automata
- State complexity of Kleene-star operations on trees
- Consensus string problem for multiple regular languages
- Problems on finite automata and the exponential time hypothesis
- Problems on finite automata and the exponential time hypothesis
- Checking whether an automaton is monotonic is NP-complete
- Structural properties of NFAs and growth rates of nondeterminism measures
- Operational state complexity of unary NFAs with finite nondeterminism
- State complexity of inversion operations
- State complexity of prefix distance
- State complexity of prefix distance
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- Complexity of exclusive nondeterministic finite automata
- Title not available (Why is that?)
- Descriptional complexity of input-driven pushdown automata
- Scattered Factor-Universality of Words
- A multi-parameter analysis of hard problems on deterministic finite automata
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- On linear languages recognized by deterministic biautomata
- Existential and universal width of alternating finite automata
- Automata Presenting Structures: A Survey of the Finite String Case
- Distributed graph problems through an automata-theoretic lens
- Walking on data words
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Complexity of suffix-free regular languages
- On the descriptional complexity of Watson-Crick automata
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- On the computational complexity of problems related to distinguishability sets
- Undecidability of state complexity
- Limited automata and regular languages
- State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
- On some decision problems for stateless deterministic ordered restarting automata
- Constant-space, constant-randomness verifiers with arbitrarily small error
- Complexity in union-free regular languages
- Nondeterministic state complexity of proportional removals
- Quasi-distances and weighted finite automata
- Parametric runtime verification is NP-complete and coNP-complete
- Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
- Title not available (Why is that?)
- Title not available (Why is that?)
- Branching measures and nearly acyclic NFAs
- State complexity of suffix distance
- Worst Case Branching and Other Measures of Nondeterminism
- Minimal and hyper-minimal biautomata
- Cellular automata: descriptional complexity and decidability
- Descriptional complexity of finite automata -- selected highlights
- Absent Subsequences in Words
- Transducing reversibly with finite state machines
- Decision problems for subregular classes
- On the complexity of decision problems for parameterized finite state synchronous transducers
- Consensus string problem for multiple regular languages
- Converting finite width AFAs to nondeterministic and universal finite automata
This page was built for publication: Descriptional and computational complexity of finite automata -- a survey
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q553312)
