Thread View: capdist.seminars
1 messages
1 total messages
Started by Pat Keller
Wed, 11 Aug 1999 00:00
SUNYA C. S. Dept. Colloquium
Author: Pat Keller
Date: Wed, 11 Aug 1999 00:00
Date: Wed, 11 Aug 1999 00:00
37 lines
2303 bytes
2303 bytes
COLLOQUIUM
University at Albany - State University of New York
Computer Science Department
Algorithms and Reductions for Some Basic Problems in Term Rewriting
Rakesh M. Verma
Dept of Computer Science
University of Houston
Houston, TX
Thursday, August 12, 1999 at 11:00AM, in LI-98 (CS Conference Room)
ABSTRACT
In this talk we will present polynomial-time reductions
between some basic decision problems of rewrite systems,
e.g., the word problem, uniqueness of normal forms, reacha-
bility, confluence, etc. We will present a polynomial-time
algorithm for the unique-normal-form property for ground
systems. We will show that all of these problems are unde-
cidable for a {\m fixed} string rewriting system using our
reductions. Finally, we prove the decidability of confluence
for commutative semi-thue systems. The Confluence and
Unique-normal form property will be shown to be Expspace-
hard for commutative semi-thue systems. We also show that
there is a family of string rewrite systems for which the
word problem is trivially decidable but confluence undecid-
able, and we show a linear equational theory with decidable
word problem but undecidable linear equational matching.
This is joint work with M. Rusinowitch and D. Lugiez.
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads