Show simple item record

dc.contributor.authorLehmann, K
dc.contributor.authorPenaloza, R
dc.date.accessioned2015-11-02T13:55:49Z
dc.date.available2015-11-02T13:55:49Z
dc.date.issued2014
dc.identifier.issn0304-3975
dc.identifier.urihttp://dx.doi.org/10.1016/j.tcs.2014.02.036
dc.identifier.urihttp://www.sciencedirect.com/science/article/pii/S0304397514001625
dc.identifier.urihttp://hdl.handle.net/10863/1430
dc.description.abstractSeveral 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. 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.en_US
dc.publisherElsevieren_US
dc.titleThe complexity of computing the behaviour of lattice automata on infinite treesen_US
dc.typeArticleen_US
dc.date.updated2015-11-02T11:22:48Z
dc.journal.titleTheoretical Computer Science
dc.description.fulltextopenen_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record