Existential and universal width of alternating finite automata

DOI10.1007/978-3-031-34326-1_4MaRDI QIDQ6175087zbMATH OpenFDO

Authors Yo-Sub Han, Sung-Min Kim, Sang-Ki Ko, Kai Salomaa

Publication date 17 August 2023

Published in Descriptional Complexity of Formal Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-031-34326-1_4

zbMATH Keywords

alternating finite automatondecidabilitymeasure of nondeterminismspace complexityuniversal and existential choices

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A Second Course in Formal Languages and Automata Theory
• Alternating finite automata with limited universal branching
• Alternation
• Alternation in two-way finite automata
• Ambiguity and communication
• Ambiguity, nondeterminism and state complexity of finite automata
• An alternating hierarchy for finite automata
• Combining limited parallelism and nondeterminism in alternating finite automata
• Communication complexity method for measuring nondeterminism in finite automata
• Constructions for alternating finite automata^∗
• Deciding path size of nondeterministic (and input-driven) pushdown automata
• Descriptional and computational complexity of finite automata -- a survey
• Descriptional complexity of machines with limited resources
• scientific article; zbMATH DE number 5595162 (Why is no real title available?)
• Limitedness theorem on finite automata with distance functions
• Limitedness theorem on finite automata with distance functions: An algebraic proof
• On finite automata with limited nondeterminism
• On measuring nondeterminism in regular languages
• On the degree of ambiguity of finite automata
• On the power of alternation in automata theory
• 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
• Succinct representation of regular languages by Boolean automata
• The limitedness problem on distance automata: Hashiguchi's method revisited
• Width measures of alternating finite automata
• Worst Case Branching and Other Measures of Nondeterminism

Cited in

(3)

• VC-dimensions of finite automata and commutative finite automata with \(k\) letters and \(n\) states
• Converting finite width AFAs to nondeterministic and universal finite automata
• Maximal universal width of an AFA is NP-hard

This page was built for publication: Existential and universal width of alternating finite automata

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