×

zbMATH — the first resource for mathematics

Relational semantics for Kleene logic and action logic. (English) Zbl 1099.03014
Recall that (1) Kleene algebras in the sense of D. Kozen provide solutions of the finite axiomatization problem for the algebra of regular sets by finitely many equations as does (2) action logic. In this interesting paper, the authors treat them as non-classsical logics with the usual Hilbert-style axiomatization and semantics. Several soundness theorems and completeness theorems are proved mostly in great detail. In their discussions of semantics based on a four-valued approach, the authors imagine a “dual” to C. E. Shannon’s concept of information, which can be used to clarify the role of the logics and algebras. Finally, in the authors’ star semantics, the reviewer wonders: can partial generalized Galois logics be extended with an operation, if the new operation is (1) circularly definable or (2) is the closure of a circularly definable operation?

MSC:
03B47 Substructural logics (including relevance, entailment, linear logic, Lambek calculus, BCK and BCI logics)
68Q70 Algebraic theory of languages and automata
03B60 Other nonclassical logic
03B45 Modal logic (including the logic of norms)
03D05 Automata and formal grammars in connection with logical questions
03C13 Model theory of finite structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Allwein, G., and J. M. Dunn, ”Kripke models for linear logic”, The Journal of Symbolic Logic , vol. 58 (1993), pp. 514–45. JSTOR: · Zbl 0795.03013
[2] Anderson, A. R., and N. D. Belnap, Jr., Entailment. The Logic of Relevance and Necessity , vol. 1, Princeton University Press, Princeton, 1975. · Zbl 0323.02030
[3] Bimbó, K., ”Semantics for structurally free logics LC\(+\)”, Logic Journal of the IGPL , vol. 9 (2001), pp. 525–39. · Zbl 0986.03019
[4] Bimbó, K., ”Semantics for dual and symmetric combinatory calculi”, Journal of Philosophical Logic , vol. 33 (2004), pp. 125–53. · Zbl 1054.03012
[5] Bimbó, K., and J. M. Dunn, ”Two extensions of the structurally free logic \(\mathrm LC\)”, Logic Journal of the IGPL , vol. 6 (1998), pp. 403–24. · Zbl 0904.03006
[6] Bimbó, K., and J. M. Dunn, ”Four-valued logic”, Notre Dame Journal of Formal Logic , vol. 42 (2001), pp. 171–92 (2003). · Zbl 1034.03021
[7] Birkhoff, G., Lattice Theory , American Mathematical Society Colloquium Publications, Vol. XXV. American Mathematical Society, Providence, 1967. · Zbl 0153.02501
[8] Birkhoff, G., and O. Frink, Jr., ”Representations of lattices by sets”, Transactions of the American Mathematical Society , vol. 64 (1948), pp. 299–316. · Zbl 0032.00504
[9] Curry, H. B., Foundations of Mathematical Logic , McGraw-Hill Book Co., New York, 1963. · Zbl 0163.24209
[10] Dunn, J. M., ”Intuitive semantics for first-degree entailments and ‘coupled trees”’, Philosophical Studies , vol. 29 (1976), pp. 149–68. · Zbl 1435.03043
[11] Dunn, J. M., ”Relevance logic and entailment”, pp. 117–229 in Handbook of Philosophical Logic , edited by D. Gabbay and F. Guenther, vol. 3, Reidel, Dordrecht, 1986. · Zbl 0875.03051
[12] Dunn, J. M., ”Gaggle theory: An abstraction of Galois connections and residuation, with applications to negation, implication, and various logical operators”, pp. 31–51 in Logics in AI (Amsterdam, 1990) , edited by J. van Eijck, vol. 478 of Lecture Notes in Computer Science , Springer, Berlin, 1991. · Zbl 0814.03044
[13] Dunn, J. M., ”Partial gaggles applied to logics with restricted structural rules”, pp. 63–108 in Substructural Logics (Tübingen, 1990) , edited by K. Došen and P. Schroeder-Heister, vol. 2 of Studies in Logic and Computation , Oxford University Press, New York, 1993. · Zbl 0941.03521
[14] Dunn, J. M., ”Gaggle theory applied to intuitionistic, modal and relevance logic”, pp. 335–68 in Logik und Mathematik. Frege-Kolloquium Jena , W. de Gruyter, Berlin, 1995.
[15] Dunn, J. M., ”Generalized ortho-negation”, pp. 3–26 in Negation: A Notion in Focus , edited by H. Wansing, W. de Gruyter, Berlin, 1996. · Zbl 0979.03027
[16] Dunn, J. M., ”A representation of relation algebras using Routley-Meyer frames”, pp. 77–108 in Logic, Meaning and Computation , edited by C. A. Anderson and M. Zelëny, vol. 305 of Synthese Library , Kluwer Academic Publishers, Dordrecht, 2001. · Zbl 1039.03051
[17] Dunn, J. M., ”Ternary relational semantics and beyond: Programs as data and programs as instructions”, Logical Studies , no. 7, online journal, (2001). Special Issue: Proceedings of the International Conference Third Smirnov Readings (Moscow, May 24–27, 2001), Part 2, http://www.logic.ru/LogStud/. · Zbl 1031.03008
[18] Dunn, J. M., and G. M. Hardegree, Algebraic Methods in Philosophical Logic , vol. 41 of Oxford Logic Guides , The Clarendon Press, New York, 2001. · Zbl 1014.03002
[19] Dunn, J. M., and R. K. Meyer, ”Combinators and structurally free logic”, Logic Journal of the IGPL , vol. 5 (1997), pp. 505–37 (electronic). · Zbl 0878.03008
[20] Ebbinghaus, H.-D., and J. Flum, Finite Model Theory , 2d edition, Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1999. · Zbl 0932.03032
[21] Enderton, H. B., A Mathematical Introduction to Logic , 2d edition, Harcourt/Academic Press, Burlington, 2001. · Zbl 0992.03001
[22] Grätzer, G., Universal Algebra , 2d edition, Springer-Verlag, New York, 1979. · Zbl 0412.08001
[23] Hartonas, C., and J. M. Dunn, ”Stone duality for lattices”, Algebra Universalis , vol. 37 (1997), pp. 391–401. · Zbl 0902.06008
[24] Kozen, D., ”A completeness theorem for Kleene algebras and the algebra of regular events”, Information and Computation , vol. 110 (1994), pp. 366–90. 1991 IEEE Symposium on Logic in Computer Science (Amsterdam, 1991). · Zbl 0806.68082
[25] Pratt, V., ”Action logic and pure induction”, pp. 97–120 in Logics in AI (Amsterdam, 1990) , edited by J. van Eijck, vol. 478 of Lecture Notes in Computer Science , Springer, Berlin, 1991. · Zbl 0814.03024
[26] Sipser, M., Introduction to the Theory of Computation , PWS Publishing Company, New York, 1997. · Zbl 1169.68300
[27] Stoll, R. R., Set Theory and Logic , Dover Publications Inc., New York, 1979. Corrected reprint of the 1963 edition. · Zbl 0489.03002
[28] Urquhart, A., ”A topological representation theory for lattices”, Algebra Universalis , vol. 8 (1978), pp. 45–58. · Zbl 0382.06010
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.