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:
Displaying similar documents to “Tree transformations defined by hypersubstitutions”
E-unification by means of tree tuple synchronized grammars.
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...
On the normal disconnection of a tree
A. Kośliński (1987)
Applicationes Mathematicae
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:
Deducing Properties of Trees From Their Matula Numbers
Ivan Gutman, Yeong-Nan Yeh (1993)
Publications de l'Institut Mathématique
Similarity:
A note on the minimalization of tree-automata
Bruno Courcelle (1988)
Banach Center Publications
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...
Completely Independent Spanning Trees in (Partial) k-Trees
Masayoshi Matsushita, Yota Otachi, Toru Araki (2015)
Discussiones Mathematicae Graph Theory
Similarity:
Two spanning trees T1 and T2 of a graph G are completely independent if, for any two vertices u and v, the paths from u to v in T1 and T2 are internally disjoint. For a graph G, we denote the maximum number of pairwise completely independent spanning trees by cist(G). In this paper, we consider cist(G) when G is a partial k-tree. First we show that [k/2] ≤ cist(G) ≤ k − 1 for any k-tree G. Then we show that for any p ∈ {[k/2], . . . , k − 1}, there exist infinitely many k-trees G such...
Subtree Matching by Pushdown Automata
Tomáš Flouri, Jan Janoušek, Bořivoj Melichar (2010)
Computer Science and Information Systems
Similarity:
On A-Trees
Đuro Kurepa (1968)
Publications de l'Institut Mathématique
Similarity:
-trees and normalization of pseudogroups.
Rimlinger, Frank (1992)
Experimental Mathematics
Similarity:
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...