2025/03/10 by Passemard, Luc, Amrane, Amazigh, Fahrenberg, Uli · 1 citation
#FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2503.07881
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.