Converting finite width AFAs to nondeterministic and universal finite automata

DOI10.1016/J.TCS.2024.114506MaRDI QIDQ6131195zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• Alternating finite automata with limited universal branching
• Maximal existential and universal width
• Transforming Two-Way Alternating Finite Automata to One-Way Nondeterministic Automata
• Descriptional Complexity of Operations on Alternating and Boolean Automata

Cites work

• scientific article; zbMATH DE number 2086220 (Why is no real title available?)
• scientific article; zbMATH DE number 1502109 (Why is no real title available?)
• scientific article; zbMATH DE number 3307592 (Why is no real title available?)
• Alternating Pushdown and Stack Automata
• Alternation
• Alternation in two-way finite automata
• Ambiguity and communication
• An alternating hierarchy for finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• DESCRIPTIONAL COMPLEXITY OF NFA OF DIFFERENT AMBIGUITY
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of machines with limited resources
• Existential and universal width of alternating finite automata
• On finite automata with limited nondeterminism
• On measuring nondeterminism in regular languages
• On the power of alternation in automata theory
• Partial orders on words, minimal elements of regular languages, and state complexity
• Relating the Type of Ambiguity of Finite Automata to the Succinctness of Their Representation
• Separating Exponentially Ambiguous Finite Automata from Polynomially Ambiguous Finite Automata
• State complexity of finite tree width NFAs
• Structural properties of NFAs and growth rates of nondeterminism measures

Cited in

(3)

• Maximal universal width of an AFA is NP-hard
• Maximal existential and universal width
• Existential and universal width of alternating finite automata

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6131195)