Language Kleene Algebra with Complement: A Finite Relational Semantics and (Un)decidability
Yoshiki Nakamura · HAL (Le Centre pour la Communication Scientifique Directe) · 2024
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 Π 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.