Languages of higher-dimensional automata
Mathematical Structures in Computer Science · 2021-05 · 31 (5) · 575-613
DOI: 10.1017/s0960129521000293 ↗Kurz gefasst
Fachartikel in der Zeitschrift Mathematical Structures in Computer Science, online erschienen am 18.10.2021. Verfasst von Uli Fahrenberg und 3 weiteren Autor:innen. Die Arbeit wurde bisher 18-mal zitiert (Crossref) und nennt 52 Literaturangaben.
Abstract (Originalsprache)
We introduce languages of higher-dimensional automata (HDAs) and develop some of their properties. To this end, we define a new category of precubical sets, uniquely naturally isomorphic to the standard one, and introduce a notion of event consistency. HDAs are then finite, labeled, event-consistent precubical sets with distinguished subsets of initial and accepting cells. Their languages are sets of interval orders closed under subsumption; as a major technical step, we expose a bijection between interval orders and a subclass of HDAs. We show that any finite subsumption-closed set of interval orders is the language of an HDA, that languages of HDAs are closed under binary unions and parallel composition, and that bisimilarity implies language equivalence.
Zitieren
APA
Fahrenberg, U., Johansen, C., Struth, G., & Ziemiański, K. (2021). Languages of higher-dimensional automata. Mathematical Structures in Computer Science, 31(5), 575-613. https://doi.org/10.1017/s0960129521000293
Vancouver
Fahrenberg U, Johansen C, Struth G, Ziemiański K. Languages of higher-dimensional automata. Mathematical Structures in Computer Science. 2021;31(5):575-613. doi:10.1017/s0960129521000293
BibTeX
@article{Fahrenberg2021,
author = {Fahrenberg, Uli and Johansen, Christian and Struth, Georg and Ziemiański, Krzysztof},
title = {Languages of higher-dimensional automata},
journal = {Mathematical Structures in Computer Science},
year = {2021},
volume = {31},
number = {5},
pages = {575--613},
doi = {10.1017/s0960129521000293}
}
EUVIMED