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 36
- Downloads 0
IF-FILTERS OF PSEUDO-BL-ALGEBRAS
Characterizations of IF-filters of a pseudo-BL-algebra are established. Some related properties are investigated. The notation of prime IF- filters and a characterization of a pseudo-BL-chain are given. Homomorphisms of...
Sublattices corresponding to very true operators in commutative basic algebras
We introduce the concept of very true operator on a commutative basic algebra in a way analogous to that for fuzzy logics. We are motivated by the fact that commutative basic algebras form an algebraic axiomatization of...
CODES OVER HYPERFIELDS
In this paper, we define linear codes and cyclic codes over a finite Krasner hyperfield and we characterize these codes by their generator matrices and parity check matrices. We also demonstrate that codes over finite Kr...
Zero-divisor graphs of reduced Rickart *-rings
For a ring A with an involution ∗, the zero-divisor graph of A, Γ∗ (A), is the graph whose vertices are the nonzero left zero-divisors in A such that distinct vertices x and y are adjacent if and only if xy∗ = 0. In this...
ON THE UNRECOGNIZABILITY BY PRIME GRAPH FOR THE ALMOST SIMPLE GROUP PGL(2, 9)
The prime graph of a finite group G is denoted by Γ(G). Also G is called recognizable by prime graph if and only if each finite group H with Γ(H) = Γ(G), is isomorphic to G. In this paper, we classify all finite groups w...