12
views
0
recommends
+1 Recommend
0 collections
    0
    shares
      • Record: found
      • Abstract: found
      • Article: found
      Is Open Access

      Completeness and Incompleteness of Synchronous Kleene Algebra

      Preprint

      Read this article at

      Bookmark
          There is no author summary for this article yet. Authors can add summaries to their articles on ScienceOpen to make them more accessible to a non-specialist audience.

          Abstract

          Synchronous Kleene algebra (SKA), an extension of Kleene algebra (KA), was proposed by Prisacariu as a tool for reasoning about programs that may execute synchronously, i.e., in lock-step. We provide a countermodel witnessing that the axioms of SKA are incomplete w.r.t. its language semantics, by exploiting a lack of interaction between the synchronous product operator and the Kleene star. We then propose an alternative set of axioms for SKA, based on Salomaa's axiomatisation of regular languages, and show that these provide a sound and complete characterisation w.r.t. the original language semantics.

          Related collections

          Most cited references19

          • Record: found
          • Abstract: not found
          • Article: not found

          Calculi for synchrony and asynchrony

            Bookmark
            • Record: found
            • Abstract: not found
            • Article: not found

            Derivatives of Regular Expressions

              Bookmark
              • Record: found
              • Abstract: not found
              • Article: not found

              Process algebra for synchronous communication

                Bookmark

                Author and article information

                Journal
                21 May 2019
                Article
                1905.08554
                260e71a3-d880-415c-9401-cbe83e10b4ed

                http://arxiv.org/licenses/nonexclusive-distrib/1.0/

                History
                Custom metadata
                cs.LO

                Theoretical computer science
                Theoretical computer science

                Comments

                Comment on this article