article

Free access

Confluent and Other Types of Thue Systems

Author:

Ronald V. BookAuthors Info & Claims

Journal of the ACM (JACM), Volume 29, Issue 1

Pages 171 - 182

https://doi.org/10.1145/322290.322301

Published: 01 January 1982 Publication History

PDF eReader

References

[1]

ADJAN, S Defining relations and algorithmic problems for groups and semlgroups Proc Stektov lnst Math 85, 1966 {Enlish version published by American Mathematical Society, 1967}

Google Scholar

[2]

AHO, A, SETHI, R, AND ULLMAN, J Code opum~zatmn and fimte Church-Rosser systems In Design and Opnmtzatton of Compders, R Rustm, Ed, Prentice Hall, 1972, pp 89-105

Google Scholar

[3]

BERSTEL, J Congruences plus que parfaites et languages algdbnque Semmair d'Informattque Thdonque, lnstltut de Programmatmn, 1976-77, pp 123-147

Google Scholar

[4]

BooK, R, JANTZEN, M, MONIEN, B, AND WRATHHELL. C Results on Thue systems and sem~groups Research announcement, Omv of Californta, Santa Barbara, Cahf, May 1980

Google Scholar

[5]

BOOK, R, JANTZEN, M, AND WRAIHALL, C Monadlc Thue systems To appear m Theor Comput SCI

Google Scholar

[6]

BooK, R, AND KWAN, C On umquely deopherable codes with two codewords IEEE Trans Comput 29 (1980), 324--325

Google Scholar

[7]

BOOK, R, AND O'DUNLAING, C Testing for the Church-Rosser property Theor Comput Sa 16 (1981), 223-229

Google Scholar

[8]

BOOK, R., AND 0'DUNLAING, C. Thue congruences and the Church-Rosser property Semtgroup Forum 22 (1981), 36%379

Google Scholar

[9]

CHURCH, A, AND ROSSER, B Some properties of conversion Tram Am Math Soc 39 (1939), 472--482

Google Scholar

[10]

COCHET, Y Sur l'algdbnotd des classes de certalnes congruences d6fimes sur le monotde hbre Thbse 3'~ cycle, Rennes, 1971

Google Scholar

[11]

COCHET, Y, AND NIVAT, M Une generalization des ensembles de Dyck lsrael J. Math. 9 (1971), 389-395

Google Scholar

[12]

HUET, G Confluent reductions Abstract properties and apphcatlons to term rewriting systems J ACM 27, 4 (Oct 1980), 797-821

Crossref

Google Scholar

[13]

JANTZEN, M. On a special monold with a single defining relauon, Theor. Comput Sct 16 (1981), 61-73

Google Scholar

[14]

LYNDON, R, AND SCHUTZENBERGER, M The equation aM - b Ncv m a free group Mtehtgan Math. J9 (1962), 289-298

Google Scholar

[15]

NEWMAN, M H A On theories with a combinatorial definition of "equtvalence." Ann Math. 43 (1943), 223-243

Google Scholar

[16]

NIVAT, M On some famdles of languages related to the Dyck languages. 2nd A CM Symp on Theory of Computing, Northampton, Mass, 1970, pp 221-225

Crossref

Google Scholar

[17]

NIVAT, M (WITh BENOtS, M )Congruences parfattes et quast-parfaltes. Semmaire Dubred, 25~ Annee, 1971-72, 7-01-09

Google Scholar

[18]

ROSEN, B K Tree-manipulatmg systems and Church-Rosser theorems J ACM 20, 1 (Jan 1973), 160-187

Crossref

Google Scholar

[19]

SAKAROVITCH, J Syntaxe des languages de ChomskymEssat sur le d6termisme Th~se de Doctoral d Etat, Umverslt6 Pans VII, 1979

Google Scholar

Cited By

View all

Nyberg-Brodda C(2023)On the word problem for free products of semigroups and monoidsJournal of Algebra10.1016/j.jalgebra.2023.02.007622(721-741)Online publication date: May-2023
https://doi.org/10.1016/j.jalgebra.2023.02.007
Nyberg-Brodda C(2022)On the word problem for special monoidsSemigroup Forum10.1007/s00233-022-10286-2105:1(295-327)Online publication date: 31-May-2022
https://doi.org/10.1007/s00233-022-10286-2
Eisenberg APiggott A(2019)Gilman's conjectureJournal of Algebra10.1016/j.jalgebra.2018.09.022517(167-185)Online publication date: Jan-2019
https://doi.org/10.1016/j.jalgebra.2018.09.022
Show More Cited By

Recommendations

Confluent term rewriting systems
RTA'05: Proceedings of the 16th international conference on Term Rewriting and Applications

The confluence property is one of the most important properties of term rewriting systems, and various sufficient criteria for proving this property have been widely investigated. A necessary and sufficient criterion for confluence of terminating term ...
On some generalizations of the Thue--Morse morphism

In 1912, the Norwegian mathematician Axel Thue was the first to describe an overlap-free binary infinite word. This word was generated by a morphism which is called, since the works of Morse, the Thue-Morse morphism. Here, we present two generalizations ...
The Knuth-Bendix Completion Procedure and Thue Systems

The Knuth-Bendix completion procedure for term rewriting systems in many cases provides a decision procedure for equational theories and has been found to have many applications in various areas. We discuss the application of the Knuth-Bendix procedure ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Journal of the ACM Volume 29, Issue 1

Jan. 1982

268 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/322290

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 1982

Published in JACM Volume 29, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

173
Total Citations
View Citations
614
Total Downloads

Downloads (Last 12 months)62
Downloads (Last 6 weeks)8

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Nyberg-Brodda C(2023)On the word problem for free products of semigroups and monoidsJournal of Algebra10.1016/j.jalgebra.2023.02.007622(721-741)Online publication date: May-2023
https://doi.org/10.1016/j.jalgebra.2023.02.007
Nyberg-Brodda C(2022)On the word problem for special monoidsSemigroup Forum10.1007/s00233-022-10286-2105:1(295-327)Online publication date: 31-May-2022
https://doi.org/10.1007/s00233-022-10286-2
Eisenberg APiggott A(2019)Gilman's conjectureJournal of Algebra10.1016/j.jalgebra.2018.09.022517(167-185)Online publication date: Jan-2019
https://doi.org/10.1016/j.jalgebra.2018.09.022
Book R(2018)Dehn's Algorithm and the Complexity of Word ProblemsThe American Mathematical Monthly10.1080/00029890.1988.1197211795:10(919-925)Online publication date: 2-Feb-2018
https://doi.org/10.1080/00029890.1988.11972117
Arajo JKinyon MKonieczny JMalheiro A(2018)Decidability and independence of conjugacy problems in finitely presented monoidsTheoretical Computer Science10.1016/j.tcs.2018.04.002731:C(88-98)Online publication date: 30-Jun-2018
https://dl.acm.org/doi/10.1016/j.tcs.2018.04.002
Riché TGonçalves RMarker BBatory D(2012)Pushouts in software architecture designACM SIGPLAN Notices10.1145/2480361.237141548:3(84-92)Online publication date: 26-Sep-2012
https://dl.acm.org/doi/10.1145/2480361.2371415
Riché TGonçalves RMarker BBatory DOstermann KBinder W(2012)Pushouts in software architecture designProceedings of the 11th International Conference on Generative Programming and Component Engineering10.1145/2371401.2371415(84-92)Online publication date: 26-Sep-2012
https://dl.acm.org/doi/10.1145/2371401.2371415
Madlener KOtto F(2011)Commutativity in groups presented by finite Church-Rosser Thue systemsRAIRO - Theoretical Informatics and Applications10.1051/ita/198822010093122:1(93-111)Online publication date: 8-Jan-2011
https://doi.org/10.1051/ita/1988220100931
ÓDúnlaing CSchluter N(2010)A shorter proof that palindromes are not a Church-Rosser language, with extensions to almost-confluent and preperfect Thue systemsTheoretical Computer Science10.1016/j.tcs.2009.10.003411:3(677-690)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1016/j.tcs.2009.10.003
Levy-Dit-Vehel FPerret L(2010)Security analysis of word problem-based cryptosystemsDesigns, Codes and Cryptography10.1007/s10623-009-9307-x54:1(29-41)Online publication date: 1-Jan-2010
https://dl.acm.org/doi/10.1007/s10623-009-9307-x
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Confluent term rewriting systems

On some generalizations of the Thue--Morse morphism

The Knuth-Bendix Completion Procedure and Thue Systems