4 Search Results for "Struth, Georg"

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}
}
Document
DOI: 10.4230/LIPIcs.CALCO.2019.18
Nominal String Diagrams

Authors: Samuel Balco and Alexander Kurz

Published in: LIPIcs, Volume 139, 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)

Abstract
We introduce nominal string diagrams as string diagrams internal in the category of nominal sets. This requires us to take nominal sets as a monoidal category, not with the cartesian product, but with the separated product. To this end, we develop the beginnings of a theory of monoidal categories internal in a symmetric monoidal category. As an instance, we obtain a notion of a nominal PROP as a PROP internal in nominal sets. A 2-dimensional calculus of simultaneous substitutions is an application.
Cite as

Samuel Balco and Alexander Kurz. Nominal String Diagrams. In 8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 139, pp. 18:1-18:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{balco_et_al:LIPIcs.CALCO.2019.18,
  author =	{Balco, Samuel and Kurz, Alexander},
  title =	{{Nominal String Diagrams}},
  booktitle =	{8th Conference on Algebra and Coalgebra in Computer Science (CALCO 2019)},
  pages =	{18:1--18:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-120-7},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{139},
  editor =	{Roggenbach, Markus and Sokolova, Ana},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CALCO.2019.18},
  URN =		{urn:nbn:de:0030-drops-114466},
  doi =		{10.4230/LIPIcs.CALCO.2019.18},
  annote =	{Keywords: string diagrams, nominal sets, separated product, simultaneous substitutions, internal category, monoidal category, internal monoidal categories, PROP}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2019.40
Reordering Derivatives of Trace Closures of Regular Languages

Authors: Hendrik Maarand and Tarmo Uustalu

Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)

Abstract
We provide syntactic derivative-like operations, defined by recursion on regular expressions, in the styles of both Brzozowski and Antimirov, for trace closures of regular languages. Just as the Brzozowski and Antimirov derivative operations for regular languages, these syntactic reordering derivative operations yield deterministic and nondeterministic automata respectively. But trace closures of regular languages are in general not regular, hence these automata cannot generally be finite. Still, as we show, for star-connected expressions, the Antimirov and Brzozowski automata, suitably quotiented, are finite. We also define a refined version of the Antimirov reordering derivative operation where parts-of-derivatives (states of the automaton) are nonempty lists of regular expressions rather than single regular expressions. We define the uniform scattering rank of a language and show that, for a regexp whose language has finite uniform scattering rank, the truncation of the (generally infinite) refined Antimirov automaton, obtained by removing long states, is finite without any quotienting, but still accepts the trace closure. We also show that star-connected languages have finite uniform scattering rank.
Cite as

Hendrik Maarand and Tarmo Uustalu. Reordering Derivatives of Trace Closures of Regular Languages. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{maarand_et_al:LIPIcs.CONCUR.2019.40,
  author =	{Maarand, Hendrik and Uustalu, Tarmo},
  title =	{{Reordering Derivatives of Trace Closures of Regular Languages}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Fokkink, Wan and van Glabbeek, Rob},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.40},
  URN =		{urn:nbn:de:0030-drops-109426},
  doi =		{10.4230/LIPIcs.CONCUR.2019.40},
  annote =	{Keywords: Mazurkiewicz traces, trace closure, regular languages, finite automata, language derivatives, scattering rank, star-connected expressions}
}
Document
DOI: 10.4230/LIPIcs.CONCUR.2017.28
On Decidability of Concurrent Kleene Algebra

Authors: Paul Brunet, Damien Pous, and Georg Struth

Published in: LIPIcs, Volume 85, 28th International Conference on Concurrency Theory (CONCUR 2017)

Abstract
Concurrent Kleene algebras support equational reasoning about computing systems with concurrent behaviours. Their natural semantics is given by series(-parallel) rational pomset languages, a standard true concurrency semantics, which is often associated with processes of Petri nets. We use constructions on Petri nets to provide two decision procedures for such pomset languages motivated by the equational and the refinement theory of concurrent Kleene algebra. The contribution to the first problem lies in a much simpler algorithm and an EXPSPACE complexity bound. Decidability of the second, more interesting problem is new and, in fact, EXPSPACE-complete.
Cite as

Paul Brunet, Damien Pous, and Georg Struth. On Decidability of Concurrent Kleene Algebra. In 28th International Conference on Concurrency Theory (CONCUR 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 85, pp. 28:1-28:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{brunet_et_al:LIPIcs.CONCUR.2017.28,
  author =	{Brunet, Paul and Pous, Damien and Struth, Georg},
  title =	{{On Decidability of Concurrent Kleene Algebra}},
  booktitle =	{28th International Conference on Concurrency Theory (CONCUR 2017)},
  pages =	{28:1--28:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-048-4},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{85},
  editor =	{Meyer, Roland and Nestmann, Uwe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2017.28},
  URN =		{urn:nbn:de:0030-drops-77881},
  doi =		{10.4230/LIPIcs.CONCUR.2017.28},
  annote =	{Keywords: Concurrent Kleene algebra, series-parallel pomsets, Petri nets}
}
  • Refine by Author
  • 2 Struth, Georg
  • 1 Balco, Samuel
  • 1 Brunet, Paul
  • 1 Fahrenberg, Uli
  • 1 Johansen, Christian
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing
  • 1 Software and its engineering → General programming languages
  • 1 Theory of computation → Automata extensions
  • 1 Theory of computation → Concurrency
  • 1 Theory of computation → Logic
  • Show More...

  • Refine by Keyword
  • 1 Concurrent Kleene algebra
  • 1 Kleene theorem
  • 1 Mazurkiewicz traces
  • 1 PROP
  • 1 Petri nets
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2019
  • 1 2017
  • 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