Displaying similar documents to “Tree Automata and Automata on Linear Orderings”

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...

Choice functions and well-orderings over the infinite binary tree

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...

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...

Systolic tree acceptors

Karel Ii Culik, Arto Salomaa, Derick Wood (1984)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity: