Minimisation of multiplicity tree automataReport as inadecuate

Minimisation of multiplicity tree automata - Download this document for free, or read online. Document in PDF available to download.

Reference: Worrell, JB, Kiefer, S and Marusic, I et al., (2017). Minimisation of multiplicity tree automata. Logical Methods in Computer Science, 13 (1), 1-25.Citable link to this page:


Minimisation of multiplicity tree automata

Abstract: We consider the problem of minimising the number of states in a multiplicity tree automaton over the field of rational numbers. We give a minimisation algorithm that runs in polynomial time assuming unit-cost arithmetic. We also show that a polynomial bound in the standard Turing model would require a breakthrough in the complexity of polynomial identity testing by proving that the latter problem is logspace equivalent to the decision version of minimisation. The developed techniques also improve the state of the art in multiplicity word automata: we give an NC algorithm for minimising multiplicity word automata. Finally, we consider the minimal consistency problem: does there exist an automaton with a given number of states that is consistent with a given finite sample of weight-labelled words or trees? We show that, over both words and trees, this decision problem is interreducible with the problem of deciding the truth of existential first-order sentences over the field of rationals—whose decidability is a longstanding open problem.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Publisher's versionDate of acceptance:2017-03-28 Funder: Engineering and Physical Sciences Research Council   Funder: Royal Society   Notes:This work is licensed under the Creative Commons Attribution-NoDerivs License. To view a copy of this license, visit or send a letter to Creative Commons, 171 Second St, Suite 300, San Francisco, CA 94105, USA, or Eisenacher Strasse 2, 10777 Berlin, Germany

Bibliographic Details

Publisher: International Federation of Computational Logic

Publisher Website:

Journal: Logical Methods in Computer Sciencesee more from them

Publication Website:

Volume: 13

Issue: 1

Issue Date: 2017-03



Issn: 1860-5974

Uuid: uuid:c3f1fd53-73c8-4677-8fce-190434be58a7

Urn: uri:c3f1fd53-73c8-4677-8fce-190434be58a7

Pubs-id: pubs:710084

Doi: Item Description

Type: journal-article;

Version: Publisher's versionKeywords: weighted automata tree automata minimisation arithmetic circuit identity testing consistent automaton


Author: Worrell, JB - Oxford, MPLS, Computer Science Green Templeton College - - - Kiefer, S - - - Marusic, I - - - - Bibliographic Detai



Related documents