11 Search Results for "Jeandel, Emmanuel"

Document
DOI: 10.4230/LIPIcs.FSCD.2022.13
Addition and Differentiation of ZX-Diagrams

Authors: Emmanuel Jeandel, Simon Perdrix, and Margarita Veshchezerova

Published in: LIPIcs, Volume 228, 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)

Abstract
The ZX-calculus is a powerful framework for reasoning in quantum computing. It provides in particular a compact representation of matrices of interests. A peculiar property of the ZX-calculus is the absence of a formal sum allowing the linear combinations of arbitrary ZX-diagrams. The universality of the formalism guarantees however that for any two ZX-diagrams, the sum of their interpretations can be represented by a ZX-diagram. We introduce a general, inductive definition of the addition of ZX-diagrams, relying on the construction of controlled diagrams. Based on this addition technique, we provide an inductive differentiation of ZX-diagrams. Indeed, given a ZX-diagram with variables in the description of its angles, one can differentiate the diagram according to one of these variables. Differentiation is ubiquitous in quantum mechanics and quantum computing (e.g. for solving optimization problems). Technically, differentiation of ZX-diagrams is strongly related to summation as witnessed by the product rules. We also introduce an alternative, non inductive, differentiation technique rather based on the isolation of the variables. Finally, we apply our results to deduce a diagram for an Ising Hamiltonian.
Cite as

Emmanuel Jeandel, Simon Perdrix, and Margarita Veshchezerova. Addition and Differentiation of ZX-Diagrams. In 7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 228, pp. 13:1-13:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.FSCD.2022.13,
  author =	{Jeandel, Emmanuel and Perdrix, Simon and Veshchezerova, Margarita},
  title =	{{Addition and Differentiation of ZX-Diagrams}},
  booktitle =	{7th International Conference on Formal Structures for Computation and Deduction (FSCD 2022)},
  pages =	{13:1--13:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-233-4},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{228},
  editor =	{Felty, Amy P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSCD.2022.13},
  URN =		{urn:nbn:de:0030-drops-162946},
  doi =		{10.4230/LIPIcs.FSCD.2022.13},
  annote =	{Keywords: ZX calculus, Addition of ZX diagrams, Diagrammatic differentiation}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2022.111
Computability of Finite Simplicial Complexes

Authors: Djamel Eddine Amir and Mathieu Hoyrup

Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)

Abstract
The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres and closed manifolds: if a set X is homeomorphic to a sphere or a closed manifold, then any algorithm that semicomputes X in some sense can be converted into an algorithm that fully computes X. In other words, the topological properties of X enable one to derive full information about X from partial information about X. In that case, we say that X has computable type. Those results have been obtained by Miller, Iljazović, Sušić and others in the recent years. A similar notion of computable type was also defined for pairs (X,A) in order to cover more spaces, such as compact manifolds with boundary and finite graphs with endpoints. We investigate the higher dimensional analog of graphs, namely the pairs (X,A) where X is a finite simplicial complex and A is a subcomplex of X. We give two topological characterizations of the pairs having computable type. The first one uses a global property of the pair, that we call the ε-surjection property. The second one uses a local property of neighborhoods of vertices, called the surjection property. We give a further characterization for 2-dimensional simplicial complexes, by identifying which local neighborhoods have the surjection property. Using these characterizations, we give non-trivial applications to two famous sets: we prove that the dunce hat does not have computable type whereas Bing’s house does. Important concepts from topology, such as absolute neighborhood retracts and topological cones, play a key role in our proofs.
Cite as

Djamel Eddine Amir and Mathieu Hoyrup. Computability of Finite Simplicial Complexes. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 111:1-111:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.ICALP.2022.111,
  author =	{Amir, Djamel Eddine and Hoyrup, Mathieu},
  title =	{{Computability of Finite Simplicial Complexes}},
  booktitle =	{49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)},
  pages =	{111:1--111:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-235-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{229},
  editor =	{Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.111},
  URN =		{urn:nbn:de:0030-drops-164522},
  doi =		{10.4230/LIPIcs.ICALP.2022.111},
  annote =	{Keywords: Computable Type, Simplicial Complex, Surjection Property, Topological Cone, Absolute Neighborhood Retract, Dunce Hat, Bing’s House}
}
Document
DOI: 10.4230/OASIcs.AUTOMATA.2021.9
An Effective Construction for Cut-And-Project Rhombus Tilings with Global n-Fold Rotational Symmetry

Authors: Victor H. Lutfalla

Published in: OASIcs, Volume 90, 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)

