Author(s):

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

Title: 
Nested weighted limitaverage automata of bounded width

Title Series: 
LIPIcs

Affiliation 
IST Austria 
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 PSPACEhard, 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 nonnested 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 PSPACEcompleteness.

Keywords: 
complexity; Weighted automata; nested weighted automata; meanpayoff

Conference Title:

MFCS: Mathematical Foundations of Computer Science (SG)

Volume: 
58

Conference Dates:

August 2226, 2016

Conference Location:

Kraków, Poland

Publisher:

Schloss Dagstuhl  LeibnizZentrum für Informatik

Date Published:

20160101

Start Page: 
24:1

End Page:

24:14

Copyright Statement: 
CC BY

URL: 

DOI: 
10.4230/LIPIcs.MFCS.2016.24

Notes: 
This research was supported in part by the Austrian Science Fund (FWF) under grants S11402N23
(RiSE/SHiNE) and Z211N23 (Wittgenstein Award), ERC Start grant (279307: Graph Games), Vienna
Science and Technology Fund (WWTF) through project ICT15003 and by the National Science Centre
(NCN), Poland under grant 2014/15/D/ST6/04543.

Open access: 
yes (OA journal) 