Skip navigation
Skip navigation

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

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]

CollectionsANU Research Publications
Date published: 2014
Type: Journal article
URI: http://hdl.handle.net/1885/74055
Source: Theoretical Computer Science
DOI: 10.1016/j.tcs.2014.02.036

Download

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:  20 July 2017/ Responsible Officer:  University Librarian/ Page Contact:  Library Systems & Web Coordinator