Displaying similar documents to “On the syntactic complexity of tree series”

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

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

Deciding inclusion of set constants over infinite non-strict data structures

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

Tree Automata and Automata on Linear Orderings

Véronique Bruyère, Olivier Carton, Géraud Sénizergues (2009)

RAIRO - Theoretical Informatics and Applications

Similarity:

We show that the inclusion problem is decidable for rational languages of words indexed by scattered countable linear orderings. The method leans on a reduction to the decidability of the monadic second order theory of the infinite binary tree [9].