Copyless cost-register automata: structure, expressiveness, and closure properties
From MaRDI portal
Publication:4601905
DOI10.4230/LIPICS.STACS.2016.53zbMATH Open1388.68175arXiv1504.01709OpenAlexW2295631659MaRDI QIDQ4601905FDOQ4601905
Authors: Filip Mazowiecki, Cristian Riveros 
Publication date: 24 January 2018
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.
Full work available at URL: https://arxiv.org/abs/1504.01709
Recommendations
Cited In (12)
- Cost register automata for nested words
- Copyless cost-register automata: structure, expressiveness, and closure properties
- Better complexity bounds for cost register automata
- Better complexity bounds for cost register automata
- Maximal partition logic: towards a logical characterization of copyless cost register automata
- Weak cost register automata are still powerful
- Bidirectional nested weighted automata
- Weak cost register automata are still powerful
- Regular functions and cost register automata (invited paper)
- Pumping lemmas for weighted automata
- Streamable regular transductions
- Determinisation of finitely-ambiguous copyless cost register automata
This page was built for publication: Copyless cost-register automata: structure, expressiveness, and closure properties
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4601905)
