The partial clone of linear tree languages

DOI10.1134/S0037446619030121MaRDI QIDQ2332072zbMATH OpenOpenAlexWikidataFDO

Authors N. Lekkoksung, Klaus Denecke

Publication date 1 November 2019

Published in Siberian Mathematical Journal (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1134/s0037446619030121

zbMATH Keywords

clonelinear hypersubstitutionlinear termlinear tree languagenondeterministic linear hypersubstitutionpartial clone

Mathematics Subject Classification ID

Operations and polynomials in algebraic structures, primal algebras (08A40) Partial algebras (08A55) Formal languages and automata (68Q45)

Review text

Here, a tree means a term. It is called linear if every variable occurs only once. The authors define a partial superposition operation on a set of linear trees of a given type and study properties of some many-sorted partial clones that have sets of linear trees as elements and partial superpositions as fundamental operations. They prove that endomorphisms of these algebras correspond to nondeterministic linear hypersubstitutions studied by the authors in a series of previous papers.

Recommendations

• On inferring linear single-tree languages
• Semigroups of linear tree languages
• A generalized superposition of linear tree languages and products of linear tree languages
• Descendants of a recognizable tree language for sets of linear monadic term rewrite rules
• Descendants of a recognizable tree language for prefix constrained linear monadic term rewriting with position cutting strategy
• Semi-linearity, Parikh-boundedness and tree adjunct languages
• scientific article; zbMATH DE number 475413
• A Generalization of Linear Indexed Grammars Equivalent to Simple Context-Free Tree Grammars

Cites work

• FUNCTORIAL SEMANTICS OF ALGEBRAIC THEORIES
• scientific article; zbMATH DE number 3254905 (Why is no real title available?)
• Non-deterministic linear hypersubstitutions
• POWER CLONES AND NON-DETERMINISTIC HYPERSUBSTITUTIONS
• Products of tree languages
• The partial clone of linear terms

Cited in

(8)

• The partial clone of linear formulas
• On inferring linear single-tree languages
• The partial clone of linear terms
• A generalized superposition of linear tree languages and products of linear tree languages
• Clone of linear terms and clone of linear formulas
• On partial clones of \(k\)-terms
• Partial clones
• The partial clone of completely expanded terms

This page was built for publication: The partial clone of linear tree languages

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2332072)