Back to Search
Start Over
Copyless cost-register automata: Structure, expressiveness, and closure properties.
- Source :
-
Journal of Computer & System Sciences . Mar2019, Vol. 100, p1-29. 29p. - Publication Year :
- 2019
-
Abstract
- Abstract Cost register automata (CRA) and its subclass, copyless CRA, were recently proposed by Alur et al. as a new model for computing functions over strings. We study some structural properties, expressiveness, and closure properties of copyless CRA. We show that copyless CRA are strictly less expressive than weighted automata and are not closed under reverse operation. To find a better class we impose restrictions on copyless CRA, which ends successfully with a new robust computational model that is closed under reverse and other extensions. Highlights • A recently proposed model for computing functions copyless CRA is studied. • It is shown that copyless CRA are not closed under reverse. • A restricted variant bounded alternation CRA (BAC) is proposed. • BAC is shown to be closed under reverse and other extensions. [ABSTRACT FROM AUTHOR]
- Subjects :
- *COST control
*ROBOTS
*COST accounting
*FINANCIAL management
*EXTERNALITIES
Subjects
Details
- Language :
- English
- ISSN :
- 00220000
- Volume :
- 100
- Database :
- Academic Search Index
- Journal :
- Journal of Computer & System Sciences
- Publication Type :
- Academic Journal
- Accession number :
- 133093697
- Full Text :
- https://doi.org/10.1016/j.jcss.2018.07.002