Systolic tree acceptors
Karel Ii Culik, Arto Salomaa, Derick Wood (1984)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Displaying similar documents to “Complexity of E0L structural equivalence”
Systolic tree acceptors
Yield-languages recognized by alternating tree recognizers
Kai Salomaa (1988)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
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...
Decidability of equivalence for a class of non-deterministic tree transducers
Yves André, Max Dauchet (1994)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Subtree Matching by Pushdown Automata
Tomáš Flouri, Jan Janoušek, Bořivoj Melichar (2010)
Computer Science and Information Systems
Similarity:
First-order properties of trees, star-free expressions, and aperiodicity
Uschi Heuter (1991)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Tree algebra of sofic tree languages
Nathalie Aubrun, Marie-Pierre Béal (2014)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We consider the languages of finite trees called tree-shift languages which are factorial extensible tree languages. These languages are sets of factors of subshifts of infinite trees. We give effective syntactic characterizations of two classes of regular tree-shift languages: the finite type tree languages and the tree languages which are almost of finite type. Each class corresponds to a class of subshifts of trees which is invariant by conjugacy. For this goal, we define a tree algebra...
E-unification by means of tree tuple synchronized grammars.
Limet, Sébastien, Réty, Pierre (1997)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
A unified Framework to compute over tree synchronized grammars and primal grammars.
Saubion, Frédéric, Stéphan, Igor (2002)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
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...