Descriptional and computational complexity of finite automata -- a survey
From MaRDI portal
Publication:553312
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
Cites work
- scientific article; zbMATH DE number 3978429 (Why is no real title available?)
- scientific article; zbMATH DE number 3744551 (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 3569855 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 1011685 (Why is no real title available?)
- scientific article; zbMATH DE number 2081039 (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 3311755 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- A lower bound technique for the size of nondeterministic finite automata
- A note on the space complexity of some decision problems for finite automata
- A note on undecidable properties of formal languages
- A very hard log-space counting class
- Alternation
- Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\)
- Classes of languages and linear-bounded automata
- 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∗
- Decision Problems for Convex Languages
- 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
- Inapproximability of Nondeterministic State and Transition Complexity Assuming P ≠ NP
- Intersection and union of regular languages and state complexity
- 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 DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- 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 Equivalence and Containment Problems for Formal Languages
- On NFAs where all states are final, initial, or both
- On counting and approximation
- On emptiness and counting for alternating finite automata
- On equations for regular languages, finite automata, and sequential networks
- 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 Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- On the equivalence, containment, and covering problems for the regular and context-free languages
- On uniformity within \(NC^ 1\)
- Optimal simulations between unary automata
- Parallel complexity of iterated morphisms and the arithmetic of small numbers
- Parity, circuits, and the polynomial-time hierarchy
- STACS 2005
- Space-bounded reducibility among combinatorial problems
- State complexity of regular languages
- Succinct representation of regular languages by Boolean automata
- Succinct representation of regular languages by Boolean automata. II
- THE STRUCTURE AND COMPLEXITY OF MINIMAL NFA’S OVER A UNARY ALPHABET
- The Tractability Frontier for NFA Minimization
- The complexity of computing the permanent
- The emptiness problem for intersections of regular languages
- The method of forced enumeration for nondeterministic automata
- The parallel complexity of finite-state automata problems
- \(NC^ 1\): The automata-theoretic viewpoint
- \(\Sigma_ 1^ 1\)-formulae on finite structures
Cited in
(76)- Quasi-distances and weighted finite automata
- Consensus string problem for multiple regular languages
- Converting finite width AFAs to nondeterministic and universal finite automata
- Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers*
- scientific article; zbMATH DE number 7559442 (Why is no real title available?)
- A hitchhiker's guide to descriptional complexity through analytic combinatorics
- The complexity of intersecting finite automata having few final states
- Comparing the notions of opacity for discrete-event systems
- The state complexity of permutations on finite languages over binary alphabets
- scientific article; zbMATH DE number 2068876 (Why is no real title available?)
- Descriptional complexity -- an introductory survey
- scientific article; zbMATH DE number 7584602 (Why is no real title available?)
- State complexity of the concatenation of regular tree languages
- On the expressive power of stateless ordered restart-delete automata
- State complexity of permutation on finite languages over a binary alphabet
- State complexity bounds for the commutative closure of group languages
- 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
- Complexity of universality and related problems for partially ordered NFAs
- State complexity of deletion and bipolar deletion
- Branching measures and nearly acyclic NFAs
- State complexity of suffix distance
- Worst Case Branching and Other Measures of Nondeterminism
- Nondeterministic state complexity of star-free languages
- Descriptional complexity of unambiguous input-driven pushdown automata
- Nondeterministic state complexity of star-free languages
- Alternation in two-way finite automata
- Descriptive set theoretic methods in automata theory. Decidability and topological complexity
- The intersection problem for finite monoids
- Minimal and hyper-minimal biautomata
- STACS 2004
- State complexity of prefix distance of subregular languages
- Cellular automata: descriptional complexity and decidability
- State complexity of Kleene-star operations on trees
- Descriptional and Computational Complexity of Finite Automata
- Descriptional complexity of finite automata -- selected highlights
- Problems on finite automata and the exponential time hypothesis
- Consensus string problem for multiple regular languages
- Problems on finite automata and the exponential time hypothesis
- Checking whether an automaton is monotonic is NP-complete
- Absent Subsequences in Words
- 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
- Transducing reversibly with finite state machines
- Complexity of exclusive nondeterministic finite automata
- scientific article; zbMATH DE number 7699973 (Why is no real title available?)
- Descriptional complexity of input-driven pushdown automata
- A multi-parameter analysis of hard problems on deterministic finite automata
- Scattered Factor-Universality of Words
- From finite automata to regular expressions and back -- a summary on descriptional complexity
- On linear languages recognized by deterministic biautomata
- Automata Presenting Structures: A Survey of the Finite String Case
- Existential and universal width of alternating finite automata
- Distributed graph problems through an automata-theoretic lens
- Walking on data words
- Complexity of suffix-free 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
- On the computational complexity of problems related to distinguishability sets
- Decision problems for subregular classes
- On the complexity of decision problems for parameterized finite state synchronous transducers
- Undecidability of state complexity
- Constant-space, constant-randomness verifiers with arbitrarily small error
- 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
- Complexity in union-free regular languages
- Nondeterministic state complexity of proportional removals
- Parametric runtime verification is NP-complete and coNP-complete
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)
