Theorem. Next on Grammars Is Presheaf Structure

For presheaves, 𝗇𝖾𝗑𝗍:𝑃→▷𝑃 restricts along the strict past, as in later on presheaves. A grammar is only a family over strings, so a map 𝗇𝖾𝗑𝗍:π΄βŠ’β–·π΄ into the later on grammars is extra data. It sends a parse over 𝑣 to parses over every proper suffix of 𝑣.

Let ░𝐴=𝐴&▷𝐴, so that (░𝐴)π‘£β‰…βˆπ‘’βŠ‘π‘£π΄π‘’. This is the comonad π‘ˆβˆ˜Cofree for the suffix order, and presheaves are comonadic over families. The counit law forces the first component of a coalgebra π΄βŠ’β–‘π΄ to be the identity. Hence:

  • a presheaf on strings under the suffix order is the same as a grammar 𝐴 with a map 𝗇𝖾𝗑𝗍:π΄βŠ’β–·π΄ that satisfies coassociativity. Restricting to 𝑒′ and then to π‘’βŠπ‘’β€² must agree with restricting to 𝑒 directly;
  • for a proposition-valued grammar (a language), coassociativity is automatic, and 𝗇𝖾𝗑𝗍 exists exactly when the language is closed under suffixes. For example, ⊀ has one, but βŒˆπ‘ŽβŒ‰ does not, since (β–·βŒˆπ‘ŽβŒ‰)π‘Žβ‰…βŒˆπ‘ŽβŒ‰πœ€ is empty.

LΓΆb does not need 𝗇𝖾𝗑𝗍 on 𝐴. The fixed-point equation only restricts a global parse ⊀⊒𝐴, and a global parse can always be restricted. In the Agda, the grammar-level IsCoalgebra record, with only the field next, is in Grammar/Later/Coalgebra.agda on the guarded branch.

On presheaves the strict downset of 𝑐++𝑑 is represented by 𝑑, because every proper suffix of 𝑐++𝑑 is a suffix of 𝑑. So predecessors simplify later to (▷𝑃)(𝑐++𝑑)≅𝑃𝑑. On grammars there is no such simplification, since the factors at different suffixes are unrelated.

grammar-next-presheaf theorem entries/parsing/grammar-next-presheaf.hel