Finite Relational Semantics for Language Kleene Algebra with Complement
Yoshiki Nakamura · HAL (Le Centre pour la Communication Scientifique Directe) · 2024
We study the equational theory of Kleene algebra (KA) w.r.t.\ languages by extending the language complement.This extension significantly enhances the expressive power of KA.In this paper, we present a (finite) \emph{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 $\Pi^{0}_{1}$-complete for KA with complement (with or without Kleene-star) and is PSPACE-complete if the complement only applies to variables or constants.