A Complete Propositional Dynamic Logic for Regular Expressions with Lookahead
Yoshiki Nakamura · 2026
Read A Complete Propositional Dynamic Logic for Regular Expressions with Lookahead by Yoshiki Nakamura (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-15214.txt.
Description
Yoshiki Nakamura completes a logic for a common tool in computing. His 2026 arXiv paper deals with regular expressions with lookahead, a pattern language used to match text. Reasoning about when two such patterns match the same text needs firm rules.
Nakamura gives an axiomatic account of that reasoning. He covers both plain language equivalence and the largest substitution-closed equivalence that stays sound. His route uses a variant of propositional dynamic logic on finite linear orders. Two extra operators restrict a stated relation to the identity or else to its complement.
Catalog record
| CREATOR | Yoshiki Nakamura |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 30 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-15214