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.CSL.2015.144
URN: urn:nbn:de:0030-drops-54127
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2015/5412/
Go to the corresponding LIPIcs Volume Portal

Mazowiecki, Filip ; Riveros, Cristian

Maximal Partition Logic: Towards a Logical Characterization of Copyless Cost Register Automata

pdf-format:
9.pdf (0.5 MB)

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 so-called 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 =	{144--159},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-90-3},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{41},
  editor =	{Stephan Kreutzer},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2015/5412},
  URN =		{urn:nbn:de:0030-drops-54127},
  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
Collection: 24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Issue Date: 2015
Date of publication: 07.09.2015

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