Displaying similar documents to “Tree algebra of sofic tree languages”

Nested Sibling Tree Automata

Françoise Gire, Jean-Marc Talbot (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

In the XML standard, data are represented as unranked labeled ordered trees. Regular unranked tree automata provide a useful formalism for the validation of schemas enforcing regular structural constraints on XML documents. However some concrete application contexts need the expression of more general constraints than the regular ones. In this paper we propose a new framework in which context-free style structural constraints can be expressed and validated. This framework is characterized...

Construction of tree automata from regular expressions

Dietrich Kuske, Ingmar Meinecke (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and...

Construction of tree automata from regular expressions

Dietrich Kuske, Ingmar Meinecke (2011)

RAIRO - Theoretical Informatics and Applications

Similarity:

Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud...

Learning tree languages from text

Henning Fernau (2007)

RAIRO - Theoretical Informatics and Applications

Similarity:

We study the problem of learning regular tree languages from text. We show that the framework of function distinguishability, as introduced by the author in [ (2003) 1679–1711], can be generalized from the case of string languages towards tree languages. This provides a large source of identifiable classes of regular tree languages. Each of these classes can be characterized in various ways. Moreover, we present a generic inference algorithm with polynomial update...

On the syntactic complexity of tree series

Symeon Bozapalidis, Antonios Kalampakas (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We display a complexity notion based on the syntax of a tree series which yields two distinct hierarchies, one within the class of recognizable tree series and another one in the class of non-recognizable tree series.

Tree transformations defined by hypersubstitutions

Sr. Arworn, Klaus Denecke (2001)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

Tree transducers are systems which transform trees into trees just as automata transform strings into strings. They produce transformations, i.e. sets consisting of pairs of trees where the first components are trees belonging to a first language and the second components belong to a second language. In this paper we consider hypersubstitutions, i.e. mappings which map operation symbols of the first language into terms of the second one and tree transformations defined by such hypersubstitutions....