On the Bounds for State-Set Size in the Proofs of Equivalence Between Deterministic, Nondeterministic, and Two-Way Finite Automata
From MaRDI portal
Publication:5638224
DOI10.1109/T-C.1971.223108zbMath0229.94033OpenAlexW2149288970WikidataQ56474704 ScholiaQ56474704MaRDI QIDQ5638224
Publication date: 1971
Published in: IEEE Transactions on Computers (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1109/t-c.1971.223108
Related Items
Complementing two-way finite automata ⋮ On the Determinization Blowup for Finite Automata Recognizing Equal-Length Languages ⋮ Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata ⋮ Succinctness of descriptions of SBTA-languages ⋮ Complexity of multi-head finite automata: origins and directions ⋮ Empirical studies in the size of diagnosers and verifiers for diagnosability analysis ⋮ State complexity of inversion operations ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ A family of NFAs which need 2\(^{n}-\alpha\) deterministic states ⋮ Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification ⋮ Complexity of exclusive nondeterministic finite automata ⋮ Pairs of complementary unary languages with ``balanced nondeterministic automata ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ Binary coded unary regular languages ⋮ On the Size of Two-Way Reasonable Automata for the Liveness Problem ⋮ Nondeterministic state complexity of star-free languages ⋮ An alternating hierarchy for finite automata ⋮ State Complexity of Regular Tree Languages for Tree Matching ⋮ On a structural property in the state complexity of projected regular languages ⋮ An \(n\log n\) algorithm for hyper-minimizing a (minimized) deterministic automaton ⋮ On the State Complexity of Operations on Two-Way Finite Automata ⋮ Descriptional Complexity of the Forever Operator ⋮ Ambiguity and structural ambiguity of symmetric difference NFAs ⋮ Translation from classical two-way automata to pebble two-way automata ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ Magic numbers in the state hierarchy of finite automata ⋮ IN SEARCH OF MOST COMPLEX REGULAR LANGUAGES ⋮ On the state complexity of operations on two-way finite automata ⋮ UNARY LANGUAGE OPERATIONS, STATE COMPLEXITY AND JACOBSTHAL'S FUNCTION ⋮ Oblivious two-way finite automata: decidability and complexity ⋮ NONDETERMINISTIC STATE COMPLEXITY OF PROPORTIONAL REMOVALS ⋮ On the descriptional complexity of finite automata with modified acceptance conditions ⋮ State complexity of some operations on binary regular languages ⋮ Complementing unary nondeterministic automata ⋮ An upper bound for transforming self-verifying automata into deterministic ones ⋮ Descriptional and computational complexity of finite automata -- a survey ⋮ Optimal simulation of self-verifying automata by deterministic automata ⋮ Determination of finite automata accepting subregular languages ⋮ Lower bounds for the size of deterministic unranked tree automata ⋮ Algorithms for finding directed graph isomorphisms by finite automata ⋮ Nondeterministic Finite Automata—Recent Results on the Descriptional and Computational Complexity ⋮ Bounds on the index and period of a binary relation on a finite set ⋮ Regular languages of partial words ⋮ Nondeterministic State Complexity of Star-Free Languages ⋮ State Complexity of Projected Languages ⋮ State Trade-Offs in Unranked Tree Automata ⋮ State complexity of deletion and bipolar deletion ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ One-Time Nondeterministic Computations ⋮ Reset Complexity of Ideal Languages Over a Binary Alphabet ⋮ Descriptional and Computational Complexity of Finite Automata ⋮ Converting Self-verifying Automata into Deterministic Automata ⋮ Better Hyper-minimization ⋮ Equivalence problem of non-deterministic finite automata ⋮ Transforming a single-valued transducer into a Mealy machine ⋮ An nlogn Algorithm for Hyper-minimizing States in a (Minimized) Deterministic Automaton ⋮ Self-Verifying Finite Automata and Descriptional Complexity ⋮ Tight bounds on the number of states of DFAs that are equivalent to \(n\)-state NFAs ⋮ On NFAs where all states are final, initial, or both ⋮ Ambiguity of Unary Symmetric Difference NFAs ⋮ Descriptional complexity of regular languages ⋮ DETERMINISM VS. NONDETERMINISM FOR TWO-WAY AUTOMATA: Representing the Meaning of States by Logical Formulæ ⋮ Unambiguity in Automata Theory ⋮ The State Complexity of Permutations on Finite Languages over Binary Alphabets ⋮ Deterministic blow-ups of minimal NFA's ⋮ Note on the complexity of Las Vegas automata problems ⋮ Deterministic one-way simulation of two-way deterministic finite automata over small alphabets ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Tight lower bounds on the size of sweeping automata ⋮ Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata ⋮ More on deterministic and nondeterministic finite cover automata
