umu.sePublications
Change search

Contributions to the theory and applications of tree languages
Umeå University, Faculty of Science and Technology, Department of Computing Science.
2007 (English)Doctoral thesis, comprehensive summary (Other academic)
##### 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 ﬁrst 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) ﬁnite 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 ﬁnite 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 eﬃcient 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 reﬁnement 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.

##### Place, publisher, year, edition, pages
Umeå: Datavetenskap , 2007. , 32 p.
##### Series
Report / UMINF, ISSN 0348-0542 ; 07.07
##### Keyword [en]
regular tree languages, tree series, algorithmic learning, MAT-learning, bisimulation minimisation, tree-based generation, algorithmic composition, music algebra
Computer Science
##### Identifiers
ISBN: 978-91-7264-336-9OAI: oai:DiVA.org:umu-1152DiVA: diva2:140401
##### Public defence
2007-09-07, MA121, MIT huset, Umeå Universitet, Umeå, 13:00 (English)
##### Supervisors
Available from: 2007-05-16 Created: 2007-05-16 Last updated: 2009-10-23Bibliographically approved
##### List of papers
1. Learning a regular tree language from a teacher
Open this publication in new window or tab >>Learning a regular tree language from a teacher
2003 (English)In: Developments in Language Theory: 7th International Conference, DLT 2003 Szeged, Hungary, July 7-11, 2003 Proceedings, 2003, 279-291 p.Chapter in book (Other academic)
##### Identifiers
urn:nbn:se:umu:diva-2412 (URN)
Available from: 2007-05-16 Created: 2007-05-16 Last updated: 2016-03-01Bibliographically approved
2. Query Learning of Regular Tree Languages: How to Avoid Dead States
Open this publication in new window or tab >>Query Learning of Regular Tree Languages: How to Avoid Dead States
2007 (English)In: Theory of Computing Systems, ISSN 1432-4350, Vol. 40, no 2, 163-185 p.Article in journal (Refereed) Published
##### Abstract [en]

We generalize an inference algorithm by Angluin, that learns a regular string language from a "minimally adequate teacher", to regular tree languages. The (deterministic bottom-up) finite tree automaton constructed by the learning algorithm is the minimal partial one recognizing the unknown language. This improves a similar algorithm proposed by Sakakibara by avoiding dead states both in the resulting automaton and the learning phase, which also leads to a considerable improvement with respect to efficiency.

##### Identifiers
urn:nbn:se:umu:diva-9267 (URN)10.1007/s00224-005-1233-3 (DOI)
Available from: 2008-03-17 Created: 2008-03-17 Last updated: 2009-10-22Bibliographically approved
3. Extensions of a MAT Learner for Regular Tree Languages
Open this publication in new window or tab >>Extensions of a MAT Learner for Regular Tree Languages
2006 (English)In: Proceedings of SAIS 2006: 23rd Annual Workshop of the Swedish Artificial Intelligence Society, Umeå: Swedish Artificial Intelligence Society - SAIS , 2006, 35-44 p.Conference paper (Refereed)
##### Abstract [en]

In an earlier paper, we proposed a learning algorithm for regular tree languages in the Minimal Adequate Teacher model and investigated its complexity from a theoretical  perspective. Here, we focus on more practical issues. We discuss a concrete implementation made available on the web, which includes two extensions of the basic algorithm. In the paper, the usefulness of these extensions is studied in an experimental setting, by running the variants of the algorithm against target languages with different characteristics.

##### Place, publisher, year, edition, pages
Umeå: Swedish Artificial Intelligence Society - SAIS, 2006
##### Series
Report / UMINF, ISSN 0348-0542 ; 19
##### Identifiers
urn:nbn:se:umu:diva-8406 (URN)
Available from: 2008-01-21 Created: 2008-01-21 Last updated: 2009-10-22Bibliographically approved
4. Bisimulation minimization of tree automata
Open this publication in new window or tab >>Bisimulation minimization of tree automata
2007 (English)In: International Journal of Foundations of Computer Science, ISSN 0129-0541, Vol. 18, no 4, 699-713 p.Article in journal (Refereed) 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.

