Extendable local partial clones
type: Item
instance of: scholarly article
title: Extendable local partial clones
zbMATH Open document ID: 1144.08005
published in: Discrete Mathematics
publication date: 2008-07-11T00:00:00Z
review text: Let \(E\) be an infinite set, \(O(E)\), \(P(E)\) be the sets of all everywhere defined (respectively partial) operations on the set \(E\), \([F]\) be the clone (partial clone) generated by a set of operations \(F\subseteq O(E)\) (\(F\subseteq P(E)\)), Loc\((F)\) be the local closure of the set \(F\), defined by \(g\in \text{Loc}(F)\) iff for every finite non-single subset \(A\subset E\) such that the restriction \(g|_{A}\) is non-void there exists \(f\in[F]\) such that \(g|_{A}=f\) on Dom\((g|_{A})\). A (partial) clone \(\mathbf{A}\) is local if Loc\((\mathbf{A})=\mathbf{A}\). It is shown that a local partial clone \(\mathbf{B}\) is maximal in \(P(E)\) iff for every finite non-single subset \(A\subset E\) the restriction \(\mathbf{B}|_{A}\) either is the full partial clone \(P(A)\) or (at least for some \(A\)) is a maximal partial clone on \(A\). Let Pol\((\mathfrak{R}\)) denote the set of all partial operations which preserve a set of relations \(\mathfrak{R}\) defined on \(E\). A partial operation \(f\in\text{Pol}(\mathfrak{R})\) with finite domain is called extendable in a local partial clone \(\mathbf{B}=\text{Pol}(\mathfrak{R})\) if there exists \(g\in\mathbf{B}\cap O(E)\) such that \(f=g\) on \(\text{Dom}(f)\); a local partial clone is extendable if every partial operation from it with finite domain is extendable. It is shown that for a single relation \(R\) on the countable set \(E\) the partial clone \(\mathbf{B}=\text{Pol}(\mathfrak{R})\) is extendable iff each relation constructed by a \((\exists,\&,=)\)-formula from \(R\) is equivalent to a relation constructed by some \((\&,=)\)-formula. All partial orders \(x\leq y\) on the countable set such that the partial clone \(\text{Pol}(x\leq y)\) is extendable are characterized and a description of all extendable maximal local partial clones on the countable set is obtained.
reviewed by: Jaak Henno
Mathematics Subject Classification ID: 08A40
Mathematics Subject Classification ID: 08A55
zbMATH DE Number: 5300633
zbMATH Keywords: local partial clone
zbMATH Keywords: maximal clone
zbMATH Keywords: extendability of partial operations
zbMATH Keywords: extendable partial clone
author: Boris A. Romov
MaRDI profile type: Publication
full work available at URL: j.disc.2007.07.080
OpenAlex ID: W1968084296
cites work: Q5613923
cites work: Error-free and best-fit extensions of partially defined Boolean functions
cites work: Q5515373
cites work: Q3491589
cites work: Completeness theory for finite partial algebras
cites work: Q3890691
cites work: The algebras of partial functions and their invariants
cites work: Q3754597
cites work: Extension of not everywhere defined functions of many-valued logic
cites work: Q4007503
cites work: Maximal local classes of partial functions of infinite-valued logic
cites work: Maximal finitely defined subalgebras of partial functions of infinite- valued logic
cites work: Q5597508
cites work: Q3659773
cites work: Local completeness. I
cites work: Q4168658
DOI: 10.1016/J.DISC.2007.07.080
description: scientific article; zbMATH DE number 5300633