~~NOCACHE~~
/* DO NOT EDIT THIS FILE               */
/* THIS FILE WAS GENERATED             */
/* EDIT THE FILE "indexheader" INSTEAD */
/* OR ACCESS THE DATABASE              */

{{page>.:indexheader}}

\\ ==== Next talk ====
[[en:seminaires:pps:index|Proofs, programs and systems]]\\
Thursday June 5, 2025, 10:30AM, Salle 3052 & online ([[https://u-paris.zoom.us/j/84381797685?pwd=WG1ZSnhnYi81MnhsTFB6S2krM0E2Zz09|Zoom link]])\\
**Noam Zeilberger**  //Finite-state automata and grammars over categories//
<button type="link" size="xs" collapse="b4-815">{{icon>info-circle?lg&color=#777}}</button>\\
<collapse id="b4-815" collapsed="true">
<well size="sm">
Many different kinds of formal systems may be presented as projection functors p : D → C from a more or less complicated category D to some simpler category C, so that natural logical and computational questions about these systems are reduced to lifting problems along the functor. In the talk I will discuss joint work with Paul-André Melliès applying this perspective to automata and formal languages, which leads naturally to a generalization of the theory of regular and context-free languages to languages of arrows in arbitrary categories.  Most of the talk will focus on finite-state automata, but time permitting I will also discuss regular and context-free grammars.

Main references by PAM and NZ:

* Functors are type refinement systems, POPL 2015, https://doi.org/10.1145/2676726.2676970
* The categorical contours of the Chomsky-Schützenberger representation theorem, LMCS 21:2, https://doi.org/10.46298/lmcs-21(2:12)2025
</well>
</collapse>


\\ ==== Previous talks ====
\\ === Year 2025 ===

{{page>.:pps2025}}

\\ === Year 2024 ===

{{page>.:pps2024}}

\\ === Year 2023 ===

{{page>.:pps2023}}

\\ === Year 2022 ===

{{page>.:pps2022}}

\\ === Year 2021 ===

{{page>.:pps2021}}

\\ === Year 2020 ===

{{page>.:pps2020}}

\\ === Year 2019 ===

{{page>.:pps2019}}

\\ === Year 2018 ===

{{page>.:pps2018}}

\\ === Year 2017 ===

{{page>.:pps2017}}

\\ === Year 2016 ===

{{page>.:pps2016}}