Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity
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_ | 1866911772449964032 |
|---|---|
| author | Zhang, Yuanrui Liu, Xinxin |
| author_facet | Zhang, Yuanrui Liu, Xinxin |
| contents | We analyze a phenomenon called ``image reflection'' on a type of characterization graphs -- LLEE charts -- of 1-free regular expressions. Due to the correspondence between 1-free regular expressions and the provable solutions of LEE/LLEE charts, this observation naturally leads to a new proof for the completeness of the proof system \MilIfree\ for 1-free regular expressions modulo bisimulation equivalence. The critical part of the previous proof is to show that bisimulation collapse, which plays the role in linking the provable solutions of two LLEE charts, is still an LLEE chart. The difference of our proof, compared to the previous one, is that we do not rely on the graph transformations from LLEE charts into their bisimulation collapses by merging two carefully-selected bisimilar nodes in each transformation step. Instead, we directly show that the bisimulation collapse of an LLEE chart possesses an LEE/LLEE structure based on its set of images mapped through the bisimulation function from the LLEE chart, and the constrained relation between the images and their so-called ``well-structured'' looping-back charts pre-images on the LLEE chart. Our approach provides a novel angle to look at this problem and related problems, and can also be used for simplifying the graph transformations in the proof of the completeness problem of the proof system \Mil\ for regular expressions modulo bisimulation equivalence, which had remained open until very recently. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_01222 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity Zhang, Yuanrui Liu, Xinxin Logic in Computer Science Formal Languages and Automata Theory We analyze a phenomenon called ``image reflection'' on a type of characterization graphs -- LLEE charts -- of 1-free regular expressions. Due to the correspondence between 1-free regular expressions and the provable solutions of LEE/LLEE charts, this observation naturally leads to a new proof for the completeness of the proof system \MilIfree\ for 1-free regular expressions modulo bisimulation equivalence. The critical part of the previous proof is to show that bisimulation collapse, which plays the role in linking the provable solutions of two LLEE charts, is still an LLEE chart. The difference of our proof, compared to the previous one, is that we do not rely on the graph transformations from LLEE charts into their bisimulation collapses by merging two carefully-selected bisimilar nodes in each transformation step. Instead, we directly show that the bisimulation collapse of an LLEE chart possesses an LEE/LLEE structure based on its set of images mapped through the bisimulation function from the LLEE chart, and the constrained relation between the images and their so-called ``well-structured'' looping-back charts pre-images on the LLEE chart. Our approach provides a novel angle to look at this problem and related problems, and can also be used for simplifying the graph transformations in the proof of the completeness problem of the proof system \Mil\ for regular expressions modulo bisimulation equivalence, which had remained open until very recently. |
| title | Image Reflection on Process Graphs -- A Novel Approach for the Completeness of an Axiomatization of 1-Free Regular Expressions Modulo Bisimilarity |
| topic | Logic in Computer Science Formal Languages and Automata Theory |
| url | https://arxiv.org/abs/2311.01222 |