Closure and Decision Properties for Higher-Dimensional Automata
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866910532452220928 |
|---|---|
| author | Amrane, Amazigh Bazille, Hugo Fahrenberg, Uli Ziemiański, Krzysztof |
| author_facet | Amrane, Amazigh Bazille, Hugo Fahrenberg, Uli Ziemiański, Krzysztof |
| contents | We report some further developments regarding the language theory of higher-dimensional automata (HDAs). Regular languages of HDAs are sets of finite interval partially ordered multisets (pomsets) with interfaces. We show a pumping lemma which allows us to expose a class of non-regular languages. Concerning decision and closure properties, we show that inclusion of regular languages is decidable (hence is emptiness), and that intersections of regular languages are again regular. On the other hand, complements of regular languages are not always regular. We introduce a width-bounded complement and show that width-bounded complements of regular languages are again regular.
We also study determinism and ambiguity. We show that it is decidable whether a regular language is accepted by a deterministic HDA and that there exists regular languages with unbounded ambiguity. Finally, we characterize one-letter deterministic languages in terms of utlimately periodic functions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2305_02873 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Closure and Decision Properties for Higher-Dimensional Automata Amrane, Amazigh Bazille, Hugo Fahrenberg, Uli Ziemiański, Krzysztof Formal Languages and Automata Theory We report some further developments regarding the language theory of higher-dimensional automata (HDAs). Regular languages of HDAs are sets of finite interval partially ordered multisets (pomsets) with interfaces. We show a pumping lemma which allows us to expose a class of non-regular languages. Concerning decision and closure properties, we show that inclusion of regular languages is decidable (hence is emptiness), and that intersections of regular languages are again regular. On the other hand, complements of regular languages are not always regular. We introduce a width-bounded complement and show that width-bounded complements of regular languages are again regular. We also study determinism and ambiguity. We show that it is decidable whether a regular language is accepted by a deterministic HDA and that there exists regular languages with unbounded ambiguity. Finally, we characterize one-letter deterministic languages in terms of utlimately periodic functions. |
| title | Closure and Decision Properties for Higher-Dimensional Automata |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2305.02873 |