Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
|
 |
Multiset Automata
| Book Series | Lecture Notes in Computer Science |
| Publisher | Springer Berlin / Heidelberg |
| ISSN | 0302-9743 (Print) 1611-3349 (Online) |
| Volume | Volume 2235/2001 |
| Book | Multiset Processing |
| DOI | 10.1007/3-540-45523-X |
| Copyright | 2001 |
| ISBN | 978-3-540-43063-6 |
| DOI | 10.1007/3-540-45523-X_4 |
| Pages | 69-83 |
| Subject Collection | Computer Science |
| SpringerLink Date | Monday, January 01, 2001 |
| |
|
Erzsébet Csuhaj-Varjú8  , Carlos Martín-Vide9 and Victor Mitrana10
| (8) |
Computer and Automation Research Institute, Hungarian Academy of Sciences, Kende u. 13-17, H-1111 Budapest, Hungary |
| (9) |
Research Group on Mathematical Linguistics, Rovira i Virgili University, Pça. Imperial Tàrraco 1, 43005 Tarragona, Spain |
| (10) |
University of Bucharest, Faculty of Mathematics, Str. Academiei 14, 70109 Bucharest, Romania |
Abstract
We propose a characterization of a Chomsky-like hierarchy of multiset grammars in terms of multiset automata. We also present
the deterministic variants of all the automata investigated and prove that, unlike the string case, most of them are strictly
less powerful than the nondeterministic variants. Some open problems and further directions of research are briefly discussed.
Research supported by the Hungarian Scientific Research Fund “OTKA” Grant No. T 029615 and by the Direcci’on General de Enseñanza
Superior e Investigaci’on Cienti fica, SB 97-00110508
Fulltext Preview (Small, Large)
 References secured to subscribers.
|
|
|
|
|
|