Brzozowski goes concurrent: A Kleene Theorem for pomset languages

T. Kappé, P. Brunet, Bas Luttik, A. Silva, F. Zanasi

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

3 Citaten (Scopus)
17 Downloads (Pure)

Samenvatting

Concurrent Kleene Algebra (CKA) is a mathematical formalism to study programs that exhibit concurrent behaviour. As with previous extensions of Kleene Algebra, characterizing the free model is crucial in order to develop the foundations of the theory and potential applications. For CKA, this has been an open question for a few years and this paper makes an important step towards an answer. We present a new automaton model and a Kleene-like theorem that relates a relaxed version of CKA to series-parallel pomset languages, which are a natural candidate for the free model. There are two substantial differences with previous work: from expressions to automata, we use Brzozowski derivatives, which enable a direct construction of the automaton; from automata to expressions, we provide a syntactic characterization of the automata that denote valid CKA behaviours.
Originele taal-2Engels
Titel28th International Conference on Concurrency Theory (CONCUR 2017)
RedacteurenRoland Meyer, Uwe Nestmann
Plaats van productieDagstuhl
UitgeverijSchloss Dagstuhl - Leibniz-Zentrum für Informatik
Pagina's1-16
Aantal pagina's16
ISBN van elektronische versie9783959770484
DOI's
StatusGepubliceerd - 1 aug 2017
Evenement28th International Conference on Concurrency Theory, CONCUR 2017 - Berlin, Duitsland
Duur: 5 sep 20178 sep 2017

Publicatie series

NaamLeibniz International Proceedings in Informatics (LIPIcs)
UitgeverijSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik
Volume85

Congres

Congres28th International Conference on Concurrency Theory, CONCUR 2017
LandDuitsland
StadBerlin
Periode5/09/178/09/17

Vingerafdruk Duik in de onderzoeksthema's van 'Brzozowski goes concurrent: A Kleene Theorem for pomset languages'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit

    Kappé, T., Brunet, P., Luttik, B., Silva, A., & Zanasi, F. (2017). Brzozowski goes concurrent: A Kleene Theorem for pomset languages. In R. Meyer, & U. Nestmann (editors), 28th International Conference on Concurrency Theory (CONCUR 2017) (blz. 1-16). [25] (Leibniz International Proceedings in Informatics (LIPIcs); Vol. 85). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2017.25