This monograph treats comprehensively central aspects of string
rewriting systems in the form of semi-Thue systems. These are so
general as to enable the discussion of all the basic notions and
questions that arise in arbitrary replacement systems as used in
various areas of computer science. The Church-Rosser property is
used in its original meaning and the existence of complete monoid
and group presentations is the central point of discussion.
Decidability problems with their complexity are surveyed and
congruential languages including the deterministic context-free NTS
languages are discussed. The book contains a number of
generalizations of results published elsewhere, e.g., the
uniqueness of complete string rewriting systems with respect to the
underlying order. Completely new and unpublished results which
serve as an exposition of techniques and new methods are discussed
in detail. With the help of semi-Thue systems it is shown in which
situations the famous Knuth-Bendix completion method does not
terminate and why, and that in general complete replacement systems
cannot always be used as algorithms to solve the word problem. It
is suggested how these situations can be stated by using a certain
control under which the rewriting is to be performed. This
monograph is a reference for graduate students and active
researchers in theoretical computer science. The reader is led to
the forefront of current research in the area of string rewriting
and monoid presentations.
General
Is the information for this product incomplete, wrong or inappropriate?
Let us know about it.
Does this product have an incorrect or missing image?
Send us a new image.
Is this product missing categories?
Add more categories.
Review This Product
No reviews yet - be the first to create one!
Welcome to Loot.co.za!
Sign in / Register |Wishlists & Gift Vouchers |Help | Advanced search
