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 33
- Downloads 0
A NOTE ON ADDITIVE GROUPS OF SOME SPECIFIC TORSION-FREE RINGS OF RANK THREE AND MIXED ASSOCIATIVE RINGS
It is studied how rank two pure subgroups of a torsion-free Abelian group of rank three influences its structure and type set. In particular, the criterion for such a subgroup B to be a direct summand of a torsion-free A...
GENERALIZED PELL EQUATIONS FOR 2 × 2 MATRICES
In this paper we consider the solutions of the generalized matrix Pell equations X^2 − dY^2 = cI, where X and Y are 2 × 2 matrices over Z, d is a non-zero (positive or negative) square-free integer, c is an arbitrary int...
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...
ENUMERATION OF Γ-GROUPS OF FINITE ORDER
The concept of Γ-semigroups is a generalization of semigroups. In this paper, we consider Γ-groups and prove that every Γ-group is derived from a group then, we give the number of Γ-groups of small order.
INTRODUCING FULLY UP-SEMIGROUPS
In this paper, we introduce some new classes of algebras related to UPalgebras and semigroups, called a left UP-semigroup, a right UP-semigroup, a fully UP-semigroup, a left-left UP-semigroup, a right-left UP-semigroup,...