arXiv Open Access 2021

Languages of Higher-Dimensional Automata

Uli Fahrenberg Christian Johansen Georg Struth Krzysztof Ziemiański

Lihat Sumber

Abstrak

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.

Topik & Kata Kunci

cs.FL

Penulis (4)

Uli Fahrenberg

Christian Johansen

Georg Struth

Krzysztof Ziemiański

Format Sitasi

APA MLA BibTeX

Fahrenberg, U., Johansen, C., Struth, G., Ziemiański, K. (2021). Languages of Higher-Dimensional Automata. https://arxiv.org/abs/2103.07557

Akses Cepat

Lihat di Sumber

Informasi Jurnal

Tahun Terbit: 2021
Bahasa: en
Sumber Database: arXiv
Akses: Open Access ✓