The Partial Clone of Linear Tree Languages

A term, also called a tree, is said to be linear, if each variable occurs in the term only once. The linear terms and sets of linear terms, the so-called linear tree languages, play some role in automata theory and in the theory of formal languages in connection with recognizability. We define a par...

Full description

Saved in:
Bibliographic Details
Published in:Siberian mathematical journal 2019-05, Vol.60 (3), p.497-507
Main Authors: Lekkoksung, N., Denecke, K.
Format: Article
Language:English
Subjects:
Automata theory
Languages
Mathematics
Mathematics and Statistics
Superposition (mathematics)
Trees
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:A term, also called a tree, is said to be linear, if each variable occurs in the term only once. The linear terms and sets of linear terms, the so-called linear tree languages, play some role in automata theory and in the theory of formal languages in connection with recognizability. We define a partial superposition operation on sets of linear trees of a given type τ and study the properties of some many-sorted partial clones that have sets of linear trees as elements and partial superposition operations as fundamental operations. The endomorphisms of those algebras correspond to nondeterministic linear hypersubstitutions.
ISSN:0037-4466
1573-9260
DOI:10.1134/S0037446619030121