Descriptional and Computational Complexity of Finite Automata
From MaRDI portal
Publication:3618565
DOI10.1007/978-3-642-00982-2_3zbMATH Open1234.68211OpenAlexW1890357466MaRDI QIDQ3618565FDOQ3618565
Authors: Markus Holzer, Martin Kutrib 
Publication date: 2 April 2009
Published in: Language and Automata Theory and Applications (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-642-00982-2_3
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- \(\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
- 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 Tractability Frontier for NFA Minimization
- Finite automata and unary languages
- Title not available (Why is that?)
- A very hard log-space counting class
- 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
- Title not available (Why is that?)
- Lower bounds on the size of sweeping automata
- 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
- 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?)
- 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?)
- 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
- 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
- Mathematical Foundations of Computer Science 2003
- On emptiness and counting for alternating finite automata
- STACS 2005
- \(NC^ 1\): The automata-theoretic viewpoint
Cited In (21)
- Computability by finite automata and pisot bases
- Descriptional complexity of machines with limited resources
- Title not available (Why is that?)
- Computational complexity of decision problems on self-verifying finite automata
- Exact complexity of problems of incompletely specified automata
- Transition function complexity of finite automata
- On the descriptional complexity of finite automata with modified acceptance conditions
- Alternation in two-way finite automata
- STACS 2004
- State trade-offs in unranked tree automata
- The complexity of compressed membership problems for finite automata
- Title not available (Why is that?)
- Descriptional Complexity of Operations on Alternating and Boolean Automata
- Limitations of lower bound methods for deterministic nested word automata
- Descriptional and computational complexity of finite automata -- a survey
- Title not available (Why is that?)
- Incomplete operational transition complexity of regular languages
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- On the descriptional complexity of Watson-Crick automata
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- Minicomplexity. Some motivation, some history, and some structure (invited talk extended abstract)
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)
