article

Pattern-matching and rewriting rules for group indexed data structures

Authors:

Jean-Louis Giavitto,

Olivier Michel,

Julien CohenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 37, Issue 12

Pages 76 - 87

https://doi.org/10.1145/636517.636529

Published: 01 December 2002 Publication History

Abstract

In this paper, we present a new framework for the definition of various data structures (including trees and arrays) together with a generic language of filters enabling a rule-based programming style for functions. This framework is implemented in an experimental language called MGS. The underlying notions funding our framework have a topological nature and enable to extend the case-based definition of functions found in modern functional languages beyond algebraic data structures.

References

[1]

Theodore P. Baker. A technique for extending rapid exact-match string matching to arrays of more than one dimension. SIAM J. Comput., 7(4):533--541, 1978.]]

[2]

Gérard Berry and Gérard Boudol. The chemical abstract machine. Theoretical Computer Science, 96:217--248, 1992.]]

Digital Library

[3]

R. S. Bird. Two dimensional pattern matching. Information Processing Letters, 6(5):168--170, October 1977.]]

[4]

J. P. Banâtre and Daniel Le Métayer. A new computational model and its discipline of programming. Technical Report RR-0566, Inria, 1986.]]

[5]

Janusz A. Brzozowski. Derivatives of regular expressions. JACM, 11(4):481--494, 1964.]]

Digital Library

[6]

Thomas Chaboud. About planar cayley graphs. In Fundamentals of Computation Theory (FCT '95), volume 965 of LNCS, pages 137--142, 1995.]]

Digital Library

[7]

Marina Chen, Young il Choo, and Jingke Li. Crystal: Theory and Pragmatics of Generating Efficient Parallel Code. In Boleslaw K. Szymanski, editor, Parallel Functional Languages and Compilers, Frontier Series, chapter 7, pages 255--308. ACM Press, New York, 1991.]]

Digital Library

[8]

J.-L. Giavitto, D. De Vito, and J.-P. Sansonnet. A data parallel Java client-server architecture for data field computations over ZZn. In EuroPar'98 Parallel Processing, volume 1470 of LNCS, pages 742--??, September 1998.]]

Digital Library

[9]

D. Gautier and C. Germain. A static approach for compiling communications in parallel scientific programs. Scientific Programming, 4:291--305, 1995.]]

Digital Library

[10]

J.-L. Giavitto, C. Godin, O. Michel, and P. Prusinkiewicz. Biological Modeling in the Genomic Context, chapter "Computational Models for Integrative and Developmental Biology". Hermes, July 2002. (to appear).]]

[11]

J.-L. Giavitto and O. Michel. MGS: a programming language for the transformations of topological collections. Technical Report 61--2001, LaMI - Universite' d'Évry Val d'Essonne, May 2001.]]

[12]

J.-L. Giavitto and O. Michel. MGS: a rule-based programming language for complex objects and collections. In Mark van den Brand and Rakesh Verma, editors, Electronic Notes in Theoretical Computer Science, volume 59. Elsevier Science Publishers, 2001.]]

[13]

J.-L. Giavitto and O. Michel. The topological structures of membrane computing. Fundamenta Informaticae, 49:107--129, 2002.]]

Digital Library

[14]

J.-L. Giavitto and O. Michel. Data Structure as Topological Spaces. In 3th Int. Conf. on Unconventional Models of ComputationFundamenta Informaticae, Himeji, Japan. To be published in the LNCS serie. Spinger, 2002.]]

Digital Library

[15]

J.-L. Giavitto, O. Michel, and J. Sansonnet. Group-based fields. In Parallel Symbolic Languages and Systems (Int. Workshop PSLS'95), volume LNCS 1068, pages 209--215. Springer, 1996.]]

Digital Library

[16]

J. Jeuring. The derivation of a hierarchy of algorithms for pattern matching on arrays. In G. Hains and L. M. R. Mullin, editors, Proceedings ATABLE-92, Second international workshop on array structures, 1992.]]

[17]

Richard M. Karp, Raymond E. Miller, and Shmuel Winograd. The organization of computations for uniform recurrence equations. Journal of the ACM, 14(3):563--590, July 1967.]]

Digital Library

[18]

B. Lisper. Data parallelism and functional programming. In Proc. ParaDigme Spring School on Data Parallelism. Springer-Verlag, March 1996. Les Ménuires, France.]]

Digital Library

[19]

Vincenzo Manca. Logical string rewriting. Theoretical Computer Science, 264(1):25--51, August 2001.]]

