State-complexity of finite-state devices, state compressibility and incompressibility
From MaRDI portal
Publication:5289271
Recommendations
- Compression of finite-state automata through failure transitions
- Finite state complexity
- State complexity and limited nondeterminism
- Finite-state complexity and the size of transducers
- State complexity of unambiguous operations on finite automata
- State-size hierarchy for finite-state complexity
- State complexity of finite partial languages
- State complexity of finite partial languages
- scientific article; zbMATH DE number 2182451
- State complexity and approximation
Cites work
- scientific article; zbMATH DE number 3664335 (Why is no real title available?)
- scientific article; zbMATH DE number 8785 (Why is no real title available?)
- scientific article; zbMATH DE number 3497806 (Why is no real title available?)
- scientific article; zbMATH DE number 3254905 (Why is no real title available?)
- scientific article; zbMATH DE number 3254906 (Why is no real title available?)
- scientific article; zbMATH DE number 3368555 (Why is no real title available?)
- A note on the reduction of two-way automata to one-way automata
- Alternating Pushdown and Stack Automata
- Alternation
- Concatenation of inputs in a two-way automaton
- Finite automata and unary languages
- Halting space-bounded computations
- Intersection and union of regular languages and state complexity
- Nondeterminism and the size of two way finite automata
- On classes of tractable unrestricted regular expressions
- On equations for regular languages, finite automata, and sequential networks
- One-tape, off-line Turing machine computations
- Optimization of LR(k) parsers
- Partial orders on words, minimal elements of regular languages, and state complexity
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Quasi-realtime languages
- STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
- Succinct representation of regular languages by Boolean automata
- Succinct representation of regular languages by Boolean automata. II
- Two-way automata and length-preserving homomorphisms
Cited in
(34)- Complexity results for multi-pebble automata and their logics
- State succinctness of two-way finite automata with quantum and classical states
- From bidirectionality to alternation.
- OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA
- From two-way to one-way finite automata -- three regular expression-based methods
- A note on the space complexity of some decision problems for finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- scientific article; zbMATH DE number 7056237 (Why is no real title available?)
- On the complexity of decision problems for some classes of machines and applications
- State complexity of two combined operations: catenation-union and catenation-intersection
- Complexity of multi-head finite automata: origins and directions
- Alternation in two-way finite automata
- On the transformation of two-way finite automata to unambiguous finite automata
- Deciding unifiability and computing local unifiers in the description logic \(\mathcal{EL}\) without top constructor
- On the transformation of two-way deterministic finite automata to unambiguous finite automata
- STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET
- Two-way unary automata versus logarithmic space
- Complexity results for two-way and multi-pebble automata and their logics
- scientific article; zbMATH DE number 7561597 (Why is no real title available?)
- Distributed Timed Automata with Independently Evolving Clocks
- On the descriptional power of heads, counters, and pebbles
- Descriptional complexity of regular languages
- Evaluating Datalog via tree automata and cycluits
- NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY
- Succinct description of regular languages by weak restarting automata
- Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity
- On the descriptional complexity of stateless deterministic ordered restarting automata
- Size Complexity of Two-Way Finite Automata
- Adding pebbles to weighted automata: easy specification \& efficient evaluation
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
- Limited automata and regular languages
- On the state complexity of operations on two-way finite automata
- NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
- Two-way automata and length-preserving homomorphisms
This page was built for publication: State-complexity of finite-state devices, state compressibility and incompressibility
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5289271)
