Projekt 19 - Restart-Automaten auf Bäumen

(Beginn: 09/2006-12/2009)

Originally restarting automata were introduced to model the so-called analysis by reduction, which is a technique used in linguistics to analyze sentences of a natural language that has free word order. This technique consists in a stepwise simplification of a sentence in such a way that the syntactical correctness or incorrectness is not affected. After a finite number of steps either a correct simple sentence is obtained, or the core of an error is detected. Analysis by reduction is usually presented by finite samples of sentences of a natural language and by sequences of their correct reduction (e.g., tree-banks). Also many variants of restarting automata have been introduced and studied. All these variants work on linear text, that is, on strings, despite the fact that in linguistics (as well as in formal language theory and its applications) trees are often used to describe sentences of a language together with some structural information. Here we just mention the well-known syntax trees and dependency trees. Therefore it is only natural to extend the notion of restarting automata from strings to trees. Here we investigate such a generalization: the restarting tree automaton.

Mitarbeiter:

Heiko Stamer

Veröffentlichungen:

Otto, F. and Stamer, H.:
Single-path restarting tree automata.
In Bozapalidis, S. and Rahonis, G., editors, Algebraic Informatics, CAI 2009, Proc. Lecture Notes in Computer Science 5725, pages 324--341, Springer, Berlin, 2009.
Stamer, H.:
Restarting Tree Automata - Formal Properties and Possible Variations.
Kassel University Press, Kassel 2008.
Stamer, H. and Otto, F.:
Restarting tree automata and linear context-free tree languages.
In Bozapalidis, S. and Rahonis, G., editors, Algebraic Informatics, CAI 2007, Proc. , Lecture Notes in Computer Science 4728, pages 275-289, Springer, Berlin, 2007.
Stamer, H. and Otto, F.:
Restarting tree automata.
In van Leeuwen, J., Italiano, G.F., van der Hoek, W., Meinel, C., Sack, H. and Plásil, F., editors, SOFSEM 2007: Theory and Practise of Computer Science, Proc., Lecture Notes in Computer Science 4362, pages 510--521, Springer, Berlin, 2007.