Multiset Processing: Mathematical,Computer Science, and Molecular Computing Points of View

Fernando Arroyo, Angel V. Baranda, Juan Castellanos, Carmen Luengo (auth.), Cristian S. Calude, Gheorghe PĂun, Grzegorz Rozenberg, Arto Salomaa (eds.)3540430636, 9783540430636

The multiset, as a set with multiplicities associated with its elements in the form of natural numbers, is a notation which has appeared again and again in various areas of mathematics and computer science. As a data structure, multisets stand in-between strings/lists, where a linear ordering of symbols/items is present, and sets, where no ordering and no multiplicity is considered. This book presents a selection of thoroughly reviewed revised full papers contributed to a workshop on multisets held in Curtea de Arges, Romania in August 2000 together with especially commissioned papers. All in all, the book assesses the state of the art of the notion of multisets, the mathematical background, and the computer science and molecular computing relevance.

---

Table of contents :
Structures and Bio-language to Simulate Transition P Systems on Digital Computers….Pages 1-15
Gamma and the Chemical Reaction Model: Fifteen Years After….Pages 17-44
Visual Multiset Rewriting: Applications to Diagram Parsing and Reasoning….Pages 45-67
Multiset Automata….Pages 69-83
Parikh Mapping and Iteration….Pages 85-101
Multiset Constraints and P Systems….Pages 103-121
Toward a Formal Macroset Theory….Pages 123-133
Normal Forms of Grammars, Finite Automata, Abstract Families, and Closure Properties of Multiset Languages….Pages 135-146
On Multisets in Database Systems….Pages 147-215
Tolerance Multisets….Pages 217-223
Fuzzy Multisets and Their Generalizations….Pages 225-235
Universality Results for Some Variants of P Systems….Pages 237-253
Multiset and K -Subset Transforming Systems….Pages 255-265
On P Systems with Active Membranes Solving the Integer Factorization Problem in a Polynomial Time….Pages 267-285
The Linear Theory of Multiset Based Dynamic Systems….Pages 287-297
Artificial Life Applications of a Class of P Systems: Abstract Rewriting Systems on Multisets….Pages 299-346
Mathematics of Multisets….Pages 347-358