{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,20]],"date-time":"2025-11-20T19:09:52Z","timestamp":1763665792992,"version":"3.41.2"},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"accepted":{"date-parts":[[2025,5,16]]},"abstract":"<jats:p>We develop fibrational perspectives on context-free grammars and on nondeterministic finite-state automata over categories and operads. A generalized CFG is a functor from a free colored operad (aka multicategory) generated by a pointed finite species into an arbitrary base operad: this encompasses classical CFGs by taking the base to be a certain operad constructed from a free monoid, as an instance of a more general construction of an \\emph{operad of spliced arrows} $\\mathcal{W}\\,\\mathcal{C}$ for any category $\\mathcal{C}$. A generalized NFA is a functor from an arbitrary bipointed category or pointed operad satisfying the unique lifting of factorizations and finite fiber properties: this encompasses classical word automata and tree automata without $\\epsilon$-transitions, but also automata over non-free categories and operads. We show that generalized context-free and regular languages satisfy suitable generalizations of many of the usual closure properties, and in particular we give a simple conceptual proof that context-free languages are closed under intersection with regular languages. Finally, we observe that the splicing functor $\\mathcal{W} : Cat \\to Oper$ admits a left adjoint $\\mathcal{C}: Oper \\to Cat$, which we call the \\emph{contour category} construction since the arrows of $\\mathcal{C}\\,\\mathcal{O}$ have a geometric interpretation as oriented contours of operations of $\\mathcal{O}$. A direct consequence of the contour \/ splicing adjunction is that every pointed finite species induces a universal CFG generating a language of \\emph{tree contour words.} This leads us to a generalization of the Chomsky-Sch\\&amp;quot;utzenberger Representation Theorem, establishing that a subset of a homset $L \\subseteq \\mathcal{C}(A,B)$ is a CFL of arrows if and only if it is a functorial image of the intersection of a $\\mathcal{C}$-chromatic tree contour language with a regular language.<\/jats:p>","DOI":"10.46298\/lmcs-21(2:12)2025","type":"journal-article","created":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T16:05:09Z","timestamp":1747411509000},"source":"Crossref","is-referenced-by-count":0,"title":["The categorical contours of the Chomsky-Sch\\\"utzenberger representation theorem"],"prefix":"10.46298","volume":"Volume 21, Issue 2","author":[{"given":"Paul-Andr\u00e9","family":"Melli\u00e8s","sequence":"first","affiliation":[]},{"given":"Noam","family":"Zeilberger","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2025,5,16]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/arxiv.org\/pdf\/2405.14703v4","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/arxiv.org\/pdf\/2405.14703v4","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,16]],"date-time":"2025-05-16T16:05:09Z","timestamp":1747411509000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/13654"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,5,16]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-21(2:12)2025","relation":{"has-preprint":[{"id-type":"arxiv","id":"2405.14703v2","asserted-by":"subject"},{"id-type":"arxiv","id":"2405.14703v1","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"2405.14703","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.2405.14703","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"type":"electronic","value":"1860-5974"}],"subject":[],"published":{"date-parts":[[2025,5,16]]},"article-number":"13654"}}