Generalised Quantifiers Based on Rabin-Mostowski Index
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866918277933957120 |
|---|---|
| author | Kuperberg, Denis Niwiński, Damian Parys, Paweł Skrzypczak, Michał |
| author_facet | Kuperberg, Denis Niwiński, Damian Parys, Paweł Skrzypczak, Michał |
| contents | In this work we introduce new generalised quantifiers which allow us to express the Rabin-Mostowski index of automata. Our main results study expressive power and decidability of the monadic second-order (MSO) logic extended with these quantifiers. We study these problems in the realm of both $ω$-words and infinite trees. As it turns out, the pictures in these two cases are very different. In the case of $ω$-words the new quantifiers can be effectively expressed in pure MSO logic. In contrast, in the case of infinite trees, addition of these quantifiers leads to an undecidable formalism.
To realise index-quantifier elimination, we consider the extension of MSO by game quantifiers. As a tool, we provide a specific quantifier-elimination procedure for them. Moreover, we introduce a novel construction of transducers realising strategies in $ω$-regular games with monadic parameters. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_04739 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Generalised Quantifiers Based on Rabin-Mostowski Index Kuperberg, Denis Niwiński, Damian Parys, Paweł Skrzypczak, Michał Logic in Computer Science Formal Languages and Automata Theory In this work we introduce new generalised quantifiers which allow us to express the Rabin-Mostowski index of automata. Our main results study expressive power and decidability of the monadic second-order (MSO) logic extended with these quantifiers. We study these problems in the realm of both $ω$-words and infinite trees. As it turns out, the pictures in these two cases are very different. In the case of $ω$-words the new quantifiers can be effectively expressed in pure MSO logic. In contrast, in the case of infinite trees, addition of these quantifiers leads to an undecidable formalism. To realise index-quantifier elimination, we consider the extension of MSO by game quantifiers. As a tool, we provide a specific quantifier-elimination procedure for them. Moreover, we introduce a novel construction of transducers realising strategies in $ω$-regular games with monadic parameters. |
| title | Generalised Quantifiers Based on Rabin-Mostowski Index |
| topic | Logic in Computer Science Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2601.04739 |