Episciences.org
Not a member yet
6707 research outputs found
Sort by
Triangular arrangements on the projective plane
No full textIn this work we study line arrangements consisting in lines passing throughthree non-aligned points. We call them triangular arrangements. We prove thatany combinatorics of a triangular arrangement is always realized by aRoots-of-Unity-Arrangement, which is a particular class of triangulararrangements. Among these Roots-of Unity-Arrangements, we provide conditionsthat ensure their freeness. Finally, we give two triangular arrangements havingthe same weak combinatorics, such that one is free but the other one is not.Comment: 20 pages. Published in \'Epijournal de G\'eom\'etrie Alg\'ebrique. Section 4 has been deeply revised due to an incorrect statement pointed out by the refere
Extremal problems of double stars
No full textIn a generalized Tur\'an problem, two graphs and are given and thequestion is the maximum number of copies of in an -free graph of order. In this paper, we study the number of double stars intriangle-free graphs. We also study an opposite version of this question: whatis the maximum number edges/triangles in graphs with double star typerestrictions, which leads us to study two questions related to the extremalnumber of triangles or edges in graphs with degree-sum constraints overadjacent or non-adjacent vertices.Comment: 18 pages, 4 figure
The number of {1243, 2134}-avoiding permutations
No full textWe show that the counting sequence for permutations avoiding both of the(classical) patterns 1243 and 2134 has the algebraic generating functionsupplied by Vaclav Kotesovec for sequence A164651 in The On-Line Encyclopediaof Integer Sequences.Comment: 8 pages, 2 figures, final version, to appear, Discrete Mathematics & Theoretical Computer Science (DMTCS
Bijective proofs for Eulerian numbers of types B and D
No full textLet \Bigl\langle\matrix{n\cr k}\Bigr\rangle, \Bigl\langle\matrix{B_n\crk}\Bigr\rangle, and \Bigl\langle\matrix{D_n\cr k}\Bigr\rangle be theEulerian numbers in the types A, B, and D, respectively -- that is, the numberof permutations of n elements with descents, the number of signedpermutations (of elements) with type B descents, the number of evensigned permutations (of elements) with type D descents. Let S_n(t) =\sum_{k = 0}^{n-1} \Bigl\langle\matrix{n\cr k}\Bigr\rangle t^k, B_n(t) =\sum_{k = 0}^n \Bigl\langle\matrix{B_n\cr k}\Bigr\rangle t^k, and D_n(t) =\sum_{k = 0}^n \Bigl\langle\matrix{D_n\cr k}\Bigr\rangle t^k. We givebijective proofs of the identity and of Stembridge's identity These bijective proofs rely on a representation ofsigned permutations as paths. Using this representation we also establish abijective correspondence between even signed permutations and pairs with a threshold graph and a degree ordering of ,which we use to obtain bijective proofs of enumerative results for thresholdgraphs.Comment: Discrete Mathematics and Theoretical Computer Science, 202
Pushdown Automata and Context-Free Grammars in Bisimulation Semantics
No full textThe Turing machine models an old-fashioned computer, that does not interactwith the user or with other computers, and only does batch processing.Therefore, we came up with a Reactive Turing Machine that does not have theseshortcomings. In the Reactive Turing Machine, transitions have labels to give anotion of interactivity. In the resulting process graph, we use bisimilarityinstead of language equivalence. Subsequently, we considered other classical theorems and notions fromautomata theory and formal languages theory. In this paper, we consider theclassical theorem of the correspondence between pushdown automata andcontext-free grammars. By changing the process operator of sequentialcomposition to a sequencing operator with intermediate acceptance, we get abetter correspondence in our setting. We find that the missing ingredient torecover the full correspondence is the addition of a notion of state awareness
A modular construction of type theories
No full textThe lambda-Pi-calculus modulo theory is a logical framework in which manytype systems can be expressed as theories. We present such a theory, the theoryU, where proofs of several logical systems can be expressed. Moreover, weidentify a sub-theory of U corresponding to each of these systems, and provethat, when a proof in U uses only symbols of a sub-theory, then it is a proofin that sub-theory
Characterizing Omega-Regularity through Finite-Memory Determinacy of Games on Infinite Graphs
No full textWe consider zero-sum games on infinite graphs, with objectives specified assets of infinite words over some alphabet of colors. A well-studied class ofobjectives is the one of -regular objectives, due to its relation tomany natural problems in theoretical computer science. We focus on the strategycomplexity question: given an objective, how much memory does each playerrequire to play as well as possible? A classical result is that finite-memorystrategies suffice for both players when the objective is -regular. Weshow a reciprocal of that statement: when both players can play optimally witha chromatic finite-memory structure (i.e., whose updates can only observecolors) in all infinite game graphs, then the objective must be-regular. This provides a game-theoretic characterization of-regular objectives, and this characterization can help in obtainingmemory bounds. Moreover, a by-product of our characterization is a newone-to-two-player lift: to show that chromatic finite-memory structures sufficeto play optimally in two-player games on infinite graphs, it suffices to showit in the simpler case of one-player games on infinite graphs. We illustrateour results with the family of discounted-sum objectives, for which-regularity depends on the value of some parameters.Comment: A previous conference version appeared in STACS 2022. 48 pages, 14 figure
A note on calculi for non-deterministic many-valued logics
No full textWe present two deductively equivalent calculi for non-deterministicmany-valued logics. One is defined by axioms and the other - by rules ofinference. The two calculi are obtained from the truth tables of the logicunder consideration in a straightforward manner. We prove soundness and strongcompleteness theorems for both calculi and also prove the cut eliminationtheorem for the calculi defined by rules of inference
Various notions of (co)simplicial (pre)sheaves
No full textThe phrase "(co)simplicial (pre)sheaf" can be reasonably interpreted inmultiple ways. In this survey we study how the various notions familiar to theauthor relate to one another. We end by giving some example applications of themost general of these notions.Comment: 20 pages, comments welcom
Prioritise the Best Variation
No full textBinary session types guarantee communication safety and session fidelity, butalone they cannot rule out deadlocks arising from the interleaving of differentsessions. In Classical Processes (CP)a process calculus based on classicallinear logicdeadlock freedom is guaranteed by combining channel creation andparallel composition under the same logical cut rule. Similarly, in GoodVariation (GV)a linear concurrent -calculusdeadlock freedom isguaranteed by combining channel creation and thread spawning under the sameoperation, called fork. In both CP and GV, deadlock freedom is achieved at the expense ofexpressivity, as the only processes allowed are tree-structured. Dardha and Gaydefine Priority CP (PCP), which allows cyclic-structured processes and restoresdeadlock freedom by using priorities, in line with Kobayashi and Padovani. Following PCP, we present Priority GV (PGV), a variant of GV which decoupleschannel creation from thread spawning. Consequently, we type cyclic-structuredprocesses and restore deadlock freedom by using priorities. We show that ourtype system is sound by proving subject reduction and progress. We define anencoding from PCP to PGV and prove that the encoding preserves typing and issound and complete with respect to the operational semantics