Semantisches Browsen
Aus International Center for Computational Logic
Several logic-based decision problems have … Several logic-based decision problems have been shown to be reducible to the emptiness problem of automata. In a similar way, non-standard reasoning problems can be reduced to the computation of the behaviour of weighted automata. In this paper, we consider a variant of weighted Büchi automata working on (unlabeled) infinite trees, where the weights belong to a lattice. We analyse the complexity of computing the behaviour of this kind of automata if the underlying lattice is not distributive.</br>We show that the decision version of this problem is in ExpTime and PSpace-hard in general, assuming that the lattice operations are polynomial-time computable. If the lattice is what we call "linear-space-computable-encoded", then the upper bound can be reduced to PSpace, but the lower bound also decreases to NP-hard and co-NP-hard. We conjecture that the upper bounds provided are in fact tight.e upper bounds provided are in fact tight. +
Rafael Peñaloza Nyssen + und Karsten Lehmann +
@article{ LePe-TCS14,
author = {Karsten {Lehmann} and Rafael {Pe{\~n}aloza}},
doi = {http://dx.doi.org/10.1016/j.tcs.2014.02.036},
journal = {Theoretical Computer Science},
month = {May},
pages = {53--68},
publisher = {Elsevier},
title = {The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees},
volume = {534},
year = {2014},
}
author = {Karsten {Lehmann} and Rafael {Pe{\~n}aloza}},
doi = {http://dx.doi.org/10.1016/j.tcs.2014.02.036},
journal = {Theoretical Computer Science},
month = {May},
pages = {53--68},
publisher = {Elsevier},
title = {The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees},
volume = {534},
year = {2014},
}
Lehmann +
Karsten +
Karsten Lehmann, Rafael Peñaloza<br/> … Karsten Lehmann, Rafael Peñaloza<br/> '''[[LATPub566|The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees]]''' <br/>__NOTOC__Theoretical Computer Science, 534:53-68, May 2014<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub566|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex; "></span> [[Media:LePe-TCS14.pdf|Download]]ia:LePe-TCS14.pdf|Download]] +
Karsten Lehmann, Rafael Peñaloza<br/> … Karsten Lehmann, Rafael Peñaloza<br/> '''[[LATPub566/en|The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees]]''' <br/>__NOTOC__Theoretical Computer Science, 534:53-68, May 2014<br/><span class="fas fa-chevron-right" style="font-size: 85%;" ></span> [[LATPub566|Details]] <span class="fas fa-chevron-right" style="font-size: 85%; margin-left: 2ex;" ></span> [[Media:LePe-TCS14.pdf|Download]]ia:LePe-TCS14.pdf|Download]] +
Anzeigetitel„Anzeigetitel <span style="font-size:small;">(Display title of)</span>“ ist ein softwareseitig fest definiertes Attribut, das einen eindeutigen Anzeigetitel zu einem Objekt speichert und ihm zuweist. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees +
Zuletzt geändert„Zuletzt geändert <span style="font-size:small;">(Modification date)</span>“ ist ein softwareseitig fest definiertes Attribut, das das Datum der letzten Änderung einer Seite speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
25. März 2015, 14:34:08 +
Hat Abfrage„Hat Abfrage <span style="font-size:small;">(Has query)</span>“ ist ein softwareseitig fest definiertes Attribut, das die Metainformationen einer Abfrage als <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Subobject">Subobjekt</a> speichert. Es wird von <a rel="nofollow" class="external text" href="https://www.semantic-mediawiki.org/wiki/Help:Special_properties">Semantic MediaWiki</a> zur Verfügung gestellt.
The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees +, The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees +, The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees +, The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees +, The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees + und The Complexity of Computing the Behaviour of Lattice Automata on Infinite Trees +
