Project without external funding
RestartAutomaten auf Baeumen
Project Details
Project duration: 09/2006–12/2010
Abstract
Originally restarting automata were introduced to model the socalled '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 reductions (e.g., treebanks). 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 wellknown 'syntax trees' and 'dependency trees'. Therefore it is only natural to extend the notion of restarting automaton from strings to trees. Here we investigate such a generalization: the restarting tree automaton.Publications
2009  Otto, F., Stamer, H., 2009. Singlepath restarting tree automata, in: Bozapalidis, S. and R. (Hrsg.), Algebraic Informatics, CAI 2009, Proc. Springer, Berlin, S. 324–341.  2008   2007  Stamer, H., Otto, F., 2007. Restarting Tree Automata, in: van Leeuwen, J. (Hrsg.), SOFSEM 2007: Theory and Practise of Computer Science, Proc. Springer, Berlin, S. 510–521.  2007  Stamer, H., Otto, F., 2007. Restarting tree automata and linear contextfree tree languages, in: Bozapalidis, S. and R. (Hrsg.), Algebraic Informatics, CAI 2007, Proceedings. Springer, Berlin, S. 275–289. 
