Converting finite width AFAs to nondeterministic and universal finite automata

DOI10.1016/j.tcs.2024.114506OpenAlexW4392869357MaRDI QIDQ6131195

Mohammad Zakzok, Kai Salomaa

Publication date: 4 April 2024

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2024.114506

zbMATH Keywords

nondeterminismstate complexityalternating finite automatonexistential and universal width

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An alternating hierarchy for finite automata
• Ambiguity and communication
• Descriptional and computational complexity of finite automata -- a survey
• Partial orders on words, minimal elements of regular languages, and state complexity
• On measuring nondeterminism in regular languages
• On the power of alternation in automata theory
• On finite automata with limited nondeterminism
• Communication complexity method for measuring nondeterminism in finite automata
• Alternation in two-way finite automata
• Structural properties of NFAs and growth rates of nondeterminism measures
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Alternating Pushdown and Stack Automata
• Alternation
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• State Complexity of Finite Tree Width NFAs
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Existential and universal width of alternating finite automata

This page was built for publication: Converting finite width AFAs to nondeterministic and universal finite automata