Digital Library

[20]

G. Paun. Computing with membranes: An introduction. Bulletin of the European Association for Theoretical Computer Science, 67:139--152, February 1999.]]

[21]

G. Rozenberg and A. Salomaa. Lindenmayer Systems. Springer, Berlin, 1992.]]

[22]

J.-P. Serre. Arbres, Amalgames, SL2. Number 46 in Astérisque. Société Mathématique de France, 1977.]]

[23]

J. Von Neumann. Theory of Self-Reproducing Automata. Univ. of Illinois Press, 1966.]]

Digital Library

[24]

W. W. Wadge and E. A. Ashcroft. Lucid, the Data flow programming language. Academic Press U. K., 1985.]]

Digital Library

[25]

J. Allan Yang and Young-il Choo. Data fields as parallel programs. In Proceedings of the Second International Workshop on Array Structure, Montreal, Canada, June/July 1992.]]

[26]

Hubert P. Yockey, Robert P. Platzman, and Henry Quastler, editors. Symposium on Information Theory in Biology. Pergamon Press, New York, London, 1958.]]

Cited By

Giavitto JKlaudel HPommereau F(2019)Integrated regulatory networks (IRNs)Theoretical Computer Science10.1016/j.tcs.2011.12.054431(219-234)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2011.12.054
Giavitto JEcheveste JChitil OKing ADanvy O(2014)Real-Time Matching of Antescofo Temporal PatternsProceedings of the 16th International Symposium on Principles and Practice of Declarative Programming10.1145/2643135.2643158(93-104)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1145/2643135.2643158
Ibrahim BHenze RGruenert GEgbert MHuwald JDittrich P(2013)Spatial Rule-Based Modeling: A Method and Its Application to the Human Mitotic KinetochoreCells10.3390/cells20305062:3(506-544)Online publication date: 2-Jul-2013
https://doi.org/10.3390/cells2030506
Show More Cited By

Index Terms

Recommendations

Pattern-matching and rewriting rules for group indexed data structures
RULE '02: Proceedings of the 2002 ACM SIGPLAN workshop on Rule-based programming

In this paper, we present a new framework for the definition of various data structures (including trees and arrays) together with a generic language of filters enabling a rule-based programming style of functions. This framework is implemented in an ...
Operational Termination of Conditional Rewriting with Built-in Numbers and Semantic Data Structures

While ordinary conditional rewrite systems are more elegant than unconditional ones, they still have limited expressive power since semantic data structures, such as sets or multisets, cannot be modeled elegantly. Extending our work presented at RTA ...
Formalization and abstract implementation of rewriting with nested rules
PPDP '04: Proceedings of the 6th ACM SIGPLAN international conference on Principles and practice of declarative programming

This paper formalizes term rewriting systems (TRSs), called scoped, in which a rewrite rule can be nested within another rewrite rule. The right-hand side and/or the condition of a nested rule can refer to any variable in the left-hand side of a nesting ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 37, Issue 12

December 2002

111 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/636517

Issue’s Table of Contents

Copyright © 2002 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 December 2002

Published in SIGPLAN Volume 37, Issue 12

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
286
Total Downloads

Downloads (Last 12 months)2
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Giavitto JKlaudel HPommereau F(2019)Integrated regulatory networks (IRNs)Theoretical Computer Science10.1016/j.tcs.2011.12.054431(219-234)Online publication date: 5-Jan-2019
https://dl.acm.org/doi/10.1016/j.tcs.2011.12.054
Giavitto JEcheveste JChitil OKing ADanvy O(2014)Real-Time Matching of Antescofo Temporal PatternsProceedings of the 16th International Symposium on Principles and Practice of Declarative Programming10.1145/2643135.2643158(93-104)Online publication date: 8-Sep-2014
https://dl.acm.org/doi/10.1145/2643135.2643158
Ibrahim BHenze RGruenert GEgbert MHuwald JDittrich P(2013)Spatial Rule-Based Modeling: A Method and Its Application to the Human Mitotic KinetochoreCells10.3390/cells20305062:3(506-544)Online publication date: 2-Jul-2013
https://doi.org/10.3390/cells2030506
Spicher AMichel OGiavitto J(2010)Interaction-Based Simulations for Integrative Spatial Systems BiologyUnderstanding the Dynamics of Biological Systems10.1007/978-1-4419-7964-3_10(195-231)Online publication date: 9-Dec-2010
https://doi.org/10.1007/978-1-4419-7964-3_10

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents