Zobrazeno 1 - 10
of 65
pro vyhledávání: '"Jean-Camille Birget"'
The symmetric Post Correspondence Problem, and errata for the freeness problem for matrix semigroups
Publikováno v:
International Journal of Algebra and Computation. 32:1261-1274
In this paper, we define the symmetric Post Correspondence Problem (PCP) and prove that it is undecidable. As an application, we show that the original proof of undecidability of the freeness problem for [Formula: see text] integer matrix semigroups
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::87e1115b21fbfc18ef1d67271a28fb92
https://doi.org/10.1142/s0218196722500540
https://doi.org/10.1142/s0218196722500540
Autor:
Jean-Camille Birget
Publikováno v:
Journal of Algebra. 553:268-318
We prove that the word problem of the Brin-Thompson group nV over a finite generating set is coNP -complete for every n ≥ 2 . It is known that { n V : n ≥ 1 } is an infinite family of infinite, finitely presented, simple groups. We also prove tha
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::6593b313ab444fe5b4427872e69c6d88
https://doi.org/10.1016/j.jalgebra.2020.02.013
https://doi.org/10.1016/j.jalgebra.2020.02.013
Autor:
Jean-Camille Birget
Publikováno v:
Communications in Algebra. 48:3429-3438
We give a direct proof that all Higman-Thompson groups of the form Gk,1 (for k≥2) are embedded in one another, which is a recent result of N. Matte Bon. This extends the embeddings given by Higman ...
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f3f80e31d721e325b3157e088d4fadb2
https://doi.org/10.1080/00927872.2020.1739290
https://doi.org/10.1080/00927872.2020.1739290
Autor:
Jean-Camille Birget
Publikováno v:
Semigroup Forum. 98:369-397
We study the P versus NP problem through properties of functions and monoids, continuing the work of [3]. Here we consider inverse monoids whose properties and relationships determine whether P is different from NP, or whether injective one-way funct
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::41c0e95c4be2d3bc8bbb9a4514e80bd2
https://doi.org/10.1007/s00233-018-9990-x
https://doi.org/10.1007/s00233-018-9990-x
Autor:
Jean-Camille Birget
Publikováno v:
International Journal of Algebra and Computation. 28:791-835
We continue with the functional approach to the P -versus- NP problem, begun in [J. C. Birget, Semigroups and one-way functions, Int. J. Algebra Comput. 25(1–2) (2015) 3–36; J. C. Birget, Infinitely generated semigroups and polynomial complexity,
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::f902138f99694a7b1f6932e8cf34560d
https://doi.org/10.1142/s0218196718500364
https://doi.org/10.1142/s0218196718500364
Autor:
Jean-Camille Birget
Publikováno v:
International Journal of Algebra and Computation. 26:727-750
This paper continues the functional approach to the [Formula: see text]-vs.-[Formula: see text] problem, begun in [J. C. Birget, Semigroups and one-way functions, Internat. J. Algebra Comput. 25 (1–2) (2015) 3–36]. Here, we focus on the monoid [F
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::2a6bba67204ca1a0e5c4b9822ef3b2fe
https://doi.org/10.1142/s0218196716500314
https://doi.org/10.1142/s0218196716500314
Publikováno v:
J. Appl. Probab. 51, no. 1 (2014), 1-18
We construct a wavelet-based almost-sure uniform approximation of fractional Brownian motion (FBM) (Bt(H))_t∈[0,1] of Hurst index H ∈ (0, 1). Our results show that, by Haar wavelets which merely have one vanishing moment, an almost-sure uniform e
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::6a0520eb5056b60f911513c1139bbc38
https://doi.org/10.1239/jap/1395771410
https://doi.org/10.1239/jap/1395771410
Autor:
Jean-Camille Birget
Publikováno v:
International Journal of Foundations of Computer Science. 22:1925-1938
We reprove a result of Boppana and Lagarias: If Pi_2^P is different from Sigma_2^P then there exists a partial function f that is computable by a polynomial-size family of circuits, but no inverse of f is computable by a polynomial-size family of cir
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::a6f4e269445a10a04611fd06eb97e8e7
https://doi.org/10.1142/s0129054111009124
https://doi.org/10.1142/s0129054111009124
Autor:
Jean-Camille Birget
Publikováno v:
International Journal of Algebra and Computation. 21:1-34
The Thompson–Higman groups Gk,i have a natural generalization to monoids, called Mk,i, and inverse monoids, called Invk,i. We study some structural features of Mk,i and Invk,i and investigate the computational complexity of related decision problem
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::3019191adc48bce7a7771f5d2a5a7a90
https://doi.org/10.1142/s0218196711006066
https://doi.org/10.1142/s0218196711006066
Autor:
Jean-Camille Birget
Publikováno v:
International Journal of Algebra and Computation. 20:489-524
We study the monoid generalization Mk, 1 of the Thompson–Higman groups, and we characterize the [Formula: see text]- and the [Formula: see text]-order of Mk, 1. Although Mk, 1 has only one nonzero [Formula: see text]-class and k-1 nonzero [Formula:
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_________::10495e07c339159a999db08398179ef4
https://doi.org/10.1142/s0218196710005741
https://doi.org/10.1142/s0218196710005741