Normal Forms for Elements of the {}^*-Continuous Kleene Algebras KRC2K\mathop{\otimes_{\cal R}} C_2'

Avatar
Poster
00:00
00:00
Voice is AI-generated
Connected to paperThis paper is a preprint and has not been certified by peer review

Normal Forms for Elements of the ${}^*$-Continuous Kleene Algebras $K\mathop{\otimes_{\cal R}} C_2'$

Authors

Mark Hopkins, Hans Leiß

Abstract

The tensor product KRC2K \mathop{\otimes_{\cal R}} C_2' of the {}^*-continuous Kleene algebra KK with the polycyclic {}^*-continuous Kleene algebra C2C_2' over two bracket pairs contains a copy of the fixed-point closure of KK: the centralizer of C2C_2' in KRC2K \mathop{\otimes_{\cal R}} C_2'. We prove a representation of elements of KRC2K\mathop{\otimes_{\cal R}} C_2' by automata \`a la Kleene and refine it by normal form theorems that restrict the occurrences of brackets on paths through the automata. This is a foundation for a calculus of context-free expressions. We also show that C2C_2' validates a relativized form of the ``completeness property'' that distinguishes the bra-ket {}^*-continuous Kleene algebra C2C_2 from the polycyclic one.

Follow Us on

0 comments

Add comment