×

The algebra of functions with antidomain and range. (English) Zbl 1377.08001

Summary: We give complete, finite quasiequational axiomatisations for algebras of unary partial functions under the operations of composition, domain, antidomain, range and intersection. This completes the extensive programme of classifying algebras of unary partial functions under combinations of these operations. We also look at the complexity of the equational theories and provide a nondeterministic polynomial upper bound. Finally we look at the problem of finite representability and show that finite algebras can be represented as a collection of functions over a finite base set provided that intersection is not in the signature.

MSC:

08B05 Equational logic, Mal’tsev conditions
08A02 Relational systems, laws of composition
03G15 Cylindric and polyadic algebras; relation algebras

Software:

Prover9; Mace4
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Batbedat, A., \(γ\)-demi-groups, demi-modules, produit demi-directs, (Semigroups, Proceedings. Semigroups, Proceedings, Oberwolfalch, Germany, 1978. Semigroups, Proceedings. Semigroups, Proceedings, Oberwolfalch, Germany, 1978, Lect. Notes Math., vol. 855 (1981), Springer-Verlag), 1-18
[2] Berendsen, J.; Jansen, D. N.; Schmaltz, J.; Vaandrager, F. W., The axiomatisation of override and update, J. Appl. Log., 8, 141-150 (2010) · Zbl 1194.03020
[3] Blackburn, P.; de Rijke, M.; Venema, Y., Modal Logic (2001), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0988.03006
[4] Cockett, J. R.B.; Guo, X.; Hofstra, P., Range categories I: general theory, Theory Appl. Categ., 26, 412-452 (2012) · Zbl 1252.18003
[5] Cockett, J. R.B.; Guo, X.; Hofstra, P., Range categories II: towards regularity, Theory Appl. Categ., 26, 453-500 (2012) · Zbl 1252.18004
[6] Cockett, J. R.B.; Lack, S., Restriction categories I. Categories of partial maps, Theor. Comput. Sci., 270, 223-259 (2002) · Zbl 0988.18003
[7] Cockett, R.; Manes, E., Boolean and classical restriction categories, Math. Struct. Comput. Sci., 19, 357-416 (2009) · Zbl 1191.03049
[8] Desharnais, J.; Möller, B.; Struth, G., Kleene algebra with domain, ACM Trans. Comput. Log., 7, 798-833 (2006) · Zbl 1367.68205
[9] Desharnais, J.; Jipsen, P.; Struth, G., Domain and antidomain semigroups, (Relations and Kleene Algebra in Computer Science. Relations and Kleene Algebra in Computer Science, Lect. Notes Comput. Sci., vol. 5827 (2009), Springer: Springer Berlin), 73-87 · Zbl 1267.03067
[10] Dudek, W.; Trokhimenko, V., Functional Menger P-algebras, Commun. Algebra, 30, 5921-5931 (2002) · Zbl 1018.20057
[11] Fountain, J.; Gomes, G.; Gould, V., A Munn-type representation for a class of \(E\)-semiadequate semigroups, J. Algebra, 218, 693-714 (1999) · Zbl 0940.20064
[12] Garey, M. R.; Johnson, D. S., Computers and Intractability (1979), W.H. Freeman and Co. · Zbl 0411.68039
[13] Goldblatt, R.; Jackson, M., Well-structured program equivalence is highly undecidable, ACM Trans. Comput. Log., 13, 3 (2012), Art. 26, 8 pp · Zbl 1351.68073
[14] Harel, D.; Kozen, D.; Tiuryn, J., Dynamic Logic, Found. Comput. Ser. (2000), MIT Press · Zbl 0976.68108
[15] Hirsch, R.; Hodkinson, I., Representability is not decidable for finite relation algebras, Trans. Am. Math. Soc., 353, 1403-1425 (2001) · Zbl 0965.03079
[16] Hirsch, R.; Hodkinson, I., Relation Algebras by Games, Stud. Logic Found. Math., vol. 147 (2002), North-Holland: North-Holland Amsterdam · Zbl 1018.03002
[17] Hirsch, R.; Jackson, M., Undecidability of representability as binary relations, J. Symb. Log., 77, 1211-1244 (2012) · Zbl 1279.03084
[18] Hollenberg, M., An equational axiomatization of dynamic negation and relational composition, J. Log. Lang. Inf., 6, 381-401 (1997) · Zbl 0882.03065
[19] Hollings, C., From right PP monoids to restriction semigroups: a survey, Eur. J. Pure Appl. Math., 2, 21-57 (2009) · Zbl 1214.20056
[20] Jackson, M.; Stokes, T., An invitation to C-semigroups, Semigroup Forum, 62, 279-310 (2001) · Zbl 0982.20051
[21] Jackson, M.; Stokes, T., Agreeable semigroups, J. Algebra, 266, 393-417 (2003) · Zbl 1041.20043
[22] Jackson, M.; Stokes, T., Identities in the algebra of partial maps, Int. J. Algebra Comput., 16, 1131-1159 (2006) · Zbl 1117.08003
[23] Jackson, M.; Stokes, T., The algebra of partial maps with domain and range: extending Schein’s representation, Commun. Algebra, 37, 2845-2870 (2009) · Zbl 1182.20058
[24] Jackson, M.; Stokes, T., Semigroups with and halting programs, Int. J. Algebra Comput., 19, 937-961 (2009) · Zbl 1203.08005
[25] Jackson, M.; Stokes, T., Modal restriction semigroups: towards an algebra of functions, Int. J. Algebra Comput., 21, 1053-1095 (2011) · Zbl 1256.20058
[26] Jackson, M.; Stokes, T., Representing semigroups with subsemilattices, J. Algebra, 376, 228-260 (2013) · Zbl 1283.20068
[27] Kambites, M., Free adequate semigroups, J. Aust. Math. Soc., 91, 365-390 (2011) · Zbl 1247.20066
[28] Kambites, M.; Kazda, A., The word problem for free adequate semigroups, Int. J. Algebra Comput., 24, 893-907 (2014) · Zbl 1307.20046
[29] Maddux, R. D., Relation Algebras, Stud. Logic Found. Math., vol. 150 (2006), North-Holland: North-Holland Amsterdam · Zbl 1197.03051
[30] Manes, E., Guarded and banded semigroups, Semigroup Forum, 72, 94-120 (2006) · Zbl 1097.20044
[31] McLean, B., The finite representation property for composition, intersection, antidomain and range, Int. J. Algebra Comput. (2015), accepted
[32] McCune, W., Prover9 and Mace4 (2005-2010)
[33] Menger, K., An axiomatic theory of functions and fluents, (Henkin, L.; Suppes, P.; Tarski, A., The Axiomatic Method (1959), North-Holland), 454-473
[34] Monk, D., On representable relation algebras, Mich. Math. J., 11, 207-210 (1964) · Zbl 0137.00603
[35] Neuzerling, M., Undecidability of representability for lattice-ordered semigroups and ordered complemented semigroups, Algebra Univers. (2015), in press · Zbl 1402.03100
[36] Schein, B. M., Restrictively multiplicative algebras of transformations, Izv. Vysš. Učebn. Zaved., Mat., 1970, 4(95), 91-102 (1970), (in Russian)
[37] Schein, B. M., Relation algebras and function semigroups, Semigroup Forum, 1, 1-62 (1970) · Zbl 0197.29404
[38] Schein, B. M., Lectures on semigroups of transformations, Am. Math. Soc. Transl. Ser. 2, 113, 123-181 (1979) · Zbl 0404.20057
[39] Schweizer, B.; Sklar, A., The algebra of functions, Math. Ann., 139, 366-382 (1960) · Zbl 0095.10101
[40] Schweizer, B.; Sklar, A., The algebra of functions II, Math. Ann., 143, 440-447 (1961) · Zbl 0099.31901
[41] Schweizer, B.; Sklar, A., The algebra of functions III, Math. Ann., 161, 171-196 (1965) · Zbl 0134.12602
[42] Schweizer, B.; Sklar, A., Function systems, Math. Ann., 172, 1-16 (1967) · Zbl 0163.01403
[43] Trokhimenko, V. S., Menger’s function systems, Izv. Vysš. Učebn. Zaved., Mat., 11, 71-78 (1973), (in Russian)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.