##### Keyword
bisimulation, minimization, tree automata
##### Identifiers
urn:nbn:se:umu:diva-2415 (URN)
Available from: 2007-05-16 Created: 2007-05-16 Last updated: 2009-10-23Bibliographically approved
5. Backward and forward bisimulation minimisation of tree automata
Open this publication in new window or tab >>Backward and forward bisimulation minimisation of tree automata
2007 (English)In: Implementation and Application of Automata: 12th International Conference, CIAA 2007, 2007Conference paper (Refereed)
##### Abstract [en]

We improve an existing bisimulation minimisation algorithm for tree automata by introducing backward and forward bisimulations and developing minimisation algorithms for them. Minimisation via forward bisimulation is effective for deterministic automata and faster than the previous algorithm. Minimisation via backward bisimulation generalises the previous algorithm and is thus more effective but just as fast. We demonstrate implementations of these algorithms on a typical task in natural language processing.

##### Series
, Lecture notes in computer science, ISSN 0302-9743
##### Identifiers
urn:nbn:se:umu:diva-2416 (URN)
Available from: 2007-05-16 Created: 2007-05-16Bibliographically approved
6. Bisimulation minimisation for weighted tree automata
Open this publication in new window or tab >>Bisimulation minimisation for weighted tree automata
2007 (English)In: Developments in Language Theory: 11th International Conference, DLT 2007, 2007Conference paper (Refereed)
##### Abstract [en]

We generalise existing forward and backward bisimulation minimisation algorithms for tree automata to weighted tree automata. The obtained algorithms work for all semirings and retain the time complexity of their unweighted variants for all additively cancellative semirings. On all other semirings the time complexity is slightly higher (linear instead of logarithmic in the number of states). We discuss implementations of these algorithms on a typical task in natural language processing.

##### Series
, Lecture Notes in Computer Science, ISSN 0302-9743
##### Identifiers
urn:nbn:se:umu:diva-2417 (URN)0302-9743 (ISBN)
Available from: 2007-05-16 Created: 2007-05-16Bibliographically approved
7. Wind in the Willows: generating music by means of tree transducers
Open this publication in new window or tab >>Wind in the Willows: generating music by means of tree transducers
2006 (English)In: Implementation and Application of Automata: 10th International Conference, CIAA 2005, Sophia Antipolis, France, June 27-29, 2005, Revised Selected Papers, Springer Berlin: Heidelberg , 2006, 153-162 p.Chapter in book (Other academic)
##### Abstract [en]

We implement a rule-based system for algorithmic composition. This system, that we call Willow, resides in the Treebag environment and consists of a sequence of formal devices, familiar from the field of tree grammars and tree transducers. Since these devices are well studied, we can apply known results to derive the descriptive complexity of the system as a whole.

##### Place, publisher, year, edition, pages
Springer Berlin: Heidelberg, 2006
##### Identifiers
urn:nbn:se:umu:diva-2418 (URN)10.1007/11605157 (DOI)
Available from: 2007-05-16 Created: 2007-05-16Bibliographically approved
8. An Algebra for Tree-Based Music Generation
Open this publication in new window or tab >>An Algebra for Tree-Based Music Generation
2007 (English)In: Algebraic Informatics: 2nd international conference, CAI 2007, Berlin: Springer , 2007, 172-188 p.Conference paper (Refereed)
##### Abstract [en]

We present an algebra whose operations act on musical pieces, and show how this algebra can be used to generate music in a tree-based fashion. Starting from input which is either generated by a regular tree grammar or provided by the user via a digital keyboard, a sequence of tree transducers is applied to generate a tree over the operations provided by the music algebra. The evaluation of this tree yields the musical piece generated.

##### Place, publisher, year, edition, pages
Berlin: Springer, 2007
##### Series
, Lecture Notes in Computer Science, ISSN 0302-9743 (Print) 1611-3349 (Online) ; 4728
##### Identifiers
urn:nbn:se:umu:diva-8408 (URN)10.1007/978-3-540-75414-5 (DOI)978-3-540-75413-8 (ISBN)
Available from: 2008-01-21 Created: 2008-01-21 Last updated: 2009-10-23Bibliographically approved

#### Open Access in DiVA

##### File information
File name FULLTEXT01.pdfFile size 415 kBChecksum MD5
cd8b01064983f406eedf60aaa36eb5c19fa67d38674534b389f1688358d1ae2aa87652e9
Type fulltextMimetype application/pdf

#### Search in DiVA

Högberg, Johanna
##### By organisation
Department of Computing Science
Computer Science