umu.sePublications
Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
An efficient best-trees algorithm for weighted tree automata over the tropical semiring
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
Umeå University, Faculty of Science and Technology, Department of Computing Science. (Natural and Formal Languages)
2015 (English)In: Proc. 9th International Conference on Language and Automata Theory and Applications / [ed] Adrian-Horia Dediu, Enrico Formenti, Carlos Martín-Vide, and Bianca Truthe, Springer, 2015, 97-108 p.Conference paper, Published paper (Refereed)
Abstract [en]

We generalise a search algorithm by Mohri and Riley from strings to trees. The original algorithm takes as input a weighted automaton M over the tropical semiring, together with an integer N, and outputs N strings of minimal weight with respect to M. In our setting, M defines a weighted tree language, again over the tropical semiring, and the output is a set of N trees with minimal weight. We prove that the algorithm is correct, and that its time complexity is a low polynomial in N and the relevant size parameters of M.

Place, publisher, year, edition, pages
Springer, 2015. 97-108 p.
Series
Lecture Notes in Computer Science, ISSN 0302-9743 ; 8977
National Category
Computer Science
Research subject
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-96680DOI: 10.1007/978-3-319-15579-1_7OAI: oai:DiVA.org:umu-96680DiVA: diva2:766062
Conference
9th International Conference on Language and Automata Theory and Applications, LATA 2015, Nice, France, March 2-6, 2015
Projects
MICO: Media in Context
Funder
EU, FP7, Seventh Framework Programme, 610480
Available from: 2014-11-25 Created: 2014-11-25 Last updated: 2015-12-03Bibliographically approved

Open Access in DiVA

No full text

Other links

Publisher's full text

Search in DiVA

By author/editor
Björklund, JohannaDrewes, FrankZechner, Niklas
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 332 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf