Hostname: page-component-cd9895bd7-lnqnp Total loading time: 0 Render date: 2024-12-22T20:25:52.325Z Has data issue: false hasContentIssue false
  • English
  • Français

The word problem for semigroups with two generators

Published online by Cambridge University Press:  12 March 2014

Marshall Hall Jr.
Marshall Hall Jr.*
Affiliation:
The Ohio State University
Get access Rights & Permissions [Opens in a new window]

Extract

Emil Post has shown that the word problem for Thue systems is unsolvable. A Thue system is a system of strings of letters x1, x2, …, xr, where a string or word is either void or a succession of letters a1a2 … at with each ai some xi. We are given a finite number of pairs of strings Ai, Bii = 1, …, m. Operations in the Thue system consist of the replacements or “productions.”

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 14 , Issue 2 , 23 June 1949 , pp. 115 - 118
Copyright
Copyright © Association for Symbolic Logic 1949

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Presented to the American Mathematical Society, December 29, 1948.

1 Emil, Post, Recursive unsolvability of a problem of Thue, this Journal, vol. 12 (1947), pp. 1–11.Google Scholar