1 Search Results for "Ziemiański, Krzysztof"

Document
DOI: 10.4230/LIPIcs.CONCUR.2022.29
A Kleene Theorem for Higher-Dimensional Automata

Authors: Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański

Published in: LIPIcs, Volume 243, 33rd International Conference on Concurrency Theory (CONCUR 2022)

Abstract
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.
Cite as

Uli Fahrenberg, Christian Johansen, Georg Struth, and Krzysztof Ziemiański. A Kleene Theorem for Higher-Dimensional Automata. In 33rd International Conference on Concurrency Theory (CONCUR 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 243, pp. 29:1-29:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{fahrenberg_et_al:LIPIcs.CONCUR.2022.29,
  author =	{Fahrenberg, Uli and Johansen, Christian and Struth, Georg and Ziemia\'{n}ski, Krzysztof},
  title =	{{A Kleene Theorem for Higher-Dimensional Automata}},
  booktitle =	{33rd International Conference on Concurrency Theory (CONCUR 2022)},
  pages =	{29:1--29:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-246-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{243},
  editor =	{Klin, Bartek and Lasota, S{\l}awomir and Muscholl, Anca},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2022.29},
  URN =		{urn:nbn:de:0030-drops-170925},
  doi =		{10.4230/LIPIcs.CONCUR.2022.29},
  annote =	{Keywords: higher-dimensional automata, interval posets, Kleene theorem, concurrency theory, labelled precube categories}
}
  • Refine by Author
  • 1 Fahrenberg, Uli
  • 1 Johansen, Christian
  • 1 Struth, Georg
  • 1 Ziemiański, Krzysztof

  • Refine by Classification
  • 1 Theory of computation → Automata extensions

  • Refine by Keyword
  • 1 Kleene theorem
  • 1 concurrency theory
  • 1 higher-dimensional automata
  • 1 interval posets
  • 1 labelled precube categories

  • Refine by Type
  • 1 document

  • Refine by Publication Year
  • 1 2022

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact