| ||||
| ||||
![]() Title:A Conway-Universal Automaton for Structurally Adam-Positional Automata Conference:Highlights26 Tags:automaton, positional language and universal automaton Abstract: In the field of automata over infinite words, a long-standing objective has been to define universal automata: an automaton $U_L$, recognizing an $\omega$-regular language $L$, such that any automaton recognizing $L$ (or possibly a sublanguage) admits a morphism towards $U_L$. Some progress has recently been made towards this objective, with the rerailing automata or more particularly the layered automata. We introduce the class of structurally Adam-positional automata. Intuitively, they are automata with an $\omega$-regular set $W$ of accepting paths, that notably satisfy that if two cycles $\rho$, $\rho'$ around a same state are accepting when repeated infinitely often, so is the cycle $\rho\rho'$. Notably, the Streett automata are structurally Adam-positional. We establish that for all prefix-independent languages $L$, there exists a structurally Adam-positional automaton $U_L$ with the following universality property: for all structurally Adam-positional automaton $A$ recognizing some language $L' \subseteq L$, there exists a transition-to-transition morphism from $A$ to $U_L$ that preserves the accepting paths. Notably, $U_L$ is history-deterministic. This is a joint work with Thomas Colcombet. A Conway-Universal Automaton for Structurally Adam-Positional Automata ![]() A Conway-Universal Automaton for Structurally Adam-Positional Automata | ||||
| Copyright © 2002 – 2026 EasyChair |
