Search Results

Documents authored by Ziemiański, Krzysztof

Document
DOI: 10.4230/LIPIcs.CONCUR.2026.32
Algebraic Characterization of FO-Definable Languages of Higher-Dimensional Automata

Authors: Enzo Erlich, Jérémy Ledent, and Krzysztof Ziemiański

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract
Higher-dimensional automata (HDA) are a model of concurrency that models simultaneous execution of events using higher dimensional cells. HDA recognize languages of pomsets, a generalization of finite words whose letters are partially ordered. We prove a new algebraic characterization of HDA languages: a language of pomsets is regular if and only if it is the inverse image of a functor from the category of pomsets into a finite category. Furthermore, the language is definable in first-order logic exactly when it is recognized by an aperiodic category, generalizing the McNaughton-Papert theorem to HDA languages. We also investigate a notion of counter-free HDA, and show that if a language is accepted by a counter-free HDA, it must be definable in first-order logic. The converse, however, is still open.
Cite as

Enzo Erlich, Jérémy Ledent, and Krzysztof Ziemiański. Algebraic Characterization of FO-Definable Languages of Higher-Dimensional Automata. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 32:1-32:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{erlich_et_al:LIPIcs.CONCUR.2026.32,
  author =	{Erlich, Enzo and Ledent, J\'{e}r\'{e}my and Ziemia\'{n}ski, Krzysztof},
  title =	{{Algebraic Characterization of FO-Definable Languages of Higher-Dimensional Automata}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{32:1--32:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.32},
  URN =		{urn:nbn:de:0030-drops-273620},
  doi =		{10.4230/LIPIcs.CONCUR.2026.32},
  annote =	{Keywords: Higher-dimensional automata, Pomset languages, McNaughton-Papert theorem, Counter-free HDA, Aperiodic category}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2026.49
Bisimulations and Modal Logics for Higher Dimensional Automata

Authors: Safa Zouari, Rob van Glabbeek, and Krzysztof Ziemiański

Published in: LIPIcs, Volume 391, 37th International Conference on Concurrency Theory (CONCUR 2026)

Abstract
Higher-Dimensional Automata (HDAs) provide a geometric model of true concurrency. While hereditary history-preserving (hhp) bisimilarity is the finest behavioural equivalence in van Glabbeek’s spectrum, no modal logic has previously characterised it on HDAs. We introduce several new intermediate equivalences that sit strictly between ST- and hhp-bisimilarity. We show how separating similarity and subsumption of paths leads to a clean formulation of these equivalences, and we present a modal logic that characterises hhp-bisimilarity. Natural fragments characterise ST-bisimilarity and the intermediate notions.
Cite as

Safa Zouari, Rob van Glabbeek, and Krzysztof Ziemiański. Bisimulations and Modal Logics for Higher Dimensional Automata. In 37th International Conference on Concurrency Theory (CONCUR 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 391, pp. 49:1-49:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{zouari_et_al:LIPIcs.CONCUR.2026.49,
  author =	{Zouari, Safa and van Glabbeek, Rob and Ziemia\'{n}ski, Krzysztof},
  title =	{{Bisimulations and Modal Logics for Higher Dimensional Automata}},
  booktitle =	{37th International Conference on Concurrency Theory (CONCUR 2026)},
  pages =	{49:1--49:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-447-5},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{391},
  editor =	{Sokolova, Ana and Totzke, Patrick},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2026.49},
  URN =		{urn:nbn:de:0030-drops-273809},
  doi =		{10.4230/LIPIcs.CONCUR.2026.49},
  annote =	{Keywords: higher-dimensional automata, bisimilarity, history-preserving bisimulation, modal logic, concurrency theory}
}
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.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}
}
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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