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

Chatterjee, Krishnendu ; Henzinger, Thomas A. ; Otop, Jan

Nested Weighted Limit-Average Automata of Bounded Width

pdf-format:
LIPIcs-MFCS-2016-24.pdf (0.5 MB)

Abstract

While weighted automata provide a natural framework to express quantitative properties, many basic properties like average response time cannot be expressed with weighted automata. Nested weighted automata extend weighted automata and consist of a master automaton and a set of slave automata that are invoked by the master automaton. Nested weighted automata are strictly more expressive than weighted automata (e.g., average response time can be expressed with nested weighted automata), but the basic decision questions have higher complexity (e.g., for deterministic automata, the emptiness question for nested weighted automata is PSPACE-hard, whereas the corresponding complexity for weighted automata is PTIME). We consider a natural subclass of nested weighted automata where at any point at most a bounded number k of slave automata can be active. We focus on automata whose master value function is the limit average. We show that these nested weighted automata with bounded width are strictly more expressive than weighted automata (e.g., average response time with no overlapping requests can be expressed with bound k=1, but not with non-nested weighted automata). We show that the complexity of the basic decision problems (i.e., emptiness and universality) for the subclass with k constant matches the complexity for weighted automata. Moreover, when k is part of the input given in unary we establish PSPACE-completeness.

BibTeX - Entry

@InProceedings{chatterjee_et_al:LIPIcs:2016:6439,
  author =	{Krishnendu Chatterjee and Thomas A. Henzinger and Jan Otop},
  title =	{{Nested Weighted Limit-Average Automata of Bounded Width}},
  booktitle =	{41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-016-3},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{58},
  editor =	{Piotr Faliszewski and Anca Muscholl and Rolf Niedermeier},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6439},
  URN =		{urn:nbn:de:0030-drops-64397},
  doi =		{10.4230/LIPIcs.MFCS.2016.24},
  annote =	{Keywords: weighted automata, nested weighted automata, complexity, mean-payoff}
}

Keywords: weighted automata, nested weighted automata, complexity, mean-payoff
Collection: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Issue Date: 2016
Date of publication: 19.08.2016

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