DROPS

Document

Track B: Automata, Logic, Semantics, and Theory of Programming

DOI: 10.4230/LIPIcs.ICALP.2025.139

Minimality and Computability of Languages of G-Shifts

Authors: Djamel Eddine Amir and Benjamin Hellouin de Menibus

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract

Motivated by the notion of strong computable type for sets in computable analysis, we define the notion of strong computable type for G-shifts, where G is a finitely generated group with decidable word problem. A G-shift has strong computable type if one can compute its language from the complement of its language. We obtain a characterization of G-shifts with strong computable type in terms of a notion of minimality with respect to properties with a bounded computational complexity. We provide a self-contained direct proof, and also explain how this characterization can be obtained from an existing similar characterization for sets by Amir and Hoyrup, and discuss its connexions with results by Jeandel on closure spaces. We apply this characterization to several classes of shifts that are minimal with respect to specific properties. This provides a unifying approach that not only generalizes many existing results but also has the potential to yield new findings effortlessly. In contrast to the case of sets, we prove that strong computable type for G-shifts is preserved under products. We conclude by discussing some generalizations and future directions.

Cite as

Djamel Eddine Amir and Benjamin Hellouin de Menibus. Minimality and Computability of Languages of G-Shifts. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 139:1-139:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{amir_et_al:LIPIcs.ICALP.2025.139,
  author =	{Amir, Djamel Eddine and Hellouin de Menibus, Benjamin},
  title =	{{Minimality and Computability of Languages of G-Shifts}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{139:1--139:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.139},
  URN =		{urn:nbn:de:0030-drops-235161},
  doi =		{10.4230/LIPIcs.ICALP.2025.139},
  annote =	{Keywords: shifts, subshifts, minimal shifts, computable language, computability, strong computable type, descriptive complexity}
}

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.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}
}

Search Results

Documents authored by Amir, Djamel Eddine

Minimality and Computability of Languages of G-Shifts

Abstract

Cite as

Computability of Finite Simplicial Complexes

Abstract

Cite as

Thanks for your feedback!

Could not send message