umu.sePublikationer
Ändra sökning
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf
Bisimulation minimization of tree automata
Umeå universitet, Teknisk-naturvetenskaplig fakultet, Institutionen för datavetenskap.
2007 (Engelska)Ingår i: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 18, nr 4, s. 699-713Artikel i tidskrift (Refereegranskat) Published
Abstract [en]

We extend an algorithm by Paige and Tarjan that solves the coarsest stable refinement problem to the domain of trees. The algorithm is used to minimize nondeterministic tree automata (NTA) with respect to bisimulation. We show that our algorithm has an overall complexity of $O(\hat{r} m \log n)$, where $\hat{r}$ is the maximum rank of any symbol in the input alphabet, m is the total size of the transition table, and n is the number of states.

Ort, förlag, år, upplaga, sidor
2007. Vol. 18, nr 4, s. 699-713
Nyckelord [en]
bisimulation, minimization, tree automata
Identifikatorer
URN: urn:nbn:se:umu:diva-2415OAI: oai:DiVA.org:umu-2415DiVA, id: diva2:140396
Tillgänglig från: 2007-05-16 Skapad: 2007-05-16 Senast uppdaterad: 2018-06-09Bibliografiskt granskad
Ingår i avhandling
1. Contributions to the theory and applications of tree languages
Öppna denna publikation i ny flik eller fönster >>Contributions to the theory and applications of tree languages
2007 (Engelska)Doktorsavhandling, sammanläggning (Övrigt vetenskapligt)
Abstract [en]

This thesis is concerned with theoretical as well as practical aspects of tree languages. It consists of an introduction and eight papers, organised into three parts. The first part is devoted to algorithmic learning of regular tree languages, the second part to bisimulation minimisation of tree automata, and the third part to tree-based generation of music. We now summarise the contributions made in each part.

In Part I, an inference algorithm for regular tree languages is presented. The algorithm is a generalisation of a previous algorithm by Angluin, and the learning task is to derive, with the aid of a so-called MAT-oracle, the minimal (partial and deterministic) finite tree automaton M that recognises the target language U over some ranked alphabet Σ. The algorithm executes in time O(|Q| |δ| (m + |Q|)), where Q and δ are the set of states and the transition table of M , respectively, r is the maximal rank of any symbol in Σ, and m is the maximum size of any answer given by the oracle. This improves on a similar algorithm by Sakakibara as dead states are avoided both in the learning phase and in the resulting automaton. Part I also describes a concrete implementation which includes two extensions of the basic algorithm.

In Part II, bisimulation minimisation of nondeterministic weighted tree automata (henceforth, wta) is introduced in general, and for finite tree automata (which can be seen as wta over the Boolean semiring) in particular. The concepts of backward and forward bisimulation are extended to wta, and efficient minimisation algorithms are developed for both types of bisimulation. In the special case where the underlying semiring of the input automaton is either cancellative or Boolean, these minimisation algorithms can be further optimised by adapting existing partition refinement algorithms by Hopcroft, Paige, and Tarjan. The implemented minimisation algorithms are demonstrated on a typical task in natural language processing.

In Part III, we consider how tree-based generation can be applied to algorithmic composition. An algebra is presented whose operations act on musical pieces, and a system capable of generating simple musical pieces is implemented in the software Treebag: starting from input which is either generated by a regular tree grammar or provided by the user via a digital keyboard, a number of top-down tree transducers are applied to generate a tree over the operations provided by the music algebra. The evaluation of this tree yields the musical piece generated.

Ort, förlag, år, upplaga, sidor
Umeå: Datavetenskap, 2007. s. 32
Serie
Report / UMINF, ISSN 0348-0542 ; 07.07
Nyckelord
regular tree languages, tree series, algorithmic learning, MAT-learning, bisimulation minimisation, tree-based generation, algorithmic composition, music algebra
Nationell ämneskategori
Datavetenskap (datalogi)
Identifikatorer
urn:nbn:se:umu:diva-1152 (URN)978-91-7264-336-9 (ISBN)
Disputation
2007-09-07, MA121, MIT huset, Umeå Universitet, Umeå, 13:00 (Engelska)
Opponent
Handledare
Tillgänglig från: 2007-05-16 Skapad: 2007-05-16 Senast uppdaterad: 2018-06-09Bibliografiskt granskad

Open Access i DiVA

Fulltext saknas i DiVA

Övriga länkar

http://search.ebscohost.com/login.aspx?direct=true&db=buh&AN=25946240&loginpage=Login.asp&site=ehost-live&scope=site

Personposter BETA

Högberg, Johanna

Sök vidare i DiVA

Av författaren/redaktören
Högberg, Johanna
Av organisationen
Institutionen för datavetenskap
I samma tidskrift
International Journal of Foundations of Computer Science

Sök vidare utanför DiVA

GoogleGoogle Scholar

urn-nbn

Altmetricpoäng

urn-nbn
Totalt: 802 träffar
RefereraExporteraLänk till posten
Permanent länk

Direktlänk
Referera
Referensformat
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Annat format
Fler format
Språk
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Annat språk
Fler språk
Utmatningsformat
  • html
  • text
  • asciidoc
  • rtf