Scholarlink

In Chapter 3 we introduced alternating automata as an extension of nondeterministic finite automata operating on finite words. They turned out not to be more expressive than NFA but generally more succinct, i.e. there are languages that can be recognized by AFA which are exponentially smaller than the smallest equivalent NFA.

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

Alternating Büchi Automata

  • 章节

  • 发表日期：

    2025年

查看全文
  • Martin Hofmann,
  • Martin Lange

摘要

In Chapter 3 we introduced alternating automata as an extension of nondeterministic finite automata operating on finite words. They turned out not to be more expressive than NFA but generally more succinct, i.e. there are languages that can be recognized by AFA which are exponentially smaller than the smallest equivalent NFA.