On the equivalence problem for regular Thue systems

Paliath Narendran

doi:10.1016/0304-3975(86)90121-0

On the equivalence problem for regular Thue systems

Paliath Narendran

Computer Science

University at Albany

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

2 Scopus citations

Abstract

A decision procedure is presented for the equivalence problem for regular almost-confluent Thue systems. On the other hand, the equivalence problem for regular preperfect systems is shown to be undecidable.

Original language	English
Pages (from-to)	237-245
Number of pages	9
Journal	Theoretical Computer Science
Volume	44
Issue number	C
DOIs	https://doi.org/10.1016/0304-3975(86)90121-0
State	Published - 1986

Access to Document

10.1016/0304-3975(86)90121-0

Cite this

@article{277e00725b6d4e6fb5a11ae19a6e8764,

title = "On the equivalence problem for regular Thue systems",

abstract = "A decision procedure is presented for the equivalence problem for regular almost-confluent Thue systems. On the other hand, the equivalence problem for regular preperfect systems is shown to be undecidable.",

author = "Paliath Narendran",

year = "1986",

doi = "10.1016/0304-3975(86)90121-0",

language = "English",

volume = "44",

pages = "237--245",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier B.V.",

number = "C",

}

TY - JOUR

T1 - On the equivalence problem for regular Thue systems

AU - Narendran, Paliath

PY - 1986

Y1 - 1986

N2 - A decision procedure is presented for the equivalence problem for regular almost-confluent Thue systems. On the other hand, the equivalence problem for regular preperfect systems is shown to be undecidable.

AB - A decision procedure is presented for the equivalence problem for regular almost-confluent Thue systems. On the other hand, the equivalence problem for regular preperfect systems is shown to be undecidable.

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

U2 - 10.1016/0304-3975(86)90121-0

DO - 10.1016/0304-3975(86)90121-0

M3 - Article

SN - 0304-3975

VL - 44

SP - 237

EP - 245

JO - Theoretical Computer Science

JF - Theoretical Computer Science

IS - C

ER -

On the equivalence problem for regular Thue systems

Abstract

Access to Document

Other files and links

Fingerprint

Cite this