Descriptional and Computational Complexity of Finite Automata

DOI10.1007/978-3-642-00982-2_3zbMath1234.68211OpenAlexW1890357466MaRDI QIDQ3618565

Martin Kutrib, Markus Holzer

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

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Related Items (4)

Incomplete operational transition complexity of regular languages ⋮ Limitations of lower bound methods for deterministic nested word automata ⋮ Alternation in two-way finite automata ⋮ State Trade-Offs in Unranked Tree Automata

Cites Work

• 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
• On equations for regular languages, finite automata, and sequential networks
• \(NC^ 1\): The automata-theoretic viewpoint
• Minimizing finite automata is computationally hard
• Finite-automaton aperiodicity is PSPACE-complete
• 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
• 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
• 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
• Constructions for alternating finite automata^∗
• The Tractability Frontier for NFA Minimization
• Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
• Finding Lower Bounds for Nondeterministic State Complexity Is Hard
• 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 ¹
• 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
• On finite monoids having only trivial subgroups
• Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
• Mathematical Foundations of Computer Science 2003
• On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
• STACS 2005

This page was built for publication: Descriptional and Computational Complexity of Finite Automata