View in EDS

On the Complexity of Concurrent Multiset Rewriting.

Saved in:
Bibliographic Details
Title: On the Complexity of Concurrent Multiset Rewriting.
Authors: Bertier, Marin1, Perrin, Matthieu2, Tedeschi, Cédric3
Source: International Journal of Foundations of Computer Science. Jan2016, Vol. 27 Issue 1, p67-83. 17p.
Subjects: Isomorphism (Mathematics), Subgraphs, Algorithms, Data analysis, Computational complexity, Rule-based programming
Abstract: In this paper, we are interested in the runtime complexity of programs based on multiset rewriting. The motivation behind this work is the study of the complexity of chemistry-inspired programming models, which recently regained momentum due to their adequacy to large autonomous systems. In these models, data are most of the time left unstructured in a container, formally, a multiset. The program to be applied to this multiset is specified as a set of conditioned rules rewriting the multiset. At run time, these rewrite operations are applied concurrently, until no rule can be applied anymore (the set of elements they need cannot be found in the multiset anymore). A limitation of these models stand in their complexity: each computation step may require a complexity in where n denotes the number of elements in the multiset, and k is the size of the subset of elements needed to trigger a given rule. By analogy with chemistry, such elements can be called reactants. In this paper, we explore the possibility of improving the complexity of searching reactants through a static analysis of the rules' condition. In particular, we give a characterisation of this complexity, by analogy to the subgraph isomorphism problem. Given a rule R, we define its rank rk(R) and its calibre C(R), allowing us to exhibit an algorithm with a complexity in for searching reactants, while showing that and that most of the time. [ABSTRACT FROM AUTHOR]
Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Database: Engineering Source
FullText Text:
  Availability: 0
Header DbId: egs
DbLabel: Engineering Source
An: 113838540
AccessLevel: 6
PubType: Academic Journal
PubTypeId: academicJournal
PreciseRelevancyScore: 0
IllustrationInfo
Items – Name: Title
  Label: Title
  Group: Ti
  Data: On the Complexity of Concurrent Multiset Rewriting.
– Name: Author
  Label: Authors
  Group: Au
  Data: <searchLink fieldCode="AR" term="%22Bertier%2C+Marin%22">Bertier, Marin</searchLink><relatesTo>1</relatesTo><br /><searchLink fieldCode="AR" term="%22Perrin%2C+Matthieu%22">Perrin, Matthieu</searchLink><relatesTo>2</relatesTo><br /><searchLink fieldCode="AR" term="%22Tedeschi%2C+Cédric%22">Tedeschi, Cédric</searchLink><relatesTo>3</relatesTo>
– Name: TitleSource
  Label: Source
  Group: Src
  Data: <searchLink fieldCode="JN" term="%22International+Journal+of+Foundations+of+Computer+Science%22">International Journal of Foundations of Computer Science</searchLink>. Jan2016, Vol. 27 Issue 1, p67-83. 17p.
– Name: Subject
  Label: Subjects
  Group: Su
  Data: <searchLink fieldCode="DE" term="%22Isomorphism+%28Mathematics%29%22">Isomorphism (Mathematics)</searchLink><br /><searchLink fieldCode="DE" term="%22Subgraphs%22">Subgraphs</searchLink><br /><searchLink fieldCode="DE" term="%22Algorithms%22">Algorithms</searchLink><br /><searchLink fieldCode="DE" term="%22Data+analysis%22">Data analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Computational+complexity%22">Computational complexity</searchLink><br /><searchLink fieldCode="DE" term="%22Rule-based+programming%22">Rule-based programming</searchLink>
– Name: Abstract
  Label: Abstract
  Group: Ab
  Data: In this paper, we are interested in the runtime complexity of programs based on multiset rewriting. The motivation behind this work is the study of the complexity of chemistry-inspired programming models, which recently regained momentum due to their adequacy to large autonomous systems. In these models, data are most of the time left unstructured in a container, formally, a multiset. The program to be applied to this multiset is specified as a set of conditioned rules rewriting the multiset. At run time, these rewrite operations are applied concurrently, until no rule can be applied anymore (the set of elements they need cannot be found in the multiset anymore). A limitation of these models stand in their complexity: each computation step may require a complexity in where n denotes the number of elements in the multiset, and k is the size of the subset of elements needed to trigger a given rule. By analogy with chemistry, such elements can be called reactants. In this paper, we explore the possibility of improving the complexity of searching reactants through a static analysis of the rules' condition. In particular, we give a characterisation of this complexity, by analogy to the subgraph isomorphism problem. Given a rule R, we define its rank rk(R) and its calibre C(R), allowing us to exhibit an algorithm with a complexity in for searching reactants, while showing that and that most of the time. [ABSTRACT FROM AUTHOR]
– Name: AbstractSuppliedCopyright
  Label:
  Group: Ab
  Data: <i>Copyright of International Journal of Foundations of Computer Science is the property of World Scientific Publishing Company and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract.</i> (Copyright applies to all Abstracts.)
PLink https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=egs&AN=113838540
RecordInfo BibRecord:
  BibEntity:
    Identifiers:
      – Type: doi
        Value: 10.1142/S0129054116500052
    Languages:
      – Code: eng
        Text: English
    PhysicalDescription:
      Pagination:
        PageCount: 17
        StartPage: 67
    Subjects:
      – SubjectFull: Isomorphism (Mathematics)
        Type: general
      – SubjectFull: Subgraphs
        Type: general
      – SubjectFull: Algorithms
        Type: general
      – SubjectFull: Data analysis
        Type: general
      – SubjectFull: Computational complexity
        Type: general
      – SubjectFull: Rule-based programming
        Type: general
    Titles:
      – TitleFull: On the Complexity of Concurrent Multiset Rewriting.
        Type: main
  BibRelationships:
    HasContributorRelationships:
      – PersonEntity:
          Name:
            NameFull: Bertier, Marin
      – PersonEntity:
          Name:
            NameFull: Perrin, Matthieu
      – PersonEntity:
          Name:
            NameFull: Tedeschi, Cédric
    IsPartOfRelationships:
      – BibEntity:
          Dates:
            – D: 01
              M: 01
              Text: Jan2016
              Type: published
              Y: 2016
          Identifiers:
            – Type: issn-print
              Value: 01290541
          Numbering:
            – Type: volume
              Value: 27
            – Type: issue
              Value: 1
          Titles:
            – TitleFull: International Journal of Foundations of Computer Science
              Type: main
ResultId 1