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

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 no real title available?)
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 no real title available?)
The state complexities of some basic operations on regular languages
Branching measures and nearly acyclic NFAs
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
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 no real title available?)
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)