Nested weighted limit-average automata of bounded width

DOI10.4230/LIPICS.MFCS.2016.24zbMATH Open1398.68305arXiv1606.03598OpenAlexW2963690846MaRDI QIDQ4608583FDOQ4608583

Authors: Krishnendu Chatterjee, Jan Otop, Thomas A. Henzinger 

Publication date: 21 March 2018

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.

Full work available at URL: https://arxiv.org/abs/1606.03598

Recommendations

• Nested weighted automata
• Nested weighted automata
• Bidirectional nested weighted automata
• Alternating Weighted Automata
• Expressiveness and closure properties for quantitative languages

zbMATH Keywords

complexityweighted automatamean-payoffnested weighted automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cited In (5)

• Multi-Dimensional Long-Run Average Problems for Vector Addition Systems with States
• Long-Run Average Behavior of Vector Addition Systems with States
• Nested weighted automata
• Bidirectional nested weighted automata
• Nested weighted automata

This page was built for publication: Nested weighted limit-average automata of bounded width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4608583)