2026-07-25T01:58:09Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22794 2025-03-13T16:29:17Z ddc:004 open_access

Finite Relational Semantics for Language Kleene Algebra with Complement Nakamura, Yoshiki Kleene algebra Language model Relational model Complexity We study the equational theory of Kleene algebra (KA) w.r.t. languages (here, meaning the equational theory of regular expressions where each letter maps to any language) by extending the algebraic signature with the language complement. This extension significantly enhances the expressive power of KA. In this paper, we present a finite relational semantics completely characterizing the equational theory w.r.t. languages, which extends the relational characterizations known for KA and for KA with top. Based on this relational semantics, we show that the equational theory w.r.t. languages is Π⁰₁-complete for KA with complement (with or without Kleene-star) and is PSPACE-complete if the complement only applies to variables or constants. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Yoshiki Nakamura 2025 Is Part Of LIPIcs, Volume 326, 33rd EACSL Annual Conference on Computer Science Logic (CSL 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2025.37 urn:nbn:de:0030-drops-227944 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2025.37 eng https://creativecommons.org/licenses/by/4.0/legalcode