State-complexity of finite-state devices, state compressibility and incompressibility
From MaRDI portal
Publication:5289271
DOI10.1007/BF01371727zbMATH Open0779.68061OpenAlexW2091815190WikidataQ57380755 ScholiaQ57380755MaRDI QIDQ5289271FDOQ5289271
Authors: J.-C. Birget 
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
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
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Alternation
- Quasi-realtime languages
- Halting space-bounded computations
- Optimization of LR(k) parsers
- Title not available (Why is that?)
- Finite automata and unary languages
- Title not available (Why is that?)
- On classes of tractable unrestricted regular expressions
- On equations for regular languages, finite automata, and sequential networks
- A note on the reduction of two-way automata to one-way automata
- Intersection and union of regular languages and state complexity
- Nondeterminism and the size of two way finite automata
- Partial orders on words, minimal elements of regular languages, and state complexity
- Succinct representation of regular languages by Boolean automata
- One-tape, off-line Turing machine computations
- Alternating Pushdown and Stack Automata
- Succinct representation of regular languages by Boolean automata. II
- Concatenation of inputs in a two-way automaton
- Two-way automata and length-preserving homomorphisms
- Positional simulation of two-way automata: Proof of a conjecture of R. Kannan and generalizations
- STRICT LOCAL TESTABILITY OF THE FINITE CONTROL OF TWO-WAY AUTOMATA AND OF REGULAR PICTURE DESCRIPTION LANGUAGES
- Title not available (Why is that?)
Cited In (34)
- 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
- Title not available (Why is that?)
- 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
- Complexity results for two-way and multi-pebble automata and their logics
- Two-way unary automata versus logarithmic space
- Title not available (Why is that?)
- 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
- Size Complexity of Two-Way Finite Automata
- On the descriptional complexity of stateless deterministic ordered restarting automata
- THE PHENOMENON OF NON-RECURSIVE TRADE-OFFS
- Adding pebbles to weighted automata: easy specification \& efficient evaluation
- 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
- Complexity results for multi-pebble automata and their logics
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)
