Cancellativity is undecidable for automatic semigroups

Alan J. Cain

doi:10.1093/qmath/hai023

Cancellativity is undecidable for automatic semigroups

Alan J. Cain

School of Mathematics and Statistics

Research output: Contribution to journal › Article › peer-review

Abstract

Via an encoding of the Modified Post's Correspondence Problem, this paper shows that it is undecidable whether an automatic semigroup is cancellative.

Original language	English
Pages (from-to)	285-295
Number of pages	11
Journal	Quarterly Journal of Mathematics
Volume	57
DOIs	https://doi.org/10.1093/qmath/hai023
Publication status	Published - Sept 2006

Access to Document

10.1093/qmath/hai023

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications
Linton, S. A. (PI), Gent, I. P. (CoI), Leonhardt, U. (CoI), Mackenzie, A. (CoI), Miguel, I. J. (CoI), Quick, M. (CoI) & Ruskuc, N. (CoI)
EPSRC
1/09/05 → 31/08/10
Project: Standard

Cite this

@article{757af903019548538101986d5a13e916,

title = "Cancellativity is undecidable for automatic semigroups",

abstract = "Via an encoding of the Modified Post's Correspondence Problem, this paper shows that it is undecidable whether an automatic semigroup is cancellative.",

author = "Cain, {Alan J.}",

year = "2006",

month = sep,

doi = "10.1093/qmath/hai023",

language = "English",

volume = "57",

pages = "285--295",

journal = "Quarterly Journal of Mathematics",

issn = "0033-5606",

publisher = "Oxford University Press",

}

TY - JOUR

T1 - Cancellativity is undecidable for automatic semigroups

AU - Cain, Alan J.

PY - 2006/9

Y1 - 2006/9

N2 - Via an encoding of the Modified Post's Correspondence Problem, this paper shows that it is undecidable whether an automatic semigroup is cancellative.

AB - Via an encoding of the Modified Post's Correspondence Problem, this paper shows that it is undecidable whether an automatic semigroup is cancellative.

U2 - 10.1093/qmath/hai023

DO - 10.1093/qmath/hai023

M3 - Article

SN - 0033-5606

VL - 57

SP - 285

EP - 295

JO - Quarterly Journal of Mathematics

JF - Quarterly Journal of Mathematics

ER -

Cancellativity is undecidable for automatic semigroups

Abstract

Access to Document

Fingerprint

Projects

EP/C523229/1: Multidisciplinary Critical Mass in Computational Algebra and Applications

Cite this