Maximal universal width of an AFA is NP-hard

DOI10.1016/J.TCS.2025.115280MaRDI QIDQ6975896zbMATH OpenFDO

Authors John Alajaji, Kai Salomaa

Publication date 2 June 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115280

zbMATH Keywords

algorithmic complexityalternating finite automatonexistential widthNP-hardnessuniversal width

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Cites work

• Alternating Pushdown and Stack Automata
• Alternation
• Alternation in two-way finite automata
• Amounts of nondeterminism in finite automata
• An alternating hierarchy for finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Complexity of some problems concerningL systems
• Converting finite width AFAs to nondeterministic and universal finite automata
• Descriptional and computational complexity of finite automata -- a survey
• Existential and universal width of alternating finite automata
• scientific article; zbMATH DE number 3802813 (Why is no real title available?)
• Maximal existential and universal width
• On measuring nondeterminism in regular languages
• On the power of alternation in automata theory
• Recognition of deterministic ETOL languages in logarithmic space
• 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
• The membership question for ETOL-languages is polynomially complete
• The tape-complexity of context-independent developmental languages
• Worst Case Branching and Other Measures of Nondeterminism

Cited in

(1)

• Existential and universal width of alternating finite automata

This page was built for publication: Maximal universal width of an AFA is NP-hard

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