Higher-Dimensional Automata : Extension to Infinite Tracks
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912847216246784 |
|---|---|
| author | Passemard, Luc Amrane, Amazigh Fahrenberg, Uli |
| author_facet | Passemard, Luc Amrane, Amazigh Fahrenberg, Uli |
| contents | We introduce higher-dimensional automata for infinite interval ipomsets ($ω$-HDAs). We define key concepts from different points of view, inspired from their finite counterparts. Then we explore languages recognized by $ω$-HDAs under Büchi and Muller semantics. We show that Muller acceptance is more expressive than Büchi acceptance and, in contrast to the finite case, both semantics do not yield languages closed under subsumption. Then, we adapt the original rational operations to deal with $ω$-HDAs and show that while languages of $ω$-HDAs are $ω$-rational, not all $ω$-rational languages can be expressed by $ω$-HDAs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2503_07881 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Higher-Dimensional Automata : Extension to Infinite Tracks Passemard, Luc Amrane, Amazigh Fahrenberg, Uli Formal Languages and Automata Theory We introduce higher-dimensional automata for infinite interval ipomsets ($ω$-HDAs). We define key concepts from different points of view, inspired from their finite counterparts. Then we explore languages recognized by $ω$-HDAs under Büchi and Muller semantics. We show that Muller acceptance is more expressive than Büchi acceptance and, in contrast to the finite case, both semantics do not yield languages closed under subsumption. Then, we adapt the original rational operations to deal with $ω$-HDAs and show that while languages of $ω$-HDAs are $ω$-rational, not all $ω$-rational languages can be expressed by $ω$-HDAs. |
| title | Higher-Dimensional Automata : Extension to Infinite Tracks |
| topic | Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2503.07881 |