Seminars
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
Calendar
Search
Add a seminar

RSS
Forthcoming seminars




Seminars "Proof Theory" and "Logic Online Seminar"
April 13, 2020 18:30, Moscow, online
 


On Free $\omega$-Continuous and Regular Ordered Algebras

Dexter Kozen
Video records:
MP4 1,429.5 Mb
MP4 774.2 Mb
Supplementary materials:
Adobe PDF 566.7 Kb

Number of views:
This page:256
Video files:49
Materials:28
Youtube:

Dexter Kozen



Abstract: Ordered algebras abound in program logics and programming language semantics: $\omega$-continuous semirings, star-continuous Kleene algebras and Kleene algebras with tests, context-free languages, OI-macro languages, iteration theories, recursion schemes, and Scott domains, among many others. These structures are all examples of varieties of ordered $\Sigma$-algebras with restricted completeness and continuity properties. In this talk I will give a general characterization of the free algebras of such varieties in terms of submonads of the monad of $\Sigma$-coterms. Varieties of this form are called quasi-regular. For example, the free star-continuous Kleene algebra is the subalgebra of the corresponding free $\Sigma$-continuous semiring determined by those elements denoted by the regular $\Sigma$-coterms, where $\Sigma$ is the signature of Kleene algebra. This is a special case of a more general construction that applies to any quasi-regular family, including all the examples mentioned above.
(joint work with Zoltán Ésik)

Supplementary materials: presentation.pdf (566.7 Kb)

Language: English
 
  Contact us:
 Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024