Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
From MaRDI portal
Publication:3034835
DOI10.1137/0218083zbMATH Open0692.68049OpenAlexW1975246937MaRDI QIDQ3034835FDOQ3034835
Authors: Oscar H. Ibarra, B. 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
Recommendations
- scientific article; zbMATH DE number 4049114
- On the degree of ambiguity of finite automata
- scientific article; zbMATH DE number 4001492
- On the relation between ambiguity and nondeterminism in finite automata
- Succinct representations for (non)deterministic finite automata
- Succinct representation for (non)deterministic finite automata
- Ambiguity, nondeterminism and state complexity of finite automata
- scientific article; zbMATH DE number 17556
- On the finite degree of ambiguity of finite tree automata
- Representations of finite automata
Cited In (48)
- Deciding path size of nondeterministic (and input-driven) pushdown automata
- Ambiguity of unary symmetric difference NFAs
- Descriptional complexity of ambiguity in symmetric difference NFAs
- Left is Better Than Right for Reducing Nondeterminism of NFAs
- Ambiguity and communication
- Ambiguity and communication
- Remarks on multiple entry deterministic finite automata
- Characterizing regular languages with polynomial densities
- Title not available (Why is that?)
- Operations on Unambiguous Finite Automata
- Unambiguous finite automata over a unary alphabet
- Comparing verboseness for finite automata and Turing machines
- 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
- Succinct representations of languages by DFA with different levels of reliability
- Title not available (Why is that?)
- The state complexities of some basic operations on regular languages
- Worst Case Branching and Other Measures of Nondeterminism
- Descriptional complexity of unambiguous input-driven pushdown automata
- Succinct descriptions of regular languages with binary \(\oplus\)-NFAs
- 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
- Investigations on automata and languages over a unary alphabet
- 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
- Nondeterministic tree width of regular languages
- 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
- General algorithms for testing the ambiguity of finite automata and the double-tape ambiguity of finite-state transducers
- On the Hardness of Determining Small NFA’s and of Proving Lower Bounds on Their Sizes
- Title not available (Why is that?)
- Structurally Unambiguous Finite Automata
- On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
- Converting finite width AFAs to nondeterministic and universal finite automata
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)
