State-complexity of finite-state devices, state compressibility and incompressibility
From MaRDI portal
Publication:5289271
DOI10.1007/BF01371727zbMath0779.68061OpenAlexW2091815190WikidataQ57380755 ScholiaQ57380755MaRDI QIDQ5289271
Publication date: 22 August 1993
Published in: Mathematical Systems Theory (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/bf01371727
Related Items
Deciding unifiability and computing local unifiers in the description logic \(\mathcal{EL}\) without top constructor ⋮ Complexity results for two-way and multi-pebble automata and their logics ⋮ State succinctness of two-way finite automata with quantum and classical states ⋮ From Two-Way to One-Way Finite Automata—Three Regular Expression-Based Methods ⋮ Complexity of multi-head finite automata: origins and directions ⋮ STATE COMPLEXITY OF TWO COMBINED OPERATIONS: CATENATION-UNION AND CATENATION-INTERSECTION ⋮ On the complexity of decision problems for some classes of machines and applications ⋮ From bidirectionality to alternation. ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ On the descriptional complexity of stateless deterministic ordered restarting automata ⋮ OPTIMAL SIMULATIONS OF WEAK RESTARTING AUTOMATA ⋮ Two-way automata and length-preserving homomorphisms ⋮ Adding pebbles to weighted automata: easy specification \& efficient evaluation ⋮ Distributed Timed Automata with Independently Evolving Clocks ⋮ NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES ⋮ Complexity results for multi-pebble automata and their logics ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ A note on the space complexity of some decision problems for finite automata ⋮ THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS ⋮ Succinct description of regular languages by weak restarting automata ⋮ On the state complexity of operations on two-way finite automata ⋮ Partial orders on words, minimal elements of regular languages, and state complexity ⋮ LIMITED AUTOMATA AND REGULAR LANGUAGES ⋮ On the descriptional power of heads, counters, and pebbles ⋮ Two-way unary automata versus logarithmic space ⋮ Unnamed Item ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Alternation in two-way finite automata ⋮ STATE COMPLEXITY AND THE MONOID OF TRANSFORMATIONS OF A FINITE SET ⋮ Unnamed Item ⋮ Size Complexity of Two-Way Finite Automata ⋮ NONDETERMINISTIC FINITE AUTOMATA — RECENT RESULTS ON THE DESCRIPTIONAL AND COMPUTATIONAL COMPLEXITY ⋮ Descriptional complexity of regular languages ⋮ Evaluating Datalog via tree automata and cycluits
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- On equations for regular languages, finite automata, and sequential networks
- Partial orders on words, minimal elements of regular languages, and state complexity
- On classes of tractable unrestricted regular expressions
- Succinct representation of regular languages by Boolean automata. II
- Finite automata and unary languages
- Concatenation of inputs in a two-way automaton
- A note on the reduction of two-way automata to one-way automata
- Halting space-bounded computations
- Succinct representation of regular languages by Boolean automata
- Intersection and union of regular languages and state complexity
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- Optimization of LR(k) parsers
- Alternating Pushdown and Stack Automata
- STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
- Alternation
- Two-way automata and length-preserving homomorphisms
- Nondeterminism and the size of two way finite automata
- Quasi-realtime languages
- One-tape, off-line Turing machine computations
