Geodesic
Classification and Enumeration of Bases in Clone of All Hyperfunctions on Two-Elements Set
The Bulletin of Irkutsk State University. Series Mathematics, Tome 7 (2014), pp. 61-78 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice de l'article

Hyperfunctions are functions from a finite set A to set of all nonempty subsets of A. Superposition of hyperfunctions is defined in a special way. Clones are sets containing all projections and closed under superposition. Clone is a maximal clone if the only clone containing it is a clone of all hyperfunctions. Set of hyperfunctions is called complete set if the only clone containing it is a clone of all hyperfunctions. Set of hyperfunctions is a basis if it is a complete set and not any of its subsets is a complete set. This paper considers hyperfunctions on a two-elements set. As Tarasov V. showed there are 9 maximal clones on this set. Hyperfunctions on two-elements set classified by their membership in maximal clones. All hyperfunctions are divided into 119 equivalence classes. Based on this classification all kinds of bases are described. Two bases are of different kinds if there is a function in one basis with no equivalent function in the other one. We show that bases of hyperfunctions can have cardinality from 1 to 7: there is only one kind of basis with cardinality 1, 581 with cardinality 2, 19 299 with cardinality 3, 58 974 with cardinality 4, 27 857 with cardinality 5, 2316 with cardinality 6 and 35 with cardinality 7.
Keywords: clone, hyperclone, basis, hyperfunction, hyperoperation, complete set, closed set, multifunction, multioperation.
Mots-clés : superposition 
@article{IIGUM_2014_7_a5,
     author = {A. Kazimirov and V. Panteleyev and L. Tokareva},
     title = {Classification and {Enumeration} of {Bases} in {Clone} of {All} {Hyperfunctions} on {Two-Elements} {Set}},
     journal = {The Bulletin of Irkutsk State University. Series Mathematics},
     pages = {61--78},
     year = {2014},
     volume = {7},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/IIGUM_2014_7_a5/}
}
TY  - JOUR
AU  - A. Kazimirov
AU  - V. Panteleyev
AU  - L. Tokareva
TI  - Classification and Enumeration of Bases in Clone of All Hyperfunctions on Two-Elements Set
JO  - The Bulletin of Irkutsk State University. Series Mathematics
PY  - 2014
SP  - 61
EP  - 78
VL  - 7
UR  - http://geodesic.mathdoc.fr/item/IIGUM_2014_7_a5/
LA  - ru
ID  - IIGUM_2014_7_a5
ER  - 
%0 Journal Article
%A A. Kazimirov
%A V. Panteleyev
%A L. Tokareva
%T Classification and Enumeration of Bases in Clone of All Hyperfunctions on Two-Elements Set
%J The Bulletin of Irkutsk State University. Series Mathematics
%D 2014
%P 61-78
%V 7
%U http://geodesic.mathdoc.fr/item/IIGUM_2014_7_a5/
%G ru
%F IIGUM_2014_7_a5
A. Kazimirov; V. Panteleyev; L. Tokareva. Classification and Enumeration of Bases in Clone of All Hyperfunctions on Two-Elements Set. The Bulletin of Irkutsk State University. Series Mathematics, Tome 7 (2014), pp. 61-78. http://geodesic.mathdoc.fr/item/IIGUM_2014_7_a5/

[1] Tarasov V. V., “Completeness Criterion for Partial Logic Functions”, Problemy Kibernetiki, 30, Nauka, M., 1975, 319–325 (in Russian) | MR

[2] Yablonskij S. V., “On the Superpositions of Logic Functions”, Mat. Sbornik, 30:2(72) (1952), 329–348 (in Russian) | MR

[3] L. Krnić, “Types of bases in the algebra of logic”, Glasnik matematicko-fizicki i astronomski. Ser. 2, 20 (1965), 23–32 | MR

[4] M. Miyakawa, I. Stojmenović, D. Lau, I. Rosenberg, “Classification and basis enumerations in many-valued logics”, Proc. 17th International Symposium on Multi-Valued logic (Boston, 1987), 151–160

[5] M. Miyakawa, I. Stojmenović, D. Lau, I. Rosenberg, “Classification and basis enumerations of the algebras for partial functions”, Proc. 19th International Symposium on Multi-Valued logic (Rostock, 1989), 8–13

[6] D. Lau, M. Miyakawa, “Classification and enumerations of bases in $P_k(2)$”, Asian-European Journal of Mathematics, 1:2 (2008), 255–282 | DOI | MR

[7] I. Stojmenović, “Classification of $P_3$ and the enumeration of base of $P_3$”, Rev. of Res. 14, Fat. of Sci., Math. Ser., Novi Sad., 1984, 73–80 | MR

[8] Miyakawa M., Rosenberg I., Stojmenović I., “Classification of three-valued logical functions preserving 0”, Discrete Applied Mathematics, 28 (1990), 231–249 | DOI | MR