An O(|T|3) algorithm for testing the Church-Rosser property of thue systems

D. Kapur; M. S. Krishnamoorthy; R. McNaughton; P. Narendran

doi:10.1016/0304-3975(85)90008-8

An O(|T|³) algorithm for testing the Church-Rosser property of thue systems

D. Kapur
, M. S. Krishnamoorthy
, R. McNaughton
, P. Narendran

Computer Science

University at Albany

G.E. Research and Development Center
Rensselaer Polytechnic Institute

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

19 Scopus citations

Abstract

We give an O(|T|³) algorithm for testing the Church-Rosser property of Thue systems using the linear string-matching algorithm by Knuth, Morris and Pratt (1977). This improves the earlier bound of O(|T|⁶) given by Book and O'Dunlaing (1981). The proposed algorithm uses a reduction algorithm for finding a normal form of a string which is based on building a trie for matching a finite set of patterns, as proposed by Aho and Corasick (1975).

Original language	English
Pages (from-to)	109-114
Number of pages	6
Journal	Theoretical Computer Science
Volume	35
Issue number	C
DOIs	https://doi.org/10.1016/0304-3975(85)90008-8
State	Published - 1985

Access to Document

10.1016/0304-3975(85)90008-8

Cite this

@article{bb29c562f95d467e9ded382e8ed99a5f,

title = "An O(|T|3) algorithm for testing the Church-Rosser property of thue systems",

abstract = "We give an O(|T|3) algorithm for testing the Church-Rosser property of Thue systems using the linear string-matching algorithm by Knuth, Morris and Pratt (1977). This improves the earlier bound of O(|T|6) given by Book and O'Dunlaing (1981). The proposed algorithm uses a reduction algorithm for finding a normal form of a string which is based on building a trie for matching a finite set of patterns, as proposed by Aho and Corasick (1975).",

author = "D. Kapur and Krishnamoorthy, \{M. S.\} and R. McNaughton and P. Narendran",

year = "1985",

doi = "10.1016/0304-3975(85)90008-8",

language = "English",

volume = "35",

pages = "109--114",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - An O(|T|3) algorithm for testing the Church-Rosser property of thue systems

AU - Kapur, D.

AU - Krishnamoorthy, M. S.

AU - McNaughton, R.

AU - Narendran, P.

PY - 1985

Y1 - 1985

N2 - We give an O(|T|3) algorithm for testing the Church-Rosser property of Thue systems using the linear string-matching algorithm by Knuth, Morris and Pratt (1977). This improves the earlier bound of O(|T|6) given by Book and O'Dunlaing (1981). The proposed algorithm uses a reduction algorithm for finding a normal form of a string which is based on building a trie for matching a finite set of patterns, as proposed by Aho and Corasick (1975).

AB - We give an O(|T|3) algorithm for testing the Church-Rosser property of Thue systems using the linear string-matching algorithm by Knuth, Morris and Pratt (1977). This improves the earlier bound of O(|T|6) given by Book and O'Dunlaing (1981). The proposed algorithm uses a reduction algorithm for finding a normal form of a string which is based on building a trie for matching a finite set of patterns, as proposed by Aho and Corasick (1975).

UR - https://www.scopus.com/pages/publications/0013450815

U2 - 10.1016/0304-3975(85)90008-8

DO - 10.1016/0304-3975(85)90008-8

M3 - Article

SN - 0304-3975

VL - 35

SP - 109

EP - 114

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

An O(|T|³) algorithm for testing the Church-Rosser property of thue systems

Abstract

Access to Document

Other files and links

Fingerprint

Cite this