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 52
- Downloads 0
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...
Left Zeroid and Right Zeroid Elements of Γ-Semirings
In this paper we introduce the notion of a left zeroid and a right zeroid of -semirings. We prove that, a left zeroid of a simple -semiring M is regular if and only if M is a regular -semiring.
Jordan numbers, Stirling numbers and sums of powers
In the paper a new combinatorical interpretation of the Jordan numbers is presented. Binomial type formulae connecting both kinds of numbers mentioned in the title are given. The decomposition of the product of polynomia...
Spectra of R-Vertex Join and R-Edge Join of Two Graphs
The R-graph R(G) of a graph G is the graph obtained from G by introducing a new vertex ue for each e ∈ E(G) and making ue adjacent to both the end vertices of e. In this paper, we determine the adjacency, Laplacian and s...
The Clifford semiring congruences on an additive regular semiring
A congruence ρ on a semiring S is called a (generalized)Clifford semiring congruence if S/ρ is a (generalized)Clifford semiring. Here we characterize the (generalized)Clifford congruences on a semiring whose additive red...