Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
From MaRDI portal
Publication:4210084
DOI10.1137/S0097539793252092zbMath0911.68144OpenAlexW2079577017MaRDI QIDQ4210084
Publication date: 20 September 1998
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/s0097539793252092
Related Items (32)
Unnamed Item ⋮ IN MEMORIAM CHANDRA KINTALA ⋮ More on Deterministic and Nondeterministic Finite Cover Automata ⋮ On the state complexity of closures and interiors of regular languages with subwords and superwords ⋮ Operational state complexity of unary NFAs with finite nondeterminism ⋮ Left is Better Than Right for Reducing Nondeterminism of NFAs ⋮ The size of power automata. ⋮ 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 ⋮ Complexity of exclusive nondeterministic finite automata ⋮ A Burnside Approach to the Termination of Mohri's Algorithm for Polynomially Ambiguous Min-Plus-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 ⋮ Descriptional complexity of unambiguous input-driven pushdown automata ⋮ DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY ⋮ Lower bounds for the transition complexity of NFAs ⋮ Ambiguity and communication ⋮ NONDETERMINISTIC BIAUTOMATA AND THEIR DESCRIPTIONAL COMPLEXITY ⋮ From Finite Automata to Regular Expressions and Back — A Summary on Descriptional Complexity ⋮ Branching Measures and Nearly Acyclic NFAs ⋮ Operations on Unambiguous Finite Automata ⋮ Ambiguity of Unary Symmetric Difference NFAs ⋮ Unambiguity in Automata Theory ⋮ Width measures of alternating finite automata ⋮ Deciding path size of nondeterministic (and input-driven) pushdown automata ⋮ Communication complexity method for measuring nondeterminism in finite automata ⋮ Tight lower bounds on the size of sweeping automata ⋮ Worst Case Branching and Other Measures of Nondeterminism ⋮ Structural properties of NFAs and growth rates of nondeterminism measures ⋮ More on deterministic and nondeterministic finite cover automata
This page was built for publication: Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
