Descriptional and Computational Complexity of Finite Automata
From MaRDI portal
Recommendations
- Descriptional and computational complexity of finite automata -- a survey
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Minimal NFA Problems are Hard
- scientific article; zbMATH DE number 176769
Cites work
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- \(NC^ 1\): The automata-theoretic viewpoint
- A note on the space complexity of some decision problems for finite automata
- A very hard log-space counting class
- Alternation
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Classification of finite monoids: the language approach
- Complexity of automaton identification from given data
- Complexity of some problems from the theory of automata
- Computational Parallels between the Regular and Context-Free Languages
- Constructions for alternating finite automata∗
- Detecting palindromes, patterns and borders in regular languages
- Dot-depth of star-free events
- Finding Lower Bounds for Nondeterministic State Complexity Is Hard
- Finite automata and unary languages
- Finite monoids and the fine structure of NC 1
- Finite-automaton aperiodicity is PSPACE-complete
- Follow automata.
- Hierarchies of complete problems
- scientific article; zbMATH DE number 3978429 (Why is no real title available?)
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 3471606 (Why is no real title available?)
- scientific article; zbMATH DE number 3511563 (Why is no real title available?)
- scientific article; zbMATH DE number 3560737 (Why is no real title available?)
- scientific article; zbMATH DE number 3561239 (Why is no real title available?)
- scientific article; zbMATH DE number 3557270 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1962776 (Why is no real title available?)
- scientific article; zbMATH DE number 1747444 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Lower bounds on the size of sweeping automata
- Mathematical Foundations of Computer Science 2003
- Minimal NFA Problems are Hard
- Minimizing finite automata is computationally hard
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Nondeterministic Space is Closed under Complementation
- Observations on the complexity of regular expression problems
- On emptiness and counting for alternating finite automata
- On equations for regular languages, finite automata, and sequential networks
- On Equivalence and Containment Problems for Formal Languages
- On finite monoids having only trivial subgroups
- On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- On the equivalence, containment, and covering problems for the regular and context-free languages
- On uniformity within \(NC^ 1\)
- Optimal simulations between unary automata
- Parity, circuits, and the polynomial-time hierarchy
- Space-bounded reducibility among combinatorial problems
- STACS 2005
- State complexity of regular languages
- Succinct representation of regular languages by Boolean automata
- Succinct representation of regular languages by Boolean automata. II
- The method of forced enumeration for nondeterministic automata
- The parallel complexity of finite-state automata problems
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- The Tractability Frontier for NFA Minimization
Cited in
(22)- Computational complexity of decision problems on self-verifying finite automata
- On the descriptional complexity of finite automata with modified acceptance conditions
- Exact complexity of problems of incompletely specified automata
- Alternation in two-way finite automata
- Minicomplexity. Some motivation, some history, and some structure (invited talk extended abstract)
- The complexity of compressed membership problems for finite automata
- On the descriptional complexity of Watson-Crick automata
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- scientific article; zbMATH DE number 2125663 (Why is no real title available?)
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- scientific article; zbMATH DE number 5309918 (Why is no real title available?)
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Computability by finite automata and pisot bases
- scientific article; zbMATH DE number 2068876 (Why is no real title available?)
- scientific article; zbMATH DE number 1502109 (Why is no real title available?)
- Incomplete operational transition complexity of regular languages
- State trade-offs in unranked tree automata
- Transition function complexity of finite automata
- STACS 2004
- Descriptional complexity of machines with limited resources
- Descriptional and computational complexity of finite automata -- a survey
- Limitations of lower bound methods for deterministic nested word automata
This page was built for publication: Descriptional and Computational Complexity of Finite Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3618565)
