VARIETIES OF REGULAR ALGEBRAS AND UNRANKED TREE LANGUAGES
Journal Title: Discussiones Mathematicae - General Algebra and Applications - Year 2016, Vol 36, Issue 2
Abstract
In this paper we develop a variety theory for unranked tree languages and unranked algebras. In an unranked tree any symbol may label a node with any number of successors. Such trees appear in markup languages such as XML and as syntactic descriptions of natural languages. In the corresponding algebras each operation is defined for any number of arguments, but in the regular algebras used as tree recognizers the operations are finite-state computable. We develop the basic theory of regular algebras for a setting in which algebras over different operator alphabets are considered together. Using syntactic algebras of unranked tree languages we establish a bijection between varieties of unranked tree languages and varieties of regular algebras. As varieties of unranked tree languages are usually defined by means of congruences of term algebras, we introduce also varieties of congruences and a general device for defining such varieties. Finally, we show that the natural unranked counterparts of several varieties of ranked tree languages form varieties in our sense.
Authors and Affiliations
Magnus Steinby, Eija Jurvanen, Antonio Cano
Keywords
Related Articles
- EP ID EP304524
- DOI -
- Views 48
- Downloads 0
ALL REGULAR-SOLID VARIETIES OF IDEMPOTENT SEMIRINGS
The lattice of all regular-solid varieties of semirings splits in two complete sublattices: the sublattice of all idempotent regular-solid varieties of semirings and the sublattice of all normal regular-solid varieties o...
On balanced order relations and the normal hull of completely simple semirings
In [1] the authors proved that a semiring S is a completely simple semiring if and only if S is isomorphic to a Rees matrix semiring over a skew-ring R with sandwich matrix P and index sets I and Λ which are bands under...
Intervals of certain classes of Z-matrices
Let A and B be M-matrices satisfying A ≤ B and J = [A, B] be the set of all matrices C such that A ≤ C ≤ B, where the order is component wise. It is rather well known that if A is an M-matrix and B is an invertible Mmatr...
Weak-hyperlattices derived from fuzzy congruences
In this paper we explore the connections between fuzzy congruence relations, fuzzy ideals and homomorphisms of hyperlattices. Indeed, we introduce the concept of fuzzy quotient set of hyperlattices as it was done in the...
On the intersection graphs of ideals of direct product of rings
In this paper we first calculate the number of vertices and edges of the intersection graph of ideals of direct product of rings and fields. Then we study Eulerianity and Hamiltonicity in the intersection graph of ideals...