Bidirectional nested weighted automata
From MaRDI portal
Publication:5111617
DOI10.4230/LIPICS.CONCUR.2017.5zbMATH Open1442.68087arXiv1706.08316OpenAlexW2963874005MaRDI QIDQ5111617FDOQ5111617
Thomas A. Henzinger, Krishnendu Chatterjee, Jan Otop
Publication date: 27 May 2020
Abstract: Nested weighted automata (NWA) present a robust and convenient automata-theoretic formalism for quantitative specifications. Previous works have considered NWA that processed input words only in the forward direction. It is natural to allow the automata to process input words backwards as well, for example, to measure the maximal or average time between a response and the preceding request. We therefore introduce and study bidirectional NWA that can process input words in both directions. First, we show that bidirectional NWA can express interesting quantitative properties that are not expressible by forward-only NWA. Second, for the fundamental decision problems of emptiness and universality, we establish decidability and complexity results for the new framework which match the best-known results for the special case of forward-only NWA. Thus, for NWA, the increased expressiveness of bidirectionality is achieved at no additional computational complexity. This is in stark contrast to the unweighted case, where bidirectional finite automata are no more expressive but exponentially more succinct than their forward-only counterparts.
Full work available at URL: https://arxiv.org/abs/1706.08316
Recommendations
- Bideterministic weighted automata
- Nested weighted automata
- Nested weighted automata
- Weighted automata
- scientific article; zbMATH DE number 1962765
- Nested weighted limit-average automata of bounded width
- Weighted nested word automata and logics over strong bimonoids
- Weighted nested word automata and logics over strong bimonoids
- Bisimulation relations for weighted automata
- Alternating Weighted Automata
Cites Work
- Handbook of weighted automata
- Formalizing and Reasoning about Quality
- Latticed-LTL Synthesis in the Presence of Noisy Inputs
- Expressiveness and closure properties for quantitative languages
- Alternating Weighted Automata
- Quantitative languages
- Title not available (Why is that?)
- Weighted Automata and Weighted Logics on Infinite Words
- Temporal Specifications with Accumulative Values
- Mean-Payoff Automaton Expressions
- Nested Weighted Automata
- Quantitative Temporal Simulation and Refinement Distances for Timed Systems
- Quantitative Automata under Probabilistic Semantics
- Regular Functions and Cost Register Automata
- Average-energy games
- Copyless Cost-Register Automata: Structure, Expressiveness, and Closure Properties
- Pebble Weighted Automata and Transitive Closure Logics
- Averaging in LTL
- Nested Weighted Automata
- Nested Weighted Limit-Average Automata of Bounded Width
Cited In (4)
This page was built for publication: Bidirectional nested weighted automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111617)
