Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation

DOI10.1137/0218083zbMATH Open0692.68049OpenAlexW1975246937MaRDI QIDQ3034835FDOQ3034835

B. Ravikumar, Oscar H. Ibarra

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

zbMATH Keywords

ambiguitynondeterministic finite automatonsuccinctness of representation

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cited In (37)

• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Left is Better Than Right for Reducing Nondeterminism of NFAs
• Ambiguity and communication
• Characterizing regular languages with polynomial densities
• GENERAL ALGORITHMS FOR TESTING THE AMBIGUITY OF FINITE AUTOMATA AND THE DOUBLE-TAPE AMBIGUITY OF FINITE-STATE TRANSDUCERS
• Operations on Unambiguous Finite Automata
• Unambiguous finite automata over a unary alphabet
• Transforming a single-valued transducer into a Mealy machine
• On the degree of ambiguity of finite automata
• Some results on the structure of unary unambiguous automata
• Polynomially ambiguous unary weighted automata over fields
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Ambiguity and structural ambiguity of symmetric difference NFAs
• An approximation algorithm for state minimization in 2-MDFAs
• Investigations on Automata and Languages Over a Unary Alphabet
• The state complexities of some basic operations on regular languages
• Worst Case Branching and Other Measures of Nondeterminism
• Ambiguity of Unary Symmetric Difference NFAs
• Nondeterministic Tree Width of Regular Languages
• Descriptional complexity of unambiguous input-driven pushdown automata
• Operations on Unambiguous Finite Automata
• Descriptional complexity of finite automata -- selected highlights
• Communication complexity method for measuring nondeterminism in finite automata
• Markov chains and unambiguous automata
• State complexity of unique rational operations
• Structural properties of NFAs and growth rates of nondeterminism measures
• In memoriam Chandra Kintala
• On the transformation of two-way deterministic finite automata to unambiguous finite automata
• Concise representations of regular languages by degree and probabilistic finite automata
• Two-way unary automata versus logarithmic space
• Pairs of complementary unary languages with ``balanced nondeterministic automata
• From finite automata to regular expressions and back -- a summary on descriptional complexity
• Existential and universal width of alternating finite automata
• Descriptional complexity of regular languages
• Branching Measures and Nearly Acyclic NFAs
• On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
• Converting finite width AFAs to nondeterministic and universal finite automata

Recommendations

• On the relation between ambiguity and nondeterminism in finite automata 👍 👎
• On the degree of ambiguity of finite automata 👍 👎
• On the finite degree of ambiguity of finite tree automata 👍 👎
• Succinct representations for (non)deterministic finite automata 👍 👎
• Ambiguity, Nondeterminism and State Complexity of Finite Automata 👍 👎
• Succinct representation for (non)deterministic finite automata 👍 👎
• Representations of finite automata 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎

This page was built for publication: Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3034835)