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 24
- Downloads 0
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...
SYMMETRIC BI-DERIVATIONS IN ALMOST DISTRIBUTIVE LATTICES
In this paper, we introduce the concept of symmetric bi-derivation in an Almost Distributive Lattice (ADL) and derive some important properties of symmetric bi-derivations in ADLs.
SEMIGROUPS DERIVED FROM (Γ, N)-SEMIHYPERGROUPS AND T-FUNCTOR
The main purpose of this paper is to introduce the concept of (Γ, n)- semihypergroups as a generalization of hypergroups, as a generalization of nary hypergroups and obtain an exact covariant functor between the category...
On Perfectness of Intersection Graph of Ideals of ℤn
In this short paper, we characterize the positive integers n for which intersection graph of ideals of Zn is perfect.
ALL MAXIMAL COMPLETELY REGULAR SUBMONOIDS OF HypG(2)
In this paper we consider mappings σ which map the binary operation symbol f to the term σ(f) which do not necessarily preserve the arity. These mapping are called generalized hypersubstitutions of type τ = (2) and we de...