Lics

ACM/IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Twentieth Annual IEEE Symposium on

Logic in Computer Science (LICS 2005)

Paper: Completions of µ-algebras (at LICS 2005)

Authors: Luigi Santocanale

Abstract

We define the class of algebraic models of µ-calculi and study whether every such model can be embedded into a model which is a complete lattice. We show that this is false in the general case and focus then on free modal µ-algebras, i.e. Lindenbaum algebras of the propositional modal µ-calculus. We prove the following fact: the MacNeille-Dedekind completion of a free modal µ-algebra is a complete modal algebra, hence a modal µ-algebra (i.e. an algebraic model of the propositional modal µ-calculus). The canonical embedding of the free modal µ-algebra into its Dedekind-MacNeille completion preserves the interpretation of all the terms in the class Comp(?1,?1) of the alternation-depth hierarchy. The proof uses algebraic techniques only and does not directly rely on previous work on the completeness of the modal µ-calculus.

BibTeX

  @InProceedings{Santocanale-Completionsofalgebr,
    author = 	 {Luigi Santocanale},
    title = 	 {Completions of µ-algebras},
    booktitle =  {Proceedings of the Twentieth Annual IEEE Symposium on Logic in Computer Science (LICS 2005)},
    year =	 {2005},
    month =	 {June}, 
    pages =      {219--228},
    location =   {Chicago, USA}, 
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2022-10-3113:49
Sam Staton