Scholarlink

<p>Maximal existential width and maximal universal width provide methods of quantifying the amount of nondeterminism and parallelism, respectively, present in computations of an alternating finite automaton (AFA). In this paper, we primarily seek to understand the complexity landscape of the problems pertaining to computing these widths. One such problem involves deciding whether the maximal universal width or maximal existential width of an AFA is bounded by a given integer <i>k</i>. For the case of a nondeterministic finite automaton (NFA), we give a polynomial time algorithm for computing maximal existential width. We also present a polynomial time algorithm for computing the existential width of a general AFA, under the assumption that the AFA’s universal width is bounded by a fixed integer <InlineEquation ID="IEq1"> <EquationSource Format="TEX">\(\ell\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>ℓ</mi> </math></EquationSource> </InlineEquation>. Finally, we reconsider the problems of computing existential and universal widths for AFAs over a unary language and demonstrate that both problems can be solved in polynomial time.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Algorithms for maximal existential and universal width

  • 期刊论文

  • 发表日期：

    2025年6月10日

查看全文
  • John Alajaji,
  • Kai Salomaa

摘要

Maximal existential width and maximal universal width provide methods of quantifying the amount of nondeterminism and parallelism, respectively, present in computations of an alternating finite automaton (AFA). In this paper, we primarily seek to understand the complexity landscape of the problems pertaining to computing these widths. One such problem involves deciding whether the maximal universal width or maximal existential width of an AFA is bounded by a given integer k. For the case of a nondeterministic finite automaton (NFA), we give a polynomial time algorithm for computing maximal existential width. We also present a polynomial time algorithm for computing the existential width of a general AFA, under the assumption that the AFA’s universal width is bounded by a fixed integer \(\ell\) ℓ . Finally, we reconsider the problems of computing existential and universal widths for AFAs over a unary language and demonstrate that both problems can be solved in polynomial time.