Zobrazeno 1 - 10
of 53
pro vyhledávání: '"Zeilberger, Noam"'
We sketch a tentative proof of P-completeness for the $\beta$-convertibility problem on untyped planar (a.k.a. ordered or non-commutative) $\lambda$-terms.
Comment: Abstract for the Trends in Linear Logic and Applications 2023 workshop, meant to
Comment: Abstract for the Trends in Linear Logic and Applications 2023 workshop, meant to
Externí odkaz:
http://arxiv.org/abs/2404.05276
Autor:
Melliès, Paul-André, Zeilberger, Noam
We develop fibrational perspectives on context-free grammars and on finite state automata over categories and operads. A generalized CFG is a functor from a free colored operad (= multicategory) generated by a pointed finite species into an arbitrary
Externí odkaz:
http://arxiv.org/abs/2405.14703
Autor:
Melliès, Paul-André, Zeilberger, Noam
Publikováno v:
Electronic Notes in Theoretical Informatics and Computer Science, Volume 1 - Proceedings of MFPS XXXVIII (February 22, 2023) entics:10508
We begin by explaining how any context-free grammar encodes a functor of operads from a freely generated operad into a certain "operad of spliced words". This motivates a more general notion of CFG over any category $C$, defined as a finite species $
Externí odkaz:
http://arxiv.org/abs/2212.09060
Structural properties of large random maps and lambda-terms may be gleaned by studying the limit distributions of various parameters of interest. In our work we focus on restricted classes of maps and their counterparts in the lambda-calculus, buildi
Externí odkaz:
http://arxiv.org/abs/2106.08291
Publikováno v:
EPTCS 333, 2021, pp. 230-246
The skew monoidal categories of Szlach\'anyi are a weakening of monoidal categories where the three structural laws of left and right unitality and associativity are not required to be isomorphisms but merely transformations in a particular direction
Externí odkaz:
http://arxiv.org/abs/2101.10487
Publikováno v:
EPTCS 332, 2021, pp. 35-53
In this paper, we develop the proof theory of skew prounital closed categories. These are variants of the skew closed categories of Street where the unit is not represented. Skew closed categories in turn are a weakening of the closed categories of E
Externí odkaz:
http://arxiv.org/abs/2101.03809
Szlach\'anyi's skew monoidal categories are a well-motivated variation of monoidal categories in which the unitors and associator are not required to be natural isomorphisms, but merely natural transformations in a particular direction. We present a
Externí odkaz:
http://arxiv.org/abs/2003.05213
Autor:
Zeilberger, Doron, Zeilberger, Noam
We recall the notion of fractional enumeration and immediately focus on the fractional counting of integer partitions, where each partition gets credit equal to the reciprocal of the product of its parts. We raise two intriguing questions regarding t
Externí odkaz:
http://arxiv.org/abs/1810.12701
Autor:
Zeilberger, Noam
Building on recently established enumerative connections between lambda calculus and the theory of embedded graphs (or "maps"), this paper develops an analogy between typing (of lambda terms) and coloring (of maps). Our starting point is the classica
Externí odkaz:
http://arxiv.org/abs/1804.10540
Autor:
Zeilberger, Noam
Publikováno v:
Logical Methods in Computer Science, Volume 15, Issue 1 (February 5, 2019) lmcs:4406
We introduce a sequent calculus with a simple restriction of Lambek's product rules that precisely captures the classical Tamari order, i.e., the partial order on fully-bracketed words (equivalently, binary trees) induced by a semi-associative law (e
Externí odkaz:
http://arxiv.org/abs/1803.10080