License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2016.53
URN: urn:nbn:de:0030-drops-57547
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5754/
Go to the corresponding LIPIcs Volume Portal

Mazowiecki, Filip ; Riveros, Cristian

Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties

pdf-format:
54.pdf (0.6 MB)

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 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.

BibTeX - Entry

@InProceedings{mazowiecki_et_al:LIPIcs:2016:5754,
  author =	{Filip Mazowiecki and Cristian Riveros},
  title =	{{Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{53:1--53:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-001-9},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{47},
  editor =	{Nicolas Ollinger and Heribert Vollmer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/5754},
  URN =		{urn:nbn:de:0030-drops-57547},
  doi =		{10.4230/LIPIcs.STACS.2016.53},
  annote =	{Keywords: Cost Register Automata, Weighted Automata, Semirings}
}

Keywords: Cost Register Automata, Weighted Automata, Semirings
Collection: 33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)
Issue Date: 2016
Date of publication: 16.02.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI