Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-08T14:55:15.364Z Has data issue: false hasContentIssue false
  • English
  • Français

Rigidity is undecidable

Published online by Cambridge University Press:  11 March 2014

MIKOŁAJ BOJAŃCZYK ,
STANISŁAW SZAWIEL  and
MAREK ZAWADOWSKI
MIKOŁAJ BOJAŃCZYK
Affiliation:
Institute of Informatics, University of Warsaw, S. Banacha 2, 02-097 Warszawa, Poland Email: bojan@mimuw.edu.pl
STANISŁAW SZAWIEL
Affiliation:
Institute of Mathematics, University of Warsaw, S. Banacha 2, 02-097 Warszawa, Poland Email: szawiel@mimuw.edu.pl; zawado@mimuw.edu.pl
MAREK ZAWADOWSKI
Affiliation:
Institute of Mathematics, University of Warsaw, S. Banacha 2, 02-097 Warszawa, Poland Email: szawiel@mimuw.edu.pl; zawado@mimuw.edu.pl
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

We show that the problem of whether a finite set of regular-linear axioms defines a rigid theory is undecidable.

Information

Type
Paper
Information
Mathematical Structures in Computer Science , Volume 24 , Issue 6 , December 2014 , e240605
Copyright
Copyright © Cambridge University Press 2014 

References

Baader, F. and Nipkow, T. (1998) Term rewriting and all that, Cambridge University Press.Google Scholar
Carboni, A. and Johnstone, P. T. (1995) Connected limits, familial representability and Artin glueing. Mathematical Structures in Computer Science 5 441–459.CrossRefGoogle Scholar
Carboni, A. and Johnstone, P. T. (2004) Corrigenda for ‘Connected limits, familial representability and Artin glueing’. Mathematical Structures in Computer Science 14 (1)185–187.Google Scholar
Joyal, A. (1986) Foncteurs analytiques et espéces de structures. In: Labelle, G. and Leroux, P. (eds.) Combinatoire énumerative. Springer-Verlag Lecture Notes in Mathematics 1234126–159.Google Scholar
Markov, A. A. (1947) On the impossibility of certain algorithms in the theory of associative systems (in Russian). Doklady Akademii Nauk SSSR 55 (7)587–590. (English translation: Comptes Rendus de l'Academie des Sciences de l'URSS (1948) 55 533–586.)Google Scholar
Post, E. (1947) Recursive Unsolvability of a Problem of Thue. Journal of Symbolic Logic 12 1–11.CrossRefGoogle Scholar
Szawiel, S. and Zawadowski, M. (2014) Theories of analytic monads. Mathematical Structures in Computer Science (to appear).CrossRefGoogle Scholar