The complexity of computing the behaviour of lattice automata on infinite trees
-
Altmetric Citations
Lehmann, Karsten; Peñaloza, Rafael
Description
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 Bu¨chi automata working on (unlabelled) 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...[Show more]
dc.contributor.author | Lehmann, Karsten | |
---|---|---|
dc.contributor.author | Peñaloza, Rafael | |
dc.date.accessioned | 2015-12-13T22:27:42Z | |
dc.identifier.issn | 0304-3975 | |
dc.identifier.uri | http://hdl.handle.net/1885/74055 | |
dc.description.abstract | 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 Bu¨chi automata working on (unlabelled) 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. | |
dc.publisher | Elsevier | |
dc.source | Theoretical Computer Science | |
dc.title | The complexity of computing the behaviour of lattice automata on infinite trees | |
dc.type | Journal article | |
local.description.notes | Imported from ARIES | |
local.identifier.citationvolume | 534 | |
dc.date.issued | 2014 | |
local.identifier.absfor | 080201 - Analysis of Algorithms and Complexity | |
local.identifier.ariespublication | U3488905xPUB3946 | |
local.type.status | Published Version | |
local.contributor.affiliation | Lehmann, Karsten, College of Engineering and Computer Science, ANU | |
local.contributor.affiliation | Peñaloza, Rafael, Technical University of Dresden | |
local.description.embargo | 2037-12-31 | |
local.bibliographicCitation.startpage | 53 | |
local.bibliographicCitation.lastpage | 68 | |
local.identifier.doi | 10.1016/j.tcs.2014.02.036 | |
local.identifier.absseo | 970108 - Expanding Knowledge in the Information and Computing Sciences | |
dc.date.updated | 2015-12-11T08:33:57Z | |
local.identifier.scopusID | 2-s2.0-84904116333 | |
local.identifier.thomsonID | 000336354000005 | |
Collections | ANU Research Publications |
Download
File | Description | Size | Format | Image |
---|---|---|---|---|
01_Lehmann_The_complexity_of_computing_2014.pdf | 338.78 kB | Adobe PDF | Request a copy |
Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.
Updated: 17 November 2022/ Responsible Officer: University Librarian/ Page Contact: Library Systems & Web Coordinator