Heyting Algebras and Formal Languages

Werner Kuich (Vienna University of Technology, Austria)

Norbert Sauer (University of Calgary, Canada)

Friedrich Urbanek (Vienna University of Technology, Austria)

Abstract: By introducing a new operation, the exponentiation of formal languages, we can define Heyting algebras of formal languages. It turns out that some well known families of languages are closed under this exponentiation, e. g., the families of regular and of context-sensitive languages.

Keywords: automata, formal languages, lattices

Categories: F.4.3