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:
Yves André, Max Dauchet (1994)
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:
Kai Salomaa, Derick Wood, Sheng Yu (1995)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
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...
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...
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.
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...
H. J. Olivié (1982)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
André Arnold (1999)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity: