---
_id: '1090'
abstract:
- lang: eng
  text: ' 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.'
acknowledgement: "This research was supported in part by the Austrian Science Fund
  (FWF) under grants S11402-N23\r\n(RiSE/SHiNE) and Z211-N23 (Wittgenstein Award),
  ERC Start grant (279307: Graph Games), Vienna\r\nScience and Technology Fund (WWTF)
  through project ICT15-003 and by the National Science Centre\r\n(NCN), Poland under
  grant 2014/15/D/ST6/04543."
alternative_title:
- LIPIcs
article_number: '24'
article_processing_charge: No
author:
- first_name: Krishnendu
  full_name: Chatterjee, Krishnendu
  id: 2E5DCA20-F248-11E8-B48F-1D18A9856A87
  last_name: Chatterjee
  orcid: 0000-0002-4561-241X
- first_name: Thomas A
  full_name: Henzinger, Thomas A
  id: 40876CD8-F248-11E8-B48F-1D18A9856A87
  last_name: Henzinger
  orcid: 0000−0002−2985−7724
- first_name: Jan
  full_name: Otop, Jan
  id: 2FC5DA74-F248-11E8-B48F-1D18A9856A87
  last_name: Otop
citation:
  ama: 'Chatterjee K, Henzinger TA, Otop J. Nested weighted limit-average automata
    of bounded width. In: Vol 58. Schloss Dagstuhl - Leibniz-Zentrum für Informatik;
    2016. doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2016.24">10.4230/LIPIcs.MFCS.2016.24</a>'
  apa: 'Chatterjee, K., Henzinger, T. A., &#38; Otop, J. (2016). Nested weighted limit-average
    automata of bounded width (Vol. 58). Presented at the MFCS: Mathematical Foundations
    of Computer Science, Krakow; Poland: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
    <a href="https://doi.org/10.4230/LIPIcs.MFCS.2016.24">https://doi.org/10.4230/LIPIcs.MFCS.2016.24</a>'
  chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Nested Weighted
    Limit-Average Automata of Bounded Width,” Vol. 58. Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2016. <a href="https://doi.org/10.4230/LIPIcs.MFCS.2016.24">https://doi.org/10.4230/LIPIcs.MFCS.2016.24</a>.
  ieee: 'K. Chatterjee, T. A. Henzinger, and J. Otop, “Nested weighted limit-average
    automata of bounded width,” presented at the MFCS: Mathematical Foundations of
    Computer Science, Krakow; Poland, 2016, vol. 58.'
  ista: 'Chatterjee K, Henzinger TA, Otop J. 2016. Nested weighted limit-average automata
    of bounded width. MFCS: Mathematical Foundations of Computer Science, LIPIcs,
    vol. 58, 24.'
  mla: Chatterjee, Krishnendu, et al. <i>Nested Weighted Limit-Average Automata of
    Bounded Width</i>. Vol. 58, 24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik,
    2016, doi:<a href="https://doi.org/10.4230/LIPIcs.MFCS.2016.24">10.4230/LIPIcs.MFCS.2016.24</a>.
  short: K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum
    für Informatik, 2016.
conference:
  end_date: 2016-08-26
  location: Krakow; Poland
  name: 'MFCS: Mathematical Foundations of Computer Science'
  start_date: 2016-08-22
date_created: 2018-12-11T11:50:05Z
date_published: 2016-08-01T00:00:00Z
date_updated: 2025-07-10T11:50:02Z
day: '01'
ddc:
- '004'
department:
- _id: KrCh
- _id: ToHe
doi: 10.4230/LIPIcs.MFCS.2016.24
ec_funded: 1
file:
- access_level: open_access
  content_type: application/pdf
  creator: system
  date_created: 2018-12-12T10:17:31Z
  date_updated: 2018-12-12T10:17:31Z
  file_id: '5286'
  file_name: IST-2017-795-v1+1_LIPIcs-MFCS-2016-24.pdf
  file_size: 564560
  relation: main_file
file_date_updated: 2018-12-12T10:17:31Z
has_accepted_license: '1'
intvolume: '        58'
language:
- iso: eng
month: '08'
oa: 1
oa_version: Published Version
project:
- _id: 25832EC2-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: S 11407_N23
  name: Rigorous Systems Engineering
- _id: 25F42A32-B435-11E9-9278-68D0E5697425
  call_identifier: FWF
  grant_number: Z211
  name: Formal methods for the design and analysis of complex systems
- _id: 2581B60A-B435-11E9-9278-68D0E5697425
  call_identifier: FP7
  grant_number: '279307'
  name: 'Quantitative Graph Games: Theory and Applications'
- _id: 25892FC0-B435-11E9-9278-68D0E5697425
  grant_number: ICT15-003
  name: Efficient Algorithms for Computer Aided Verification
publication_status: published
publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik
publist_id: '6286'
pubrep_id: '795'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Nested weighted limit-average automata of bounded width
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
volume: 58
year: '2016'
...