Normal Forms for Elements of ${}^*$-Continuous Kleene Algebras Representing the Context-Free Languages
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917328645521408 |
|---|---|
| author | Hopkins, Mark Leiß, Hans |
| author_facet | Hopkins, Mark Leiß, Hans |
| contents | Within the tensor product $K \mathop{\otimes_{\cal R}} C_2'$ of any ${}^*$-continuous Kleene algebra $K$ with the polycyclic ${}^*$-continuous Kleene algebra $C_2'$ over two bracket pairs there is a copy of the fixed-point closure of $K$: the centralizer of $C_2'$ in $K \mathop{\otimes_{\cal R}} C_2'$. Using an automata-theoretic representation of elements of $K\mathop{\otimes_{\cal R}} C_2'$ à la Kleene, with the aid of normal form theorems that restrict the occurrences of brackets on paths through the automata, we develop a foundation for a calculus of context-free expressions without variable binders. We also give some results on the bra-ket ${}^*$-continuous Kleene algebra $C_2$, motivate the ``completeness equation'' that distinguishes $C_2$ from $C_2'$, and show that $C_2'$ already validates a relativized form of this equation. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2310_17295 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Normal Forms for Elements of ${}^*$-Continuous Kleene Algebras Representing the Context-Free Languages Hopkins, Mark Leiß, Hans Formal Languages and Automata Theory F.4.3 Within the tensor product $K \mathop{\otimes_{\cal R}} C_2'$ of any ${}^*$-continuous Kleene algebra $K$ with the polycyclic ${}^*$-continuous Kleene algebra $C_2'$ over two bracket pairs there is a copy of the fixed-point closure of $K$: the centralizer of $C_2'$ in $K \mathop{\otimes_{\cal R}} C_2'$. Using an automata-theoretic representation of elements of $K\mathop{\otimes_{\cal R}} C_2'$ à la Kleene, with the aid of normal form theorems that restrict the occurrences of brackets on paths through the automata, we develop a foundation for a calculus of context-free expressions without variable binders. We also give some results on the bra-ket ${}^*$-continuous Kleene algebra $C_2$, motivate the ``completeness equation'' that distinguishes $C_2$ from $C_2'$, and show that $C_2'$ already validates a relativized form of this equation. |
| title | Normal Forms for Elements of ${}^*$-Continuous Kleene Algebras Representing the Context-Free Languages |
| topic | Formal Languages and Automata Theory F.4.3 |
| url | https://arxiv.org/abs/2310.17295 |