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
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 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.

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
National Category
Computer Science
Identifiers
URN: urn:nbn:se:umu:diva-1152ISBN: 978-91-7264-336-9 (print)OAI: oai:DiVA.org:umu-1152DiVA: diva2:140401
Public defence
2007-09-07, MA121, MIT huset, Umeå Universitet, Umeå, 13:00 (English)
Opponent
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, Published 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, Published 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, Published 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, Published 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

fulltext(415 kB)779 downloads
File information
File name FULLTEXT01.pdfFile size 415 kBChecksum SHA-1
674534b389f1688358d1ae2aa87652e9cd8b01064983f406eedf60aaa36eb5c19fa67d38
Type fulltextMimetype application/pdf

Authority records BETA

Högberg, Johanna

Search in DiVA

By author/editor
Högberg, Johanna
By organisation
Department of Computing Science
Computer Science

Search outside of DiVA

GoogleGoogle Scholar
Total: 779 downloads
The number of downloads is the sum of all downloads of full texts. It may include eg previous versions that are now no longer available

isbn
urn-nbn

Altmetric score

isbn
urn-nbn
Total: 580 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