اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدSubfunction relations defined by the clones containing all unary operations
44
0
0.0
(
0
)
تأليف
Erkko Lehtonen
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
For a class C of operations on a nonempty base set A, an operation f is called a C-subfunction of an operation g, if f = g(h_1, ..., h_n), where all the inner functions h_i are members of C. Two operations are C-equivalent if they are C-subfunctions of each other. The C-subfunction relation is a quasiorder if and only if the defining class C is a clone. The C-subfunction relations defined by clones that contain all unary operations on a finite base set are examined. For each such clone it is determined whether the corresponding partial order satisfies the descending chain condition and whether it contains infinite antichains.
قيم البحث
اقرأ أيضاً
The study of partial clones on $mathbf{2}:={0,1}$ was initiated by R. V. Freivald. In his fundamental paper published in 1966, Freivald showed, among other things, that the set of all monotone partial functions and the set of all self-dual partial fu
nctions are both maximal partial clones on $mathbf{2}$. Several papers dealing with intersections of maximal partial clones on $mathbf{2}$ have appeared after Freivald work. It is known that there are infinitely many partial clones that contain the set of all monotone self-dual partial functions on $mathbf{2}$, and the problem of describing them all was posed by some authors. In this paper we show that the set of partial clones that contain all monotone self-dual partial functions is of continuum cardinality on $mathbf{2}$.
There are continuum many clones on a three-element set even if they are considered up to emph{homomorphic equivalence}. The clones we use to prove this fact are clones consisting of emph{self-dual operations}, i.e., operations that preserve the relat
ion ${(0,1),(1,2),(2,0)}$. However, there are only countably many such clones when considered up to equivalence with respect to emph{minor-preserving maps} instead of clone homomorphisms. We give a full description of the set of clones of self-dual operations, ordered by the existence of minor-preserving maps. Our result can also be phrased as a statement about structures on a three-element set, ordered by primitive positive constructability, because there is a minor-preserving map from the polymorphism clone of a finite structure $mathfrak A$ to the polymorphism clone of a finite structure $mathfrak B$ if and only if there is a primitive positive construction of $mathfrak B$ in $mathfrak A$.
We propose a quantum walk defined by digraphs (mixed graphs). This is like Grover walk that is perturbed by a certain complex-valued function defined by digraphs. The discriminant of this quantum walk is a matrix that is a certain normalization of ge
neralized Hermitian adjacency matrices. Furthermore, we give definitions of the positive and negative supports of the transfer matrix, and clarify explicit formulas of their supports of the square. In addition, we give tables by computer on the identification of digraphs by their eigenvalues.
We consider a series of configurations defined by fibers of a given base configuration. We prove that Markov degree of the configurations is bounded from above by the Markov complexity of the base configuration. As important examples of base configur
ations we consider incidence matrices of graphs and study the maximum Markov degree of configurations defined by fibers of the incidence matrices. In particular we give a proof that the Markov degree for two-way transportation polytopes is three.
Consider all $k$-element subsets and $ell$-element subsets $(k>ell )$ of an $n$-element set as vertices of a bipartite graph. Two vertices are adjacent if the corresponding $ell$-element set is a subset of the corresponding $k$-element set. Let $G_{k
,ell}$ denote this graph. The domination number of $G_{k,1}$ was exactly determined by Badakhshian, Katona and Tuza. A conjecture was also stated there on the asymptotic value ($n$ tending to infinity) of the domination number of $G_{k,2}$. Here we prove the conjecture, determining the asymptotic value of the domination number $gamma (G_{k,2})={k+3over 2(k-1)(k+1)}n^2+o(n^2)$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
