Pomset automata are an operational model of weak bi-Kleene algebra, which describes programs that can fork an execution into parallel threads, upon completion of which execution can join to resume as a single thread. We characterize a fragment of pomset automata that admits a decision procedure for language equivalence. Furthermore, we prove that this fragment corresponds precisely to series-rational expressions, i.e., rational expressions with an additional operator for bounded parallelism. As a consequence, we obtain a new proof that equivalence of series-rational expressions is decidable.

Equivalence checking for weak bi-kleene algebra∗ / Kappe T.; Brunet P.; Luttik B.; Silva A.; Zanasi F.. - In: LOGICAL METHODS IN COMPUTER SCIENCE. - ISSN 1860-5974. - ELETTRONICO. - 17:3(2021), pp. 19.1-19.53. [10.46298/LMCS-17(3:19)2021]

Equivalence checking for weak bi-kleene algebra∗

Zanasi F.
2021

Abstract

Pomset automata are an operational model of weak bi-Kleene algebra, which describes programs that can fork an execution into parallel threads, upon completion of which execution can join to resume as a single thread. We characterize a fragment of pomset automata that admits a decision procedure for language equivalence. Furthermore, we prove that this fragment corresponds precisely to series-rational expressions, i.e., rational expressions with an additional operator for bounded parallelism. As a consequence, we obtain a new proof that equivalence of series-rational expressions is decidable.
2021
Equivalence checking for weak bi-kleene algebra∗ / Kappe T.; Brunet P.; Luttik B.; Silva A.; Zanasi F.. - In: LOGICAL METHODS IN COMPUTER SCIENCE. - ISSN 1860-5974. - ELETTRONICO. - 17:3(2021), pp. 19.1-19.53. [10.46298/LMCS-17(3:19)2021]
Kappe T.; Brunet P.; Luttik B.; Silva A.; Zanasi F.
File in questo prodotto:
File Dimensione Formato  
1807.02102.pdf

accesso aperto

Tipo: Versione (PDF) editoriale
Licenza: Licenza per Accesso Aperto. Creative Commons Attribuzione (CCBY)
Dimensione 673.38 kB
Formato Adobe PDF
673.38 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/904563
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? 0
social impact