Abstract
It is highly desirable for a computational model to have a logic characterization like in the seminal work from Buchi that connects MSO with finite automata. For example, weighted automata are the quantitative extension of finite automata for computing functions over words and they can be naturally characterized by a subframent of weighted logic introduced by Droste and Gastin. Recently, cost register automata (CRA) were introduced by Alur et al. as an alternative model for weighted automata. In hope of finding decidable subclasses of weighted automata, they proposed to restrict their model with the socalled copyless restriction. Unfortunately, copyless CRA do not enjoy good closure properties and, therefore, a logical characterization of this class seems to be unlikely.
In this paper, we introduce a new logic called maximal partition logic (MPL) for studying the expressiveness of copyless CRA. In contrast from the previous approaches (i.e. weighted logics), MPL is based on a new set of "regular" quantifiers that partition a word into maximal subwords, compute the output of a subformula over each subword separately, and then aggregate these outputs with a semiring operation. We study the expressiveness of MPL and compare it with weighted logics. Furthermore, we show that MPL is equally expressive to a natural subclass of copyless CRA. This shows the first logical characterization of copyless CRA and it gives a better understanding of the copyless restriction in weighted automata.
BibTeX  Entry
@InProceedings{mazowiecki_et_al:LIPIcs:2015:5412,
author = {Filip Mazowiecki and Cristian Riveros},
title = {{Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata}},
booktitle = {24th EACSL Annual Conference on Computer Science Logic (CSL 2015)},
pages = {144159},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897903},
ISSN = {18688969},
year = {2015},
volume = {41},
editor = {Stephan Kreutzer},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2015/5412},
URN = {urn:nbn:de:0030drops54127},
doi = {10.4230/LIPIcs.CSL.2015.144},
annote = {Keywords: MSO, Finite Automata, Cost Register Automata, Weighted Automata, Weighted Logics, Semirings}
}
Keywords: 

MSO, Finite Automata, Cost Register Automata, Weighted Automata, Weighted Logics, Semirings 
Seminar: 

24th EACSL Annual Conference on Computer Science Logic (CSL 2015) 
Issue Date: 

2015 
Date of publication: 

04.09.2015 