Displaying similar documents to “On the solidity of general varieties of tree languages”

Nd-solid varieties

Klaus Denecke, Prisana Glubudom (2007)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

A non-deterministic hypersubstitution maps any operation symbol of a tree language of type τ to a set of trees of the same type, i.e. to a tree language. Non-deterministic hypersubstitutions can be extended to mappings which map tree languages to tree languages preserving the arities. We define the application of a non-deterministic hypersubstitution to an algebra of type τ and obtain a class of derived algebras. Non-deterministic hypersubstitutions can also be applied to equations of...

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

The lattice of varieties of fibered automata

Anna Mućka (2006)

Discussiones Mathematicae - General Algebra and Applications

Similarity:

The class of all fibered automata is a variety of two-sorted algebras. This paper provides a full description of the lattice of varieties of fibred automata.

On geometry of binary symmetric models of phylogenetic trees

Weronika Buczyńska, Jaroslaw A. Wiśniewski (2007)

Journal of the European Mathematical Society

Similarity:

We investigate projective varieties which are binary symmetric models of trivalent phylogenetic trees. We prove that they have Gorenstein terminal singularities and are Fano varieties of index 4 and dimension equal to the number of edges of the tree in question. Moreover any two such varieties which are of the same dimension are deformation equivalent, that is, they are in the same connected component of the Hilbert scheme of the projective space. As an application we provide a simple...

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

On varieties of orgraphs

Alfonz Haviar, Gabriela Monoszová (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper we investigate varieties of orgraphs (that is, oriented graphs) as classes of orgraphs closed under isomorphic images, suborgraph identifications and induced suborgraphs, and we study the lattice of varieties of tournament-free orgraphs.