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:
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...
Arnaud Carayol, Christof Löding, Damian Niwinski, Igor Walukiewicz (2010)
Open Mathematics
Similarity:
We give a new proof showing that it is not possible to define in monadic second-order logic (MSO) a choice function on the infinite binary tree. This result was first obtained by Gurevich and Shelah using set theoretical arguments. Our proof is much simpler and only uses basic tools from automata theory. We show how the result can be used to prove the inherent ambiguity of languages of infinite trees. In a second part we strengthen the result of the non-existence of an MSO-definable...
Limet, Sébastien, Réty, Pierre (1997)
Discrete Mathematics and Theoretical Computer Science. DMTCS [electronic only]
Similarity:
Bruno Courcelle (1988)
Banach Center Publications
Similarity:
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...
Chaudhuri, R., Höft, H. (1991)
International Journal of Mathematics and Mathematical Sciences
Similarity:
H. J. Olivié (1982)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Karel Ii Culik, Arto Salomaa, Derick Wood (1984)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Helen Cameron, Derick Wood (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity: