On Finite Model Property of the Equational Theory of Kleene Algebras

• Autorzy: Palka E.
• Języki publikacji: EN

Abstrakty

EN

The finite model property of the equational fragment of the theory of Kleene algebras is a consequence of Kozen's [3] completeness theorem. We show that, conversely, this completeness theorem can be proved assuming the finite model property of this fragment.

Słowa kluczowe

EN

Kleene algebras; action algebras; regular expressions; finite model property

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 68, nr 3
• Strony: 221--230
• Opis fizyczny: Bibliogr. 5 poz.

Twórcy

autor

Palka E.

• Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Umultowska 87, 61-614 Poznań, Poland,

Bibliografia

• [1] Buszkowski, W.: On complete action algebras, in: Volume of Abstracts of 11th International Congress of Logic, Methodology and Philosophy of Science, Cracow, 1999, 483.
• [2] Conway, J.H.: Regular Algebras and Finite Machines, Chapman and Hall, London, 1974.
• [3] Kozen, D.: A completeness theorem for Kleene algebras and the algebra of regular events, Information and Computation 110, 1994, 366-390.
• [4] Krob, D.: Complete systems of β-rational identities, Theoretical Computer Science 89, 1991, 207-343.
• [5] Pratt V.: Action Logic and Pure Induction, in: Logics in AI (J. Vav Eijck, Ed.), LNAI 478, Springer, Berlin, 1991, 97-120.