License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2020.44
URN: urn:nbn:de:0030-drops-132850
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13285/
Droste, Manfred ;
Dziadek, Sven ;
Kuich, Werner
Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words
Abstract
Recently, weighted ω-pushdown automata have been introduced by Droste, Ésik, Kuich. This new type of automaton has access to a stack and models quantitative aspects of infinite words. Here, we consider a simple version of those automata. The simple ω-pushdown automata do not use ε-transitions and have a very restricted stack access. In previous work, we could show this automaton model to be expressively equivalent to context-free ω-languages in the unweighted case. Furthermore, semiring-weighted simple ω-pushdown automata recognize all ω-algebraic series.
Here, we consider ω-valuation monoids as weight structures. As a first result, we prove that for this weight structure and for simple ω-pushdown automata, Büchi-acceptance and Muller-acceptance are expressively equivalent. In our second result, we derive a Nivat theorem for these automata stating that the behaviors of weighted ω-pushdown automata are precisely the projections of very simple ω-series restricted to ω-context-free languages. The third result is a weighted logic with the same expressive power as the new automaton model. To prove the equivalence, we use a similar result for weighted nested ω-word automata and apply our present result of expressive equivalence of Muller and Büchi acceptance.
BibTeX - Entry
@InProceedings{droste_et_al:LIPIcs:2020:13285,
author = {Manfred Droste and Sven Dziadek and Werner Kuich},
title = {{Nivat-Theorem and Logic for Weighted Pushdown Automata on Infinite Words}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {44:1--44:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13285},
URN = {urn:nbn:de:0030-drops-132850},
doi = {10.4230/LIPIcs.FSTTCS.2020.44},
annote = {Keywords: Weighted automata, Pushdown automata, Infinite words, Weighted logic}
}
|
Keywords: |
|
Weighted automata, Pushdown automata, Infinite words, Weighted logic |
|
Collection: |
|
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
04.12.2020 |
