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.29
URN: urn:nbn:de:0030-drops-57305
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/5730/
Go to the corresponding LIPIcs Volume Portal

Colcombet, Thomas ; Kuperberg, Denis ; Manuel, Amaldev ; Torunczyk, Szymon

Cost Functions Definable by Min/Max Automata

pdf-format:
30.pdf (0.6 MB)

Abstract

Regular cost functions form a quantitative extension of regular languages that share the array of characterisations the latter possess. In this theory, functions are treated only up to preservation of boundedness on all subsets of the domain. In this work, we subject the well known distance automata (also called min-automata), and their dual max-automata to this framework, and obtain a number of effective characterisations in terms of logic, expressions and algebra.

BibTeX - Entry

@InProceedings{colcombet_et_al:LIPIcs:2016:5730,
  author =	{Thomas Colcombet and Denis Kuperberg and Amaldev Manuel and Szymon Torunczyk},
  title =	{{Cost Functions Definable by Min/Max Automata}},
  booktitle =	{33rd Symposium on Theoretical Aspects of Computer Science (STACS 2016)},
  pages =	{29:1--29: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/5730},
  URN =		{urn:nbn:de:0030-drops-57305},
  doi =		{10.4230/LIPIcs.STACS.2016.29},
  annote =	{Keywords: distance automata, B-automata, regular cost functions, stabilisation monoids, decidability, min-automata, max-automata}
}

Keywords: distance automata, B-automata, regular cost functions, stabilisation monoids, decidability, min-automata, max-automata
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