Algorithms for maximal existential and universal width

The article explores the computational efficiency of alternating finite automata (AFAs), which utilize both nondeterminism and parallelism to describe regular languages. AFAs can achieve significant state complexity savings compared to nondeterministic finite automata (NFAs) and deterministic finite automata (DFAs), making them highly effective for representing regular languages. The text introduces measures of existential and universal width to quantify the nondeterminism and parallelism in AFA computations, focusing on worst-case scenarios to demonstrate the efficiency of these automata. The article presents algorithms for computing maximal existential and universal width, providing a detailed analysis of their computational complexity and efficiency. Additionally, it discusses the decision problems related to these width measures, offering insights into the challenges and potential solutions for determining the bounds of AFA computations. The study also considers the unary language case, where the algorithms for computing maximal existential and universal width are shown to be more efficient, highlighting the differences between unary and non-unary cases. The conclusions draw attention to the open problems and future research directions in the field of AFA computations, emphasizing the need for further exploration of the finiteness of width measures and the decision problems associated with them.