Bilattices and hyperidentities

Yu. M. Movsisyan

Trudy Matematicheskogo Instituta imeni V.A. Steklova, Algorithmic aspects of algebra and logic, Tome 274 (2011), pp. 191-209.

Résumé

Bilattices as algebras with two lattice structures were introduced by M. Ginsberg and M. Fitting in 1986–1990. They have found wide applications in logic programming, multi-valued logic, and artificial intelligence. We call these bilattices Ginsberg's bilattices. The description of Ginsberg's bilattices was obtained by various authors under the conditions of interlacement (or distributivity) and boundedness. In this paper, we prove that this description remains true without the second condition, while interlacement can be replaced with a weaker form called weak interlacement here. In particular, we prove that every weakly interlaced bilattice is isomorphic to the superproduct of two lattices, while every weakly interlaced Ginsberg bilattice is isomorphic to the Ginsberg superproduct of two equal lattices.

Bibliographie

[1] Arnold B.H., “Distributive lattices with a third operation defined”, Pac. J. Math., 1 (1951), 33–41 | DOI | MR | Zbl

[2] Kiss S.A., Transformations on lattices and structures of logic, New York, 1947 | MR | Zbl

[3] Jakubik J., Kolibiar M., “On some properties of a pair of lattices”, Czech. Math. J., 4 (1954), 1–27 | MR | Zbl

[4] Jakubik J., Kolibiar M., “Lattices with a third distributive operation”, Math. Slovaca, 27:3 (1977), 287–292 | MR | Zbl

[5] Ginsberg M.L., “Multivalued logics: a uniform approach to reasoning in artificial intelligence”, Comput. Intell., 4 (1988), 265–316 | DOI

[6] Fitting M., “Bilattices in logic programming”, Proc. 20th Intern. Symp. on Multiple-Valued Logic, ISMVL 1990, IEEE, New York, 1990, 238–246

[7] Fitting M., “Logic programming on a topological bilattice”, Fund. Inform., 11 (1988), 209–218 | MR | Zbl

[8] Fitting M., “Bilattices and the semantics of logic programming”, J. Log. Program., 11 (1991), 91–116 | DOI | MR | Zbl

[9] Jonsson B., Distributive bilattices, Preprint, Vanderbilt Univ., Nashville, 1994 | MR

[10] Mobasher B., Pigozzi D., Slutzki G., “Multi-valued logic programming semantics: An algebraic approach”, Theor. Comput. Sci., 171 (1997), 77–109 | DOI | MR | Zbl

[11] Mobasher B., Pigozzi D., Slutzki G., Voutsadakis G., “A duality theory for bilattices”, Algebra Univers., 43 (2000), 109–125 | DOI | MR | Zbl

[12] Romanowska A., Trakul A., “On the structure of some bilattices”, Universal and applied algebra, World Sci., Singapore, 1989, 235–253 | MR

[13] Avron A., “The structure of interlaced bilattices”, Math. Struct. Comput. Sci., 6 (1996), 287–299 | DOI | MR | Zbl

[14] Movsisyan Yu.M., Romanowska A.B., Smith J.D.H., “Superproducts, hyperidentities, and algebraic structures of logic programming”, J. Comb. Math. and Comb. Comput., 58 (2006), 101–111 | MR | Zbl

[15] Movsisyan Yu.M., Vvedenie v teoriyu algebr so sverkhtozhdestvami, Izd-vo Erevan. gos. un-ta, Erevan, 1986 | MR | Zbl

[16] Movsisyan Yu.M., “Sverkhtozhdestva v algebrakh i mnogoobraziyakh”, UMN, 53:1 (1998), 61–114 | DOI | MR | Zbl

[17] Movsisyan Yu.M., “Algebry so sverkhtozhdestvami mnogoobraziya bulevykh algebr”, Izv. RAN. Ser. mat., 60:6 (1996), 127–168 | DOI | MR | Zbl

[18] Movsisyan Yu.M., “Sverkhtozhdestva bulevykh algebr”, Izv. RAN. Ser. mat., 56:3 (1992), 654–672 | MR | Zbl

[19] Padmanabhan R., Penner P., “Binary hyperidentities of lattices”, Aequationes Math., 44 (1992), 154–167 | DOI | MR | Zbl

[20] Padmanabhan R., Penner P., “A hyperbase for binary lattice hyperidentities”, J. Autom. Reasoning., 24 (2000), 365–370 | DOI | MR | Zbl

[21] Denecke K., Wismath S.L., Hyperidentities and clones, Gordon and Breach, Amsterdam, 2000 | MR | Zbl

[22] Koppitz J., Denecke K., M-solid varieties of algebras, Springer, New York, 2006 | MR | Zbl

[23] Anosov V.D., “O gomomorfizmakh mnogoosnovnykh algebraicheskikh sistem v svyazi s kriptograficheskimi primeneniyami”, Diskret. matematika, 19:2 (2007), 27–44 | DOI | Zbl

[24] Font J.M., Moussavi M., “Note on a six-valued extension of tree-valued logic”, J. Appl. Non-Class. Logic., 3 (1993), 173–187 | DOI | MR | Zbl

[25] Kondo M., “On the structures of weak interlaced bilattice”, Proc. 32nd Intern. Symp. on Multiple-Valued Logic, ISMVL 2002, May 15–18, 2002, Boston, MA, IEEE, Washington, DC, 2002, 23 | MR

[26] Grettser G., Obschaya teoriya reshetok, Mir, M., 1982 | MR

[27] Movsisyan Yu.M., Budaghyan L.M., “The elementary characterization of algebras with hyperidentities of Boolean algebras”, Intern. Conf. on Mathematical Logic, Algebra and Set Theory dedicated to the 100th anniversary of P.S. Novikov, Moscow, Aug. 27–31, 2001, Abstr., Moscow State Univ., Moscow, 2001, 32

[28] Movsisyan Yu.M., Budaghyan L.M., “On elementary decidability of quasi-boolean algebras”, Mathematics in Armenia, advances and perspectives, Proc. Intern. Conf., Yerevan (Armenia), Sept. 30–Oct. 7, 2003, Yerevan State Univ., Yerevan, 2003, 55–57

[29] Plotkin B.I., Universalnaya algebra, algebraicheskaya logika i bazy dannykh, Nauka, M., 1991 | MR | Zbl

[30] Higgins P.J., “Algebras with a scheme of operators”, Math. Nachr., 27 (1963), 115–132 | DOI | MR | Zbl

[31] Birkhoff G., Lipson J.D., “Heterogeneous algebras”, J. Comb. Theory, 8 (1970), 115–133 | DOI | MR | Zbl