Zobrazeno 1 - 10
of 10
pro vyhledávání: '"Etienne Moutot"'
Autor:
Solène J. Esnay, Etienne Moutot
Publikováno v:
Theoretical Computer Science. 917:31-50
Publikováno v:
Natural Computing
Natural Computing, 2021, Unconventional Computing and Natural Computing — Selected papers from 2019 conference, 20 (2), pp.259-270. ⟨10.1007/s11047-020-09815-1⟩
Natural Computing, 2021, Unconventional Computing and Natural Computing — Selected papers from 2019 conference, 20 (2), pp.259-270. ⟨10.1007/s11047-020-09815-1⟩
We present new results on the computational limitations of affine automata (AfAs). First, we show that using the endmarker does not increase the computational power of AfAs. Second, we show that the computation of bounded-error rational-valued AfAs c
Publikováno v:
Theory of Computing Systems
Theory of Computing Systems, Springer Verlag, 2020, 64 (1), pp.35-61. ⟨10.1007/s00224-019-09931-1⟩
Theory of Computing Systems, 2020, 64 (1), pp.35-61. ⟨10.1007/s00224-019-09931-1⟩
Theory of Computing Systems, Springer Verlag, 2020, 64 (1), pp.35-61. ⟨10.1007/s00224-019-09931-1⟩
Theory of Computing Systems, 2020, 64 (1), pp.35-61. ⟨10.1007/s00224-019-09931-1⟩
In this paper we study the directions of periodicity of multidimensional subshifts of finite type (SFTs) and of multidimensional effectively closed and sofic subshifts. A configuration of a subshift has a slope of periodicity if it is periodic in exa
Autor:
Etienne Moutot, Jarkko Kari
Publikováno v:
Theoretical Computer Science
Theoretical Computer Science, Elsevier, 2019, ⟨10.1016/j.tcs.2018.12.029⟩
Theoretical Computer Science, 2019, ⟨10.1016/j.tcs.2018.12.029⟩
Theoretical Computer Science, Elsevier, 2019, ⟨10.1016/j.tcs.2018.12.029⟩
Theoretical Computer Science, 2019, ⟨10.1016/j.tcs.2018.12.029⟩
We study Nivat's conjecture on algebraic subshifts and prove that in some of them every low complexity configuration is periodic. This is the case in the Ledrappier subshift (the 3-dot system) and, more generally, in all two-dimensional algebraic sub
Publikováno v:
UCNC2019
UCNC2019, Jun 2019, Tokyo, Japan. pp.108-121, ⟨10.1007/978-3-030-19311-9_10⟩
Unconventional Computation and Natural Computation ISBN: 9783030193102
UCNC
UCNC2019, Jun 2019, Tokyo, Japan. pp.108-121, ⟨10.1007/978-3-030-19311-9_10⟩
Unconventional Computation and Natural Computation ISBN: 9783030193102
UCNC
We present two new results on the computational limitations of affine automata. First, we show that the computation of bounded-error rational-values affine automata is simulated in logarithmic space. Second, we give an impossibility result for algebr
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::24a9926fac20c3cd951a4fde12613091
https://hal.archives-ouvertes.fr/hal-02157985
https://hal.archives-ouvertes.fr/hal-02157985
Autor:
Etienne Moutot, Jarkko Kari
Publikováno v:
STACS 2020
STACS 2020, Mar 2020, Montpellier, France. ⟨10.4230/LIPIcs.STACS.2020.14⟩
Theory of Computing Systems
Theory of Computing Systems, Springer Verlag, 2021, ⟨10.1007/s00224-021-10063-8⟩
Theory of Computing Systems, 2021, ⟨10.1007/s00224-021-10063-8⟩
STACS 2020, Mar 2020, Montpellier, France. ⟨10.4230/LIPIcs.STACS.2020.14⟩
Theory of Computing Systems
Theory of Computing Systems, Springer Verlag, 2021, ⟨10.1007/s00224-021-10063-8⟩
Theory of Computing Systems, 2021, ⟨10.1007/s00224-021-10063-8⟩
In this paper we study colorings (or tilings) of the two-dimensional grid $\mathbb{Z}^2$. A coloring is said to be valid with respect to a set $P$ of $n\times m$ rectangular patterns if all $n\times m$ sub-patterns of the coloring are in $P$. A color
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::53b775043d8d8184fa384defada1c19d
http://arxiv.org/abs/1904.01267
http://arxiv.org/abs/1904.01267
Publikováno v:
MFCS2019 44th International Symposium on Mathematical Foundations of Computer Science
MFCS2019 44th International Symposium on Mathematical Foundations of Computer Science, Aug 2019, Aachen, Germany
HAL
MFCS2019 44th International Symposium on Mathematical Foundations of Computer Science, Aug 2019, Aachen, Germany
HAL
We show that the domino problem is undecidable on orbit graphs of non-deterministic substitutions which satisfy a technical property. As an application, we prove that the domino problem is undecidable for the fundamental group of any closed orientabl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::884ee2ade745ecb41dae946237a78e63
http://arxiv.org/abs/1811.08420
http://arxiv.org/abs/1811.08420
Publikováno v:
Natural Computing. 20:271-271
In the original publication of the article, unfortunately, the corrections provided were missed for affiliations, equations and sentences. The original article has been updated with the corrections.
Autor:
Pascal Vanier, Etienne Moutot
Publikováno v:
CSR 2018
CSR 2018, Jun 2018, Moscou, Russia. pp.257--268, ⟨10.1007/978-3-319-90530-3_22⟩
Computer Science – Theory and Applications ISBN: 9783319905297
CSR
CSR 2018, Jun 2018, Moscou, Russia. pp.257--268, ⟨10.1007/978-3-319-90530-3_22⟩
Computer Science – Theory and Applications ISBN: 9783319905297
CSR
In this paper we study the directions of periodicity of three-dimensional subshifts of finite type (SFTs) and in particular their slopes. A configuration of a subshift has a slope of periodicity if it is periodic in exactly one direction, the slope b
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::62b28f28513c91a3f91551547004344d
https://hal.archives-ouvertes.fr/hal-01772574/document
https://hal.archives-ouvertes.fr/hal-01772574/document
Publikováno v:
Language and Automata Theory and Applications
Language and Automata Theory and Applications, Mar 2017, Umeå, Sweden. ⟨10.1007/978-3-319-53733-7_30⟩
Language and Automata Theory and Applications ISBN: 9783319537320
Language and Automata Theory and Applications, Mar 2017, Umeå, Sweden. ⟨10.1007/978-3-319-53733-7_30⟩
Language and Automata Theory and Applications ISBN: 9783319537320
We investigate the computational power of affine automata (AfAs) introduced in [4]. In particular, we present a simpler proof for how to change the cutpoint for any affine language and a method how to reduce error in bounded error case. Moreover, we
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fde1be902668eec45d48fb6f0f67bbde
https://hal.science/hal-01908682
https://hal.science/hal-01908682