Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
From MaRDI portal
Publication:3034835
DOI10.1137/0218083zbMath0692.68049OpenAlexW1975246937MaRDI QIDQ3034835
Oscar H. Ibarra, Bala Ravikumar
Publication date: 1989
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0218083
Related Items
IN MEMORIAM CHANDRA KINTALA, An approximation algorithm for state minimization in 2-MDFAs, Characterizing regular languages with polynomial densities, Polynomially ambiguous unary weighted automata over fields, Markov chains and unambiguous automata, Left is Better Than Right for Reducing Nondeterminism of NFAs, Converting finite width AFAs to nondeterministic and universal finite automata, Unambiguous finite automata over a unary alphabet, Existential and universal width of alternating finite automata, Pairs of complementary unary languages with ``balanced nondeterministic automata, On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes, Ambiguity and structural ambiguity of symmetric difference NFAs, Operations on Unambiguous Finite Automata, On the degree of ambiguity of finite automata, Descriptional complexity of unambiguous input-driven pushdown automata, On the transformation of two-way deterministic finite automata to unambiguous finite automata, DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY, GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS, Ambiguity and communication, Some results on the structure of unary unambiguous automata, Two-way unary automata versus logarithmic space, Investigations on Automata and Languages Over a Unary Alphabet, From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity, Branching Measures and Nearly Acyclic NFAs, Operations on Unambiguous Finite Automata, State complexity of unique rational operations, Transforming a single-valued transducer into a Mealy machine, Ambiguity of Unary Symmetric Difference NFAs, Descriptional complexity of regular languages, Nondeterministic Tree Width of Regular Languages, Deciding path size of nondeterministic (and input-driven) pushdown automata, Communication complexity method for measuring nondeterminism in finite automata, Concise representations of regular languages by degree and probabilistic finite automata, The state complexities of some basic operations on regular languages, Worst Case Branching and Other Measures of Nondeterminism, Structural properties of NFAs and growth rates of nondeterminism measures