Abstract
We give an explicit and effective construction for rhombus cut-and-project tilings with global n-fold rotational symmetry for any n. This construction is based on the dualization of regular n-fold multigrids. The main point is to prove the regularity of these multigrids, for this we use a result on trigonometric diophantine equations. A SageMath program that computes these tilings and outputs svg files is publicly available in [Lutfalla, 2021].
Cite as

Victor H. Lutfalla. An Effective Construction for Cut-And-Project Rhombus Tilings with Global n-Fold Rotational Symmetry. In 27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021). Open Access Series in Informatics (OASIcs), Volume 90, pp. 9:1-9:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{lutfalla:OASIcs.AUTOMATA.2021.9,
  author =	{Lutfalla, Victor H.},
  title =	{{An Effective Construction for Cut-And-Project Rhombus Tilings with Global n-Fold Rotational Symmetry}},
  booktitle =	{27th IFIP WG 1.5 International Workshop on Cellular Automata and Discrete Complex Systems (AUTOMATA 2021)},
  pages =	{9:1--9:12},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-189-4},
  ISSN =	{2190-6807},
  year =	{2021},
  volume =	{90},
  editor =	{Castillo-Ramirez, Alonso and Guillon, Pierre and Perrot, K\'{e}vin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.AUTOMATA.2021.9},
  URN =		{urn:nbn:de:0030-drops-140182},
  doi =		{10.4230/OASIcs.AUTOMATA.2021.9},
  annote =	{Keywords: Cut-and-project tiling, Rhombus tiling, Aperiodic order, Rotational symmetry, De Bruijn multigrid, Trigonometric diophantine equations}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.24
PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations

Authors: Alexandre Clément and Simon Perdrix

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We introduce the PBS-calculus to represent and reason on quantum computations involving coherent control of quantum operations. Coherent control, and in particular indefinite causal order, is known to enable multiple computational and communication advantages over classically ordered models like quantum circuits. The PBS-calculus is inspired by quantum optics, in particular the polarising beam splitter (PBS for short). We formalise the syntax and the semantics of the PBS-diagrams, and we equip the language with an equational theory, which is proved to be sound and complete: two diagrams are representing the same quantum evolution if and only if one can be transformed into the other using the rules of the PBS-calculus. Moreover, we show that the equational theory is minimal. Finally, we consider applications like the implementation of controlled permutations and the unrolling of loops.
Cite as

Alexandre Clément and Simon Perdrix. PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{clement_et_al:LIPIcs.MFCS.2020.24,
  author =	{Cl\'{e}ment, Alexandre and Perdrix, Simon},
  title =	{{PBS-Calculus: A Graphical Language for Coherent Control of Quantum Computations}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{24:1--24:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.24},
  URN =		{urn:nbn:de:0030-drops-126921},
  doi =		{10.4230/LIPIcs.MFCS.2020.24},
  annote =	{Keywords: Quantum Computing, Diagrammatic Language, Completeness, Quantum Control, Polarising Beam Splitter, Categorical Quantum Mechanics, Quantum Switch}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2020.118
A Recipe for Quantum Graphical Languages

Authors: Titouan Carette and Emmanuel Jeandel

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
Different graphical calculi have been proposed to represent quantum computation. First the ZX-calculus [Coecke and Duncan, 2011], followed by the ZW-calculus [Hadzihasanovic, 2015] and then the ZH-calculus [Backens and Kissinger, 2018]. We can wonder if new ZX-like calculi will continue to be proposed forever. This article answers negatively. All those language share a common core structure we call Z^*-algebras. We classify Z^*-algebras up to isomorphism in two dimensional Hilbert spaces and show that they are all variations of the aforementioned calculi. We do the same for linear relations and show that the calculus of [Bonchi et al., 2017] is essentially the unique one.
Cite as

Titouan Carette and Emmanuel Jeandel. A Recipe for Quantum Graphical Languages. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 118:1-118:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{carette_et_al:LIPIcs.ICALP.2020.118,
  author =	{Carette, Titouan and Jeandel, Emmanuel},
  title =	{{A Recipe for Quantum Graphical Languages}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{118:1--118:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.118},
  URN =		{urn:nbn:de:0030-drops-125250},
  doi =		{10.4230/LIPIcs.ICALP.2020.118},
  annote =	{Keywords: Categorical Quantum Mechanics, Quantum Computing, Category Theory}
}
Document
Track B: Automata, Logic, Semantics, and Theory of Programming
DOI: 10.4230/LIPIcs.ICALP.2019.108
Completeness of Graphical Languages for Mixed States Quantum Mechanics (Track B: Automata, Logic, Semantics, and Theory of Programming)

Authors: Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart

Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)

Abstract
There exist several graphical languages for quantum information processing, like quantum circuits, ZX-Calculus, ZW-Calculus, etc. Each of these languages forms a dagger-symmetric monoidal category (dagger-SMC) and comes with an interpretation functor to the dagger-SMC of (finite dimension) Hilbert spaces. In the recent years, one of the main achievements of the categorical approach to quantum mechanics has been to provide several equational theories for most of these graphical languages, making them complete for various fragments of pure quantum mechanics. We address the question of the extension of these languages beyond pure quantum mechanics, in order to reason on mixed states and general quantum operations, i.e. completely positive maps. Intuitively, such an extension relies on the axiomatisation of a discard map which allows one to get rid of a quantum system, operation which is not allowed in pure quantum mechanics. We introduce a new construction, the discard construction, which transforms any dagger-symmetric monoidal category into a symmetric monoidal category equipped with a discard map. Roughly speaking this construction consists in making any isometry causal. Using this construction we provide an extension for several graphical languages that we prove to be complete for general quantum operations. However this construction fails for some fringe cases like the Clifford+T quantum mechanics, as the category does not have enough isometries.
Cite as

Titouan Carette, Emmanuel Jeandel, Simon Perdrix, and Renaud Vilmart. Completeness of Graphical Languages for Mixed States Quantum Mechanics (Track B: Automata, Logic, Semantics, and Theory of Programming). In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 108:1-108:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{carette_et_al:LIPIcs.ICALP.2019.108,
  author =	{Carette, Titouan and Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud},
  title =	{{Completeness of Graphical Languages for Mixed States Quantum Mechanics}},
  booktitle =	{46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
  pages =	{108:1--108:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-109-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{132},
  editor =	{Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.108},
  URN =		{urn:nbn:de:0030-drops-106844},
  doi =		{10.4230/LIPIcs.ICALP.2019.108},
  annote =	{Keywords: Quantum Computing, Quantum Categorical Mechanics, Category Theory, Mixed States, Completely Positive Maps}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.23
Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts

Authors: Julien Destombes and Andrei Romashchenko

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
We suggest necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on Z^2 with very low block complexity: the number of globally admissible patterns of size n x n grows only as a polynomial in n.
Cite as

Julien Destombes and Andrei Romashchenko. Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 23:1-23:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{destombes_et_al:LIPIcs.STACS.2019.23,
  author =	{Destombes, Julien and Romashchenko, Andrei},
  title =	{{Resource-Bounded Kolmogorov Complexity Provides an Obstacle to Soficness of Multidimensional Shifts}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{23:1--23:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.23},
  URN =		{urn:nbn:de:0030-drops-102624},
  doi =		{10.4230/LIPIcs.STACS.2019.23},
  annote =	{Keywords: Sofic shifts, Block complexity, Kolmogorov complexity}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.40
A Characterization of Subshifts with Computable Language

Authors: Emmanuel Jeandel and Pascal Vanier

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
Subshifts are sets of colorings of Z^d by a finite alphabet that avoid some family of forbidden patterns. We investigate here some analogies with group theory that were first noticed by the first author. In particular we prove several theorems on subshifts inspired by Higman’s embedding theorems of group theory, among which, the fact that subshifts with a computable language can be obtained as restrictions of minimal subshifts of finite type.
Cite as

Emmanuel Jeandel and Pascal Vanier. A Characterization of Subshifts with Computable Language. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 40:1-40:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.STACS.2019.40,
  author =	{Jeandel, Emmanuel and Vanier, Pascal},
  title =	{{A Characterization of Subshifts with Computable Language}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{40:1--40:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.40},
  URN =		{urn:nbn:de:0030-drops-102798},
  doi =		{10.4230/LIPIcs.STACS.2019.40},
  annote =	{Keywords: subshifts, computability, Enumeration degree, Turing degree, minimal subshifts}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2017.11
ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics

Authors: Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang

Published in: LIPIcs, Volume 83, 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)

Abstract
The ZX-Calculus is a powerful graphical language for quantum mechanics and quantum information processing. The completeness of the language - i.e. the ability to derive any true equation - is a crucial question. In the quest of a complete ZX-calculus, supplementarity has been recently proved to be necessary for quantum diagram reasoning (MFCS 2016). Roughly speaking, supplementarity consists in merging two subdiagrams when they are parameterized by antipodal angles. We introduce a generalised supplementarity - called cyclotomic supplementarity - which consists in merging n subdiagrams at once, when the n angles divide the circle into equal parts. We show that when n is an odd prime number, the cyclotomic supplementarity cannot be derived, leading to a countable family of new axioms for diagrammatic quantum reasoning. We exhibit another new simple axiom that cannot be derived from the existing rules of the ZX-Calculus, implying in particular the incompleteness of the language for the so-called Clifford+T quantum mechanics. We end up with a new axiomatisation of an extended ZX-Calculus, including an axiom schema for the cyclotomic supplementarity.
Cite as

Emmanuel Jeandel, Simon Perdrix, Renaud Vilmart, and Quanlong Wang. ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics. In 42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 83, pp. 11:1-11:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.MFCS.2017.11,
  author =	{Jeandel, Emmanuel and Perdrix, Simon and Vilmart, Renaud and Wang, Quanlong},
  title =	{{ZX-Calculus: Cyclotomic Supplementarity and Incompleteness for Clifford+T Quantum Mechanics}},
  booktitle =	{42nd International Symposium on Mathematical Foundations of Computer Science (MFCS 2017)},
  pages =	{11:1--11:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-046-0},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{83},
  editor =	{Larsen, Kim G. and Bodlaender, Hans L. and Raskin, Jean-Francois},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2017.11},
  URN =		{urn:nbn:de:0030-drops-81173},
  doi =		{10.4230/LIPIcs.MFCS.2017.11},
  annote =	{Keywords: Categorical Quantum Mechanincs, ZX-Calculus, Completeness, Cyclotomic Supplmentarity, Clifford+T}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.421
Computability of the entropy of one-tape Turing machines

Authors: Emmanuel Jeandel

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We prove that the maximum speed and the entropy of a one-tape Turing machine are computable, in the sense that we can approximate them to any given precision . This is counterintuitive, as all dynamical properties are usually undecidable for Turing machines. The result is quite specific to one-tape Turing machines, as it is not true anymore for two-tape Turing machines by the results of Blondel et al., and uses the approach of crossing sequences introduced by Hennie.
Cite as

Emmanuel Jeandel. Computability of the entropy of one-tape Turing machines. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 421-432, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{jeandel:LIPIcs.STACS.2014.421,
  author =	{Jeandel, Emmanuel},
  title =	{{Computability of the entropy of one-tape Turing machines}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{421--432},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.421},
  URN =		{urn:nbn:de:0030-drops-44767},
  doi =		{10.4230/LIPIcs.STACS.2014.421},
  annote =	{Keywords: Turing Machines, Dynamical Systems, Entropy, Crossing Sequences, Automata}
}
Document
DOI: 10.4230/LIPIcs.STACS.2013.490
Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type

Authors: Emmanuel Jeandel and Pascal Vanier

Published in: LIPIcs, Volume 20, 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)

Abstract
Subshifts of finite type are sets of colorings of the plane defined by local constraints. They can be seen as a discretization of continuous dynamical systems. We investigate here the hardness of deciding factorization, conjugacy and embedding of subshifts of finite type (SFTs) in dimension d > 1. In particular, we prove that the factorization problem is Sigma^0_3-complete and that the conjugacy and embedding problems are Sigma^0_1-complete in the arithmetical hierarchy.
Cite as

Emmanuel Jeandel and Pascal Vanier. Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type. In 30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 20, pp. 490-501, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{jeandel_et_al:LIPIcs.STACS.2013.490,
  author =	{Jeandel, Emmanuel and Vanier, Pascal},
  title =	{{Hardness of Conjugacy, Embedding and Factorization of multidimensional Subshifts of Finite Type}},
  booktitle =	{30th International Symposium on Theoretical Aspects of Computer Science (STACS 2013)},
  pages =	{490--501},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-50-7},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{20},
  editor =	{Portier, Natacha and Wilke, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2013.490},
  URN =		{urn:nbn:de:0030-drops-39592},
  doi =		{10.4230/LIPIcs.STACS.2013.490},
  annote =	{Keywords: Subshifts, Computability, Factorization, Embedding, Conjugacy}
}
  • Refine by Author
  • 7 Jeandel, Emmanuel
  • 4 Perdrix, Simon
  • 2 Carette, Titouan
  • 2 Vanier, Pascal
  • 2 Vilmart, Renaud
  • Show More...

  • Refine by Classification
  • 4 Theory of computation → Quantum computation theory
  • 2 Mathematics of computing
  • 2 Mathematics of computing → Combinatorics
  • 2 Theory of computation → Axiomatic semantics
  • 1 Hardware → Quantum communication and cryptography
  • Show More...

  • Refine by Keyword
  • 3 Quantum Computing
  • 2 Categorical Quantum Mechanics
  • 2 Category Theory
  • 2 Completeness
  • 1 Absolute Neighborhood Retract
  • Show More...

  • Refine by Type
  • 11 document

  • Refine by Publication Year
  • 3 2019
  • 2 2020
  • 2 2022
  • 1 2013
  • 1 2014
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact