The uniform conjugacy problem for finite church-Rosser thue systems is NP-complete

Paliath Narendran; Friedrich Otto; Karl Winklmann

doi:10.1016/S0019-9958(84)80041-8

The uniform conjugacy problem for finite church-Rosser thue systems is NP-complete

Paliath Narendran
, Friedrich Otto
, Karl Winklmann

Computer Science

University at Albany

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

6 Scopus citations

Abstract

The uniform conjugacy problem for finite Church-Rosser Thue systems over alphabet σ is NP-complete, if σ contains at least two letters. If σ contains a single letter only, then this problem is tractable.

Original language	English
Pages (from-to)	58-66
Number of pages	9
Journal	Information and control
Volume	63
Issue number	1-2
DOIs	https://doi.org/10.1016/S0019-9958(84)80041-8
State	Published - 1984

Access to Document

10.1016/S0019-9958(84)80041-8

Cite this

@article{aa17b03d6cd24d2ca22a37ee5bd13397,

title = "The uniform conjugacy problem for finite church-Rosser thue systems is NP-complete",

abstract = "The uniform conjugacy problem for finite Church-Rosser Thue systems over alphabet σ is NP-complete, if σ contains at least two letters. If σ contains a single letter only, then this problem is tractable.",

author = "Paliath Narendran and Friedrich Otto and Karl Winklmann",

year = "1984",

doi = "10.1016/S0019-9958(84)80041-8",

language = "English",

volume = "63",

pages = "58--66",

journal = "Information and control",

issn = "0019-9958",

publisher = "Elsevier Inc.",

number = "1-2",

}

TY - JOUR

T1 - The uniform conjugacy problem for finite church-Rosser thue systems is NP-complete

AU - Narendran, Paliath

AU - Otto, Friedrich

AU - Winklmann, Karl

PY - 1984

Y1 - 1984

N2 - The uniform conjugacy problem for finite Church-Rosser Thue systems over alphabet σ is NP-complete, if σ contains at least two letters. If σ contains a single letter only, then this problem is tractable.

AB - The uniform conjugacy problem for finite Church-Rosser Thue systems over alphabet σ is NP-complete, if σ contains at least two letters. If σ contains a single letter only, then this problem is tractable.

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

U2 - 10.1016/S0019-9958(84)80041-8

DO - 10.1016/S0019-9958(84)80041-8

M3 - Article

SN - 0019-9958

VL - 63

SP - 58

EP - 66

JO - Information and control

JF - Information and control

IS - 1-2

ER -

The uniform conjugacy problem for finite church-Rosser thue systems is NP-complete

Abstract

Access to Document

Other files and links

Fingerprint

Cite this