--- _id: '711' abstract: - lang: eng text: 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. alternative_title: - LIPIcs article_number: '5' 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 last_name: Otop citation: ama: 'Chatterjee K, Henzinger TA, Otop J. Bidirectional nested weighted automata. In: Vol 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 2017. doi:10.4230/LIPIcs.CONCUR.2017.5' apa: 'Chatterjee, K., Henzinger, T. A., & Otop, J. (2017). Bidirectional nested weighted automata (Vol. 85). Presented at the 28th International Conference on Concurrency Theory, CONCUR, Berlin, Germany: Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5' chicago: Chatterjee, Krishnendu, Thomas A Henzinger, and Jan Otop. “Bidirectional Nested Weighted Automata,” Vol. 85. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. https://doi.org/10.4230/LIPIcs.CONCUR.2017.5. ieee: K. Chatterjee, T. A. Henzinger, and J. Otop, “Bidirectional nested weighted automata,” presented at the 28th International Conference on Concurrency Theory, CONCUR, Berlin, Germany, 2017, vol. 85. ista: Chatterjee K, Henzinger TA, Otop J. 2017. Bidirectional nested weighted automata. 28th International Conference on Concurrency Theory, CONCUR, LIPIcs, vol. 85, 5. mla: Chatterjee, Krishnendu, et al. Bidirectional Nested Weighted Automata. Vol. 85, 5, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017, doi:10.4230/LIPIcs.CONCUR.2017.5. short: K. Chatterjee, T.A. Henzinger, J. Otop, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017. conference: end_date: 2017-09-08 location: Berlin, Germany name: 28th International Conference on Concurrency Theory, CONCUR start_date: 2017-09-05 date_created: 2018-12-11T11:48:04Z date_published: 2017-08-01T00:00:00Z date_updated: 2021-01-12T08:11:53Z day: '01' ddc: - '004' - '005' department: - _id: KrCh - _id: ToHe doi: 10.4230/LIPIcs.CONCUR.2017.5 file: - access_level: open_access checksum: d2bda4783821a6358333fe27f11f4737 content_type: application/pdf creator: system date_created: 2018-12-12T10:08:02Z date_updated: 2020-07-14T12:47:49Z file_id: '4661' file_name: IST-2017-886-v1+1_LIPIcs-CONCUR-2017-5.pdf file_size: 570294 relation: main_file file_date_updated: 2020-07-14T12:47:49Z has_accepted_license: '1' intvolume: ' 85' language: - iso: eng month: '08' oa: 1 oa_version: Published Version publication_identifier: issn: - '18688969' publication_status: published publisher: Schloss Dagstuhl - Leibniz-Zentrum für Informatik publist_id: '6976' pubrep_id: '886' quality_controlled: '1' scopus_import: 1 status: public title: Bidirectional nested weighted automata 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: 3E5EF7F0-F248-11E8-B48F-1D18A9856A87 volume: 85 year: '2017' ...