arXiv Open Access 2024

Logic and Languages of Higher-Dimensional Automata

Amazigh Amrane Hugo Bazille Uli Fahrenberg Marie Fortin

Lihat Sumber

Abstrak

In this paper we study finite higher-dimensional automata (HDAs) from the logical point of view. Languages of HDAs are sets of finite bounded-width interval pomsets with interfaces (iiPoms<=k) closed under order extension. We prove that languages of HDAs are MSO-definable. For the converse, we show that the order extensions of MSO-definable sets of iiPoms<=k are languages of HDAs. As a consequence, unlike the case of all pomsets, order extension of MSO-definable sets of iiPoms<=k is also MSO-definable.

Topik & Kata Kunci

cs.FL cs.LO

Penulis (4)

Amazigh Amrane

Hugo Bazille

Uli Fahrenberg

Marie Fortin

Format Sitasi

APA MLA BibTeX

Amrane, A., Bazille, H., Fahrenberg, U., Fortin, M. (2024). Logic and Languages of Higher-Dimensional Automata. https://arxiv.org/abs/2403.19526

Akses Cepat

Lihat di Sumber

Informasi Jurnal

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