Zobrazeno 1 - 10
of 20
pro vyhledávání: '"Yves Lafont"'
Linear logic, introduced in 1986 by J.-Y. Girard, is based upon a fine grain analysis of the main proof-theoretical notions of logic. The subject develops along the lines of denotational semantics, proof nets and the geometry of interaction. Its basi
Autor:
Yves Lafont
Publikováno v:
Applied Categorical Structures. 15:415-437
We present various results of the last 20 years converging towards a homotopical theory of computation. This new theory is based on two crucial notions: polygraphs (introduced by Albert Burroni) and polygraphic resolutions (introduced by Francois Met
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::20ba56d8a023fb72671662018156236e
https://doi.org/10.1007/s10485-007-9083-6
https://doi.org/10.1007/s10485-007-9083-6
Autor:
Yves Lafont
Publikováno v:
Theoretical Computer Science. 318:163-180
We present a subsystem of second-order linear logic with restricted rules for exponentials so that proofs correspond to polynomial time algorithms, and vice versa.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::d945882e39fa2690a82b43122c6e3a74
https://doi.org/10.1016/j.tcs.2003.10.018
https://doi.org/10.1016/j.tcs.2003.10.018
Autor:
Yves Lafont
Publikováno v:
Journal of Pure and Applied Algebra. 184:257-310
Boolean circuits are used to represent programs on finite data. Reversible Boolean circuits and quantum Boolean circuits have been introduced to modelize some physical aspects of computation. Those notions are essential in complexity theory, but we c
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::8c6db4d221c9b5efdced960b122dc40e
https://doi.org/10.1016/s0022-4049(03)00069-0
https://doi.org/10.1016/s0022-4049(03)00069-0
Autor:
Yves Lafont
Publikováno v:
Journal of Symbolic Logic. 61:541-548
Recently, Lincoln, Scedrov and Shankar showed that the multiplicative fragment of second order intuitionistic linear logic is undecidable, using an encoding of second order intuitionistic logic. Their argument applies to the multiplicative-additive f
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::572cfcc45b7605a068aca3b2c6dd4334
https://doi.org/10.2307/2275674
https://doi.org/10.2307/2275674
Autor:
Andre Scedrov, Yves Lafont
Publikováno v:
Information and Computation. 125(1):46-51
The multiplicative fragment of second order propositional linear logic is shown to be undecidable.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::f7d52f50cfbbf3d6b65727d6178691aa
Autor:
Yves Lafont
Publikováno v:
Journal of Pure and Applied Algebra. 98:229-244
Recently, Craig Squier introduced the notion of finite derivation type to show that some finitely presentable monoid has no presentation by means of a finite complete rewriting system. A similar result was already obtained by the same author using ho
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::2f1cab4546ffc279980c6cc7433b8340
https://doi.org/10.1016/0022-4049(94)00043-i
https://doi.org/10.1016/0022-4049(94)00043-i
Autor:
Yves Lafont, François Métayer
Publikováno v:
Journal of Pure and Applied Algebra
Journal of Pure and Applied Algebra, Elsevier, 2009, 213, pp.947-968. ⟨10.1016/j.jpaa.2008.10.005⟩
Journal of Pure and Applied Algebra, 2009, 213, pp.947-968. ⟨10.1016/j.jpaa.2008.10.005⟩
Journal of Pure and Applied Algebra, Elsevier, 2009, 213, pp.947-968. ⟨10.1016/j.jpaa.2008.10.005⟩
Journal of Pure and Applied Algebra, 2009, 213, pp.947-968. ⟨10.1016/j.jpaa.2008.10.005⟩
soumis; International audience; We prove that, for any monoid M, the homology defined by the second author by means of polygraphic resolutions coincides with the homology classically defined by means of resolutions by free ZM-modules.
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::7c08a99199c06849ee8d535358e6777d
https://hal.archives-ouvertes.fr/hal-00148370v2/file/polrhm.pdf
https://hal.archives-ouvertes.fr/hal-00148370v2/file/polrhm.pdf
Autor:
Alain Prouté, Yves Lafont
Publikováno v:
Mathematical Structures in Computer Science. 1:297-326
We present a result of C.C. Squier relating two topics:— the canonical rewriting systems, which have been widely studied by computer scientists as a tool for solving word problems,— the homology of groups (more generally of monoids), which belong
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::acf1644e885a72ac9cb5b0719f617df7
https://doi.org/10.1017/s096012950000133x
https://doi.org/10.1017/s096012950000133x
Autor:
Pierre Rannou, Yves Lafont
Publikováno v:
Rewriting Techniques and Applications ISBN: 9783540705888
RTA
RTA
Orthogonal diagramsrepresent decompositions of isometries of ?ninto symmetries and rotations. Some convergent (that is noetherian and confluent) rewrite system for this structure was introduced by the first author. One of the rules is similar to Yang
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::467fd0f62d04086800b4ac881f2ed453
https://doi.org/10.1007/978-3-540-70590-1_16
https://doi.org/10.1007/978-3-540-70590-1_16