Definition. Later on Grammars

Write π‘’βŠπ‘£ when 𝑒 is a proper suffix of 𝑣, that is, 𝑣=π‘₯++𝑒 with π‘₯β‰ πœ€. The later of a grammar 𝐴 is

(▷𝐴)𝑣=βˆπ‘’βŠπ‘£π΄π‘’.

A parse of ▷𝐴 over 𝑣 is a parse of 𝐴 over every proper suffix of 𝑣. In particular (▷𝐴)πœ€ is a singleton.

This is later on families for strings under the proper-suffix order. That order is well-founded because it strictly decreases length, so it is a thin direct category. There is at most one map 𝑒→𝑣, so the product over maps from the strict past has one factor per proper suffix. Guarded recursion is modelled by presheaves on πœ”, the topos of trees, and more generally by sheaves over a well-founded base [1]. Here the later acts on families, which is what grammars are, and there is no clock.

Later is the right adjoint of the proper-suffix derivative. Let 𝖭𝖀𝖲=⨁π‘₯β‰ πœ€βŒˆπ‘₯βŒ‰ be the grammar of non-empty strings. Then the derivative (πœ•π–­π–€π–²π΅)π‘’β‰…βˆ‘π‘₯β‰ πœ€π΅(π‘₯++𝑒) has the right adjoint

πΆπ–­π–€π–²π‘£β‰…βˆπ‘₯++𝑒=𝑣𝖭𝖀𝖲π‘₯→𝐢𝑒≅(▷𝐢)𝑣,

so πœ•π–­π–€π–²βˆ’βŠ£β–·. Splitting 𝖭𝖀𝖲 into its summands gives the form of β–· that the calculus can define:

▷𝐴≅&π‘€β‰ πœ€π΄βŒˆπ‘€βŒ‰,π΄βŒˆπ‘€βŒ‰β‰…(βŒˆπ‘€βŒ‰βŠ—βŠ€)β‡’(βŒˆπ‘€βŒ‰βŠ—π΄).

The component at 𝑀 says: if the string begins with 𝑀, then the rest parses as 𝐴.

The restriction to non-empty 𝑀 is what makes this a later. At 𝑀=πœ€ the component is π΄βŒˆπœ€βŒ‰β‰…π΄. Including it would give a projection β–·π΄βŠ’π΄, and LΓΆb would then prove every grammar. For the same reason the later is a product over suffixes. A sum such as β¨π‘βŒˆπ‘βŒ‰βŠΈπ΄ is empty at πœ€, and at 𝐴=βŠ₯ it is βŠ₯. The identity step βŠ₯⊒βŠ₯ would then give LΓΆb a proof of ⊀⊒βŠ₯.

In the Agda this is β–· in Grammar/Later/Base.agda, which is defined as the indexed conjunction of √l-string. The mirror image β–·r, over proper prefixes, is defined in the same way. See also the bilateral later and the later along an arbitrary well-founded order.

References

First steps in synthetic guarded domain theory: step-indexing in the topos of trees β†—
grammar-later definition entries/parsing/grammar-later.hel