Project without external funding

Restart-Automaten auf Baeumen

Project Details
Project duration: 09/200612/2010

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 reductions (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 automaton from strings to trees. Here we investigate such a generalization: the restarting tree automaton.

Principal Investigator


Last updated on 2017-11-07 at 13:45