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 47
- Downloads 0
NON-DETERMINISTIC LINEAR HYPERSUBSTITUTIONS
A non-deterministic hypersubstitution maps operation symbols to sets of terms of the corresponding arity. A non-deterministic hypersubstitution of type τ is said to be linear if it maps any operation symbol to a set of l...
SOME HOMOLOGICAL PROPERTIES OF SKEW P BW EXTENSIONS ARISING IN NON-COMMUTATIVE ALGEBRAIC GEOMETRY
In this short paper we study for the skew P BW (Poincar-Birkhoff-Witt) extensions some homological properties arising in non-commutative algebraic geometry, namely, Auslander-Gorenstein regularity, Cohen-Macaulayness and...
ON THE SECOND SPECTRUM OF LATTICE MODULES
The second spectrum Specs(M) is the collection of all second elements of M. In this paper, we study the topology on Specs(M), which is a generalization of the Zariski topology on the prime spectrum of lattice modules. Be...
Trace inequalities for positive semidefinite matrices
Certain trace inequalities for positive definite matrices are generalized for positive semidefinite matrices using the notion of the group generalized inverse.
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...