Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2501.15192 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914527865470976 |
|---|---|
| author | Staiger, Ludwig |
| author_facet | Staiger, Ludwig |
| contents | A subset of a topological space possesses the Baire property if it can be
covered by an open set up to a meagre set. For the Cantor space of infinite
words Finkel introduced the automatic Baire category where both sets, the
open and the meagre, can be chosen to be definable by finite automata. Here
we show that, given a Muller automaton defining the original set, resulting
open and meagre sets can be constructed in polynomial time.
Since the constructed sets are of simple topological structure, it is
possible to construct not only Muller automata defining them but also the
simpler Büchi automata. To this end we give, for a restricted class of
Muller automata, a conversion to equivalent Büchi automata of at most
quadratic size. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_15192 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A polynomial-time algorithm for the automatic Baire property Staiger, Ludwig Formal Languages and Automata Theory 68Q45, F.4 A subset of a topological space possesses the Baire property if it can be covered by an open set up to a meagre set. For the Cantor space of infinite words Finkel introduced the automatic Baire category where both sets, the open and the meagre, can be chosen to be definable by finite automata. Here we show that, given a Muller automaton defining the original set, resulting open and meagre sets can be constructed in polynomial time. Since the constructed sets are of simple topological structure, it is possible to construct not only Muller automata defining them but also the simpler Büchi automata. To this end we give, for a restricted class of Muller automata, a conversion to equivalent Büchi automata of at most quadratic size. |
| title | A polynomial-time algorithm for the automatic Baire property |
| topic | Formal Languages and Automata Theory 68Q45, F.4 |
| url | https://arxiv.org/abs/2501.15192 |