Subtree Matching by Pushdown Automata
Tomáš Flouri, Jan Janoušek, Bořivoj Melichar (2010)
Computer Science and Information Systems
Similarity:
Tomáš Flouri, Jan Janoušek, Bořivoj Melichar (2010)
Computer Science and Information Systems
Similarity:
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...
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...
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...
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...
Bruno Courcelle (1988)
Banach Center Publications
Similarity:
Manfred Schmidt-Schauss, David Sabel, Marko Schütz (2007)
RAIRO - Theoretical Informatics and Applications
Similarity:
Various static analyses of functional programming languages that permit infinite data structures make use of set constants like , , and , denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. ...
Karel Ii Culik, Arto Salomaa, Derick Wood (1984)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Limet, Sébastien, Réty, Pierre (1997)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
André Arnold (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity: