Abstract
A macroset is a (finite or infinite) set of multisets over a finite alphabet. We introduce a Chomsky-like hierarchy of multiset rewriting devices which, therefore, generate macrosets. Some results are proved about the power of these devices and some open problems are formulated. We also present an algebraic characterization of some of the macroset families as least fixed point solutions of algebraic systems of equations.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
References
J.P. Banătre, A. Coutant, D. Le Metayer, A parallel machine for multiset transformationand its programming style, Future Generation Computer Systems, 4 (1988),133–144.
J.P. Banătre, D. Le Metayer, The Gamma model and its discipline of programming,Science of Computer Programming, 15 (1990), 55–77.
J. P. Banătre, D. Le Metayer, Gamma and the chemical reaction model: ten yearsafter, Coordination Programming: Mechanisms, Models and Semantics, ImperialCollege Press, 1996.
H.P. Barendregt, The Lambda Calculus; Its Syntaxand Semantics, North-Holland, Amsterdam, 1984.
T. Basten, Parsing partially ordered multisets, Intern. J. Found. Computer Sci.,8, 4 (1997), 379–407.
G. Berry, G. Boudol, The chemical abstract machine, Theoretical Computer Sci.,96 (1992), 217–248.
A. Colmerauer, Equations and inequalities on finite and finite trees, Proc. of Second Intern. Conf. on Fifth Generation Computer Systems, Tokyo, 1984, 85–99.
S. Crespi-Reghizzi, D. Mandrioli, Commutative Grammars, Calcolo, 13, 2 (1976),173–189.
J. Dassow, Gh. Păun, Regulated Rewriting in Formal Language Theory, Springer-Verlag, Berlin, 1989.
J. Dassow, Gh Păun, A. Salomaa, Grammars with Controlled Derivations, in:Handbook of Formal Languages, vol. 2, p 101–154, Springer-Verlag, 1997.
S. Ginsburg, The Mathematical Theory of Context-free Languages, McGraw Hill,1966.
J.L. Gischer, The equational theory of pomsets, Theoretical Computer Sci., 61, 2–3(1988), 199–224.
J.S. Golan, The Theory of Semirings with Application in Mathematics and TheoreticalComputer Science, Longman Scientific and Technical, 1992.
S. Gorn, Explicit definitions and linguistic dominoes, in Systems and ComputerScience (J. Hart, S. Takasu, eds.), Univ. of Toronto Press, Toronto, 1967, 77–115.
D.T. Hunyh, Commutative grammars: The complexity of uniform word problem,Inform. Control, 57 (1983), 21–39.
J. Kortelainen, Properties of trios and AFLs with bounded or commutative generators,Mathematics, University of Oulu, No. 53, 1980.
W. Kuich, A. Salomaa, Semirings, Automata, Languages, EATCS Monographs onTheoretical Computer Science 5, Springer-Verlag, Berlin
M. Latteux, Cônes rationnels commutativement clos, R.A.I.R.O., 11, 1 (1977),29–51.
M. Latteux, Langages commutatifs, Publications de Laboratoire de Calcul del’Université des Sciences et Techniques de Lille, May 1978.
M. Latteux, Cônes rationnels commutatifs, Journal of Computer System Sciences,18 (1979), 307–333.
S. Miyamoto, Fuzzy multisets and application to rough approximation of fuzzysets, Techn. Rep. Inst. of Inform. Sciences and Electronics, Univ. of Tsukuba,1SE-TR-96-136, June 1996, 1–10.
S. Miyamoto, Basic operations on fuzzy multisets, J. of Japan Soc. of Fuzzy Theoryand Systems, 8, 4 (1996).
S. Miyamoto, Fuzzy multisets with in finite collections of memberships, Proc. 7thIntern. Fuzzy Systems Ass. World. Congress (IFSA’97), June 1997, Prague, vol. I,61–66.
B. Li, Fuzzy bags and applications, Fuzzy Sets and Systems, 34 (1990), 61–71.
Gh. Păun, Computing with membranes, Journal of Computer and System Sciences,61, 1 (2000), 108–143
Gh. Păun, Computing with membranes. An introduction, Bulletin of the EATCS,67 (Febr. 1999), 139–152.
Gh. Păun, Computing with membranes (P systems): Twenty six researchtopics, Auckland University, CDMTCS Report No 119, 2000(http://www.cs.auckland.ac.nz/CDMTCS).
Gh. Păun, G. Rozenberg, A. Salomaa, DNA Computing. New ComputingParadigms, Springer-Verlag, Heidelberg, 1998.
G. Rozenberg, A. Salomaa, eds., Handbook of Formal Languages, 3 volumes,Springer-Verlag, Berlin, 1997.
Y. Suzuki, H. Tanaka, Symbolic chemical system based on abstract rewriting systemand its behavior pattern, Artificial Life Robotics, 1 (1997), 211–219.
Y. Suzuki, H. Tanaka, Chemical evolution among artificial proto-cells, Proc. of Artificial Life VIII Conf., MIT Press, 2000
A. Syropoulos, A note on multi-sets, basic pairs and the chemical abstract machine,manuscript, 2000.
A. Syropoulos, Fuzzy sets and fuzzy multisets as Chu spaces, manuscript, 2000.
A. Syropoulos, Multisets and Chu Spaces, PhDThesis, Univ. of Xanti, Greece, inpreparation.
R. R. Yager, On the theory of bags, Intern. J. General Systems, 13 (1986), 23–37.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2001 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Kudlek, M., Martín-Vide, C., PĂun, G. (2001). Toward a Formal Macroset Theory. In: Calude, C.S., PĂun, G., Rozenberg, G., Salomaa, A. (eds) Multiset Processing. WMC 2000. Lecture Notes in Computer Science, vol 2235. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-45523-X_7
Download citation
DOI: https://doi.org/10.1007/3-540-45523-X_7
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-43063-6
Online ISBN: 978-3-540-45523-3
eBook Packages: Springer Book Archive