Skip navigation
Skip navigation

The complexity of computing the behaviour of lattice automata on infinite trees

Lehmann, Karsten; Peñaloza, Rafael


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]

CollectionsANU Research Publications
Date published: 2014
Type: Journal article
Source: Theoretical Computer Science
DOI: 10.1016/j.tcs.2014.02.036


File Description SizeFormat Image
01_Lehmann_The_complexity_of_computing_2014.pdf338.78 kBAdobe PDF    Request a copy

Items in Open Research are protected by copyright, with all rights reserved, unless otherwise indicated.

Updated:  19 May 2020/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator