A proof theory of right-linear (omega-)grammars via cyclic proofs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911763768803328 |
|---|---|
| author | Das, Anupam De, Abhishek |
| author_facet | Das, Anupam De, Abhishek |
| contents | Right-linear (or left-linear) grammars are a well-known class of context-free grammars computing just the regular languages. They may naturally be written as expressions with (least) fixed points but with products restricted to letters as left arguments, giving an alternative to the syntax of regular expressions. In this work, we investigate the resulting logical theory of this syntax. Namely, we propose a theory of right-linear algebras (RLA) over of this syntax and a cyclic proof system CRLA for reasoning about them.
We show that CRLA is sound and complete for the intended model of regular languages. From here we recover the same completeness result for RLA by extracting inductive invariants from cyclic proofs, rendering the model of regular languages the free right-linear algebra.
Finally, we extend system CRLA by greatest fixed points, nuCRLA, naturally modelled by languages of omega-words thanks to right-linearity. We show a similar soundness and completeness result of (the guarded fragment of) nuCRLA for the model of omega-regular languages, employing game theoretic techniques. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2401_13382 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | A proof theory of right-linear (omega-)grammars via cyclic proofs Das, Anupam De, Abhishek Logic in Computer Science Formal Languages and Automata Theory Logic Right-linear (or left-linear) grammars are a well-known class of context-free grammars computing just the regular languages. They may naturally be written as expressions with (least) fixed points but with products restricted to letters as left arguments, giving an alternative to the syntax of regular expressions. In this work, we investigate the resulting logical theory of this syntax. Namely, we propose a theory of right-linear algebras (RLA) over of this syntax and a cyclic proof system CRLA for reasoning about them. We show that CRLA is sound and complete for the intended model of regular languages. From here we recover the same completeness result for RLA by extracting inductive invariants from cyclic proofs, rendering the model of regular languages the free right-linear algebra. Finally, we extend system CRLA by greatest fixed points, nuCRLA, naturally modelled by languages of omega-words thanks to right-linearity. We show a similar soundness and completeness result of (the guarded fragment of) nuCRLA for the model of omega-regular languages, employing game theoretic techniques. |
| title | A proof theory of right-linear (omega-)grammars via cyclic proofs |
| topic | Logic in Computer Science Formal Languages and Automata Theory Logic |
| url | https://arxiv.org/abs/2401.13382 |