A Kleene Theorem for Higher-Dimensional Automata

Autor:	Fahrenberg, Uli, Johansen, Christian, Struth, Georg, Ziemiański, Krzysztof
Jazyk:	angličtina
Rok vydání:	2022
Předmět:	interval posets labelled precube categories Theory of computation → Automata extensions Kleene theorem higher-dimensional automata concurrency theory
Zdroj:	Leibniz International Proceedings in Informatics
Popis:	We prove a Kleene theorem for higher-dimensional automata (HDAs). It states that the languages they recognise are precisely the rational subsumption-closed sets of interval pomsets. The rational operations include a gluing composition, for which we equip pomsets with interfaces. For our proof, we introduce HDAs with interfaces as presheaves over labelled precube categories and use tools inspired by algebraic topology, such as cylinders and (co)fibrations. HDAs are a general model of non-interleaving concurrency, which subsumes many other models in this field. Interval orders are used as models for concurrent or distributed systems where events extend in time. Our tools and techniques may therefore yield templates for Kleene theorems in various models and applications. LIPIcs, Vol. 243, 33rd International Conference on Concurrency Theory (CONCUR 2022), pages 29:1-29:18
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d89e92d9e30d8f5b09ac0e96914a542f https://hdl.handle.net/11250/3055862 Zobrazit plný text záznamu