Commutative grammars |
| |
| Authors: | S Crespi-Reghizzi D Mandrioli |
| |
| Affiliation: | (1) Istituto di Elettrotecnica ed Elettronica del Politecnico e Centro CNR per l’Ingegneria dei Sistemi per l’Elaborazione dell’Informazione, Piazza L. Da Vinci, 32-20133 Milano |
| |
| Abstract: | Commutative grammars are a formalism for generating bags, equivalent to vector addition systems and Petri nets. Known results
are recalled and new one are presented on reachability and boundedness. In particular some subclasses of commutative grammars
are introduced which admit a positive answer to these problems, and generate semilinear languages. Finally the equivalence,
via Parikh mapping, of commutative and matrix grammars is proven. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
