Automata on linear orderings are a form of finite-state automata introduced by Bruyère and Carton, that generalize the concepts of finite-word, infinite-word, and transfinite-word automata. They recognize words indexed by linear orderings, defined as mappings from the elements of such orderings to a finite alphabet. Some theoretical developments involving automata on linear orderings are hindered by the fact that their definition does not allow epsilon transitions, i.e., transitions with an empty label. In this paper, we define a variant of automata on linear orderings that allows such transitions in their transition relation, and show that this extension does not modify the expressive power of the automata. We motivate the usefulness of epsilon automata on linear orderings by using them for correcting an erroneous construction in the original proof of equivalence between automata on linear orderings and the corresponding notion of regular expressions.

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

Epsilon Automata on Linear Orderings

  • Bernard Boigelot,
  • Thomas Braipson,
  • Tom Clara

摘要

Automata on linear orderings are a form of finite-state automata introduced by Bruyère and Carton, that generalize the concepts of finite-word, infinite-word, and transfinite-word automata. They recognize words indexed by linear orderings, defined as mappings from the elements of such orderings to a finite alphabet. Some theoretical developments involving automata on linear orderings are hindered by the fact that their definition does not allow epsilon transitions, i.e., transitions with an empty label. In this paper, we define a variant of automata on linear orderings that allows such transitions in their transition relation, and show that this extension does not modify the expressive power of the automata. We motivate the usefulness of epsilon automata on linear orderings by using them for correcting an erroneous construction in the original proof of equivalence between automata on linear orderings and the corresponding notion of regular expressions.