Abstract
We consider various classes of algebras obtained by expanding idempotent semirings with meet, residuals and Kleene-*. An investigation of congruence properties (e-permutability, e-regularity, congruence distributivity) is followed by a section on algebraic Gentzen systems for proving inequalities in idempotent semirings, in residuated lattices, and in (residuated) Kleene lattices (with cut). Finally we define (one-sorted) residuated Kleene lattices with tests to complement two-sorted Kleene algebras with tests.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Andréka, H., ‘Representations of distributive lattice-ordered semigroups with binary relations’, Algebra Universalis 28 (1991), no. 1, 12-25.
Belardinelli, F., P. Jipsen, H. Ono, ‘Algebraic aspects of cut-elimination theorems’, preprint.
Blount, K., and C. Tsinakis, ‘The structure of Residuated Lattices’, International Journal of Algebra and Computation, to appear.
Conway, J. H., Regular Algebra and Finite Machines, Chapman and Hall, 1971.
Freese, R., and J. B. Nation, ‘Congruence lattices of semilattices’, Pacific J. Math. 49 (1973), 51-58.
Gumm, H. P., and A. Ursini, ‘Ideals in universal algebras’, Algebra Universalis 19 (1984), no. 1, 45-54.
Jipsen, P., and C. Tsinakis, ‘A Survey of Residuated Lattices’, in J. Martinez, (ed.), Ordered Algebraic Structures Kluwer Academic Publishers, Dordrecht, 2002, pp. 19-56.
Jónsson, B., ‘On the representation of lattices’, Math. Scand 1 (1953), 193-206.
Kozen, D., ‘A completeness theorem for Kleene algebras and the algebra of regular events’, Infor. and Comput., 110:366-390, May 1994. http://www.cs.cornell.edu/kozen/papers/ka.ps
Kozen, D., ‘On action algebras’, in J. van Eijck and A. Visser, (eds.), Logic and Information Flow, pages 78-88. MIT Press, 1994. http://www.cs.cornell.edu/kozen/papers/act.ps
Kozen, D., ‘Kleene algebra with tests’, Transactions on Programming Languages and Systems, May 1997, 427-443. http://www.cs.cornell.edu/kozen/papers/kat.ps
Kozen, D., ‘On Hoare logic and Kleene algebra with tests’, Trans. Computational Logic 1:1 (July 2000), 60-76. http://www.cs.cornell.edu/kozen/papers/Hoare.ps
Kozen, D., and M. Patron, ‘Certification of compiler optimizations using Kleene algebra with tests’, in J. Lloyd et al, (eds.), Proc. 1st Int. Conf. Computational Logic (CL2000), vol 1861 LNAI, Springer-Verlag, London, July 2000, 568-582. http://www.cs.cornell.edu/kozen/papers/opti.ps
Lincoln, P., J. Mitchell, A. Scedrov, and N. Shankar, ‘Decision problems for propositional linear logic’, Ann. Pure Appl. Logic 56 (1992), no. 1–3, 239-311.
Ono, H., and Y. Komori, ‘Logics without the contraction rule’, J. Symbolic Logic 50 (1985), no. 1, 169-201.
Pratt, V., ‘Action Logic and Pure Induction’, in J. van Eijck, (ed.) Logics in AI: European Workshop JELIA '90, LNCS 478, Springer-Verlag, Amsterdam, NL, Sep, 1990, pp. 97-120. http://boole.stanford.edu/pub/jelia.ps.gz
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Jipsen, P. From Semirings to Residuated Kleene Lattices. Studia Logica 76, 291–303 (2004). https://doi.org/10.1023/B:STUD.0000032089.54776.63
Issue Date:
DOI: https://doi.org/10.1023/B:STUD.0000032089.54776.63