\(\varOmega \) -automata and Wilke algebras are formalisms for characterising \(\omega \) -regular languages via their ultimately periodic words. \(\varOmega \) -automata read finite representations of ultimately periodic words, called lassos, and they are a subclass of lasso automata. We introduce lasso semigroups as a generalisation of Wilke algebras that mirrors how lasso automata generalise \(\varOmega \) -automata, and we show that finite lasso semigroups characterise regular lasso languages. We then show a dual adjunction between lasso automata and quotients of the free lasso semigroup with a recognising set, and as our main result we show that this dual adjunction restricts to one between \(\varOmega \) -automata and quotients of the free Wilke algebra with a recognising set.

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

Dual Adjunction Between \(\varOmega \) -Automata and Wilke Algebra Quotients

  • Anton Chernev,
  • Helle Hvid Hansen,
  • Clemens Kupke

摘要

\(\varOmega \) -automata and Wilke algebras are formalisms for characterising \(\omega \) -regular languages via their ultimately periodic words. \(\varOmega \) -automata read finite representations of ultimately periodic words, called lassos, and they are a subclass of lasso automata. We introduce lasso semigroups as a generalisation of Wilke algebras that mirrors how lasso automata generalise \(\varOmega \) -automata, and we show that finite lasso semigroups characterise regular lasso languages. We then show a dual adjunction between lasso automata and quotients of the free lasso semigroup with a recognising set, and as our main result we show that this dual adjunction restricts to one between \(\varOmega \) -automata and quotients of the free Wilke algebra with a recognising set.