---
res:
  bibo_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.@eng'
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Krishnendu
      foaf_name: Chatterjee, Krishnendu
      foaf_surname: Chatterjee
      foaf_workInfoHomepage: http://www.librecat.org/personId=2E5DCA20-F248-11E8-B48F-1D18A9856A87
    orcid: 0000-0002-4561-241X
  - foaf_Person:
      foaf_givenName: Thomas A
      foaf_name: Henzinger, Thomas A
      foaf_surname: Henzinger
      foaf_workInfoHomepage: http://www.librecat.org/personId=40876CD8-F248-11E8-B48F-1D18A9856A87
    orcid: 0000−0002−2985−7724
  - foaf_Person:
      foaf_givenName: Jan
      foaf_name: Otop, Jan
      foaf_surname: Otop
      foaf_workInfoHomepage: http://www.librecat.org/personId=2FC5DA74-F248-11E8-B48F-1D18A9856A87
  bibo_doi: 10.4230/LIPIcs.MFCS.2016.24
  bibo_volume: 58
  dct_date: 2016^xs_gYear
  dct_language: eng
  dct_publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik@
  dct_title: Nested weighted limit-average automata of bounded width@
...