Operations on Unambiguous Finite Automata

DOI10.1142/S012905411842008XzbMath1403.68115MaRDI QIDQ4683235

Galina Jirásková, Jozef jun. Jirásek, Juraj Šebej

Publication date: 20 September 2018

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

zbMATH Keywords

state complexityregular operationsunambiguous finite automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (6)

On complementing unambiguous automata and graphs with many cliques and cocliques ⋮ Operational complexity: NFA-to-DFA trade-off ⋮ On the transformation of two-way finite automata to unambiguous finite automata ⋮ On the transformation of two-way deterministic finite automata to unambiguous finite automata ⋮ State complexity of unambiguous operations on finite automata ⋮ Image-binary automata

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unambiguous finite automata over a unary alphabet
• Ambiguity and communication
• A lower bound technique for the size of nondeterministic finite automata
• Partial orders on words, minimal elements of regular languages, and state complexity
• Succinct representation of regular languages by Boolean automata
• On the finite-valuedness problem for sequential machines
• On the degree of ambiguity of finite automata
• Intersection and union of regular languages and state complexity
• The state complexities of some basic operations on regular languages
• State complexity of some operations on binary regular languages
• Communication complexity method for measuring nondeterminism in finite automata
• Kleene Star on Unary Regular Languages
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Descriptional Complexity of (Un)ambiguous Finite State Machines and Pushdown Automata
• On the Equivalence and Containment Problems for Unambiguous Regular Expressions, Regular Grammars and Finite Automata
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• Unambiguity in Automata Theory
• NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY

This page was built for publication: Operations on Unambiguous Finite Automata