|
Showing 1 - 5 of
5 matches in All Departments
Replacement systems, such as term rewriting systems, tree manipulat
ing systems, and graph grammars, have been used in Computer Science
in the context of theorem proving, program optimization, abstract
data types, algebraic simplification, and symbolic comput ation.
Replacement systems for strings arose about seventy years earlier
in the area of combinatory logic and group theory. The most natural
and appropriate formalism for dealing with string rewriting is the
notion of a semi-Thue system and this monograph treats its central
aspects. The reduction relation is here defined firstly by the
direction of the rules and secondly by some metric that yields
efficient algorithms. These systems are general enough to discuss
the basic notions of arbitrary replacement systems, such as
termination, confluence, and the Church-Rosser property in its
original meaning. Confluent semi-Thue systems in which each and
every derivation consists of finitely many steps only are called
complete; they guarantee the existence of unique normal forms as
canonical representatives of the Thue congruence classes. Each such
system can be considered a nondeterministic algorithm for the word
problem which works correctly without backtracking. This is often
conceptually simpler and more elegant than an ad hoc construction.
In many cases a replace ment system can be altered to a complete
system by the Knuth-Bendix completion method."
This book constitutes an anthology of refereed papers arranged to
acknowledge the work of Wilfried Brauer on the occasion of his
sixtieth birthday. The volume presents 49 revised refereed papers
organized in topical sections on computer science and its
potential, social implications of computer science, formal
languages and automata, structures and complexity theory, Petri
nets, systems analysis and distributed systems, software
engineering and verification, cognition and artificial
intelligence, knowledge representation and reasoning, machine
learning, neural networks and robotics, language and information
systems.
This volume gives the proceedings of the ninth Symposium on
Theoretical Aspects of Computer Science (STACS). This annual
symposium is held alternately in France and Germany and is
organized jointly by the Special Interest Group for Fundamental
Computer Science of the Association Francaise des Sciences et
Technologies de l'Information et des Syst mes (AFCET) and the
Special Interest Group for Theoretical Computer Science of the
Gesellschaft f}r Informatik (GI). The volume includes three invited
lectures and sections on parallel algorithms, logic and semantics,
computational geometry, automata and languages, structural
complexity, computational geometry and learning theory, complexity
and communication, distributed systems, complexity, algorithms,
cryptography, VLSI, words and rewriting, and systems.
This volume contains the proceedings of STACS 91, a symposium on
the theoretical aspects of computer science, held in Hamburg,
Germany in February 1991. STACS is held each year, alternately in
Germany and France, and is organized jointly by the Special
Interest Group for Theoretical Computer Science of the Gesellschaft
fuer Informatik (GI) and the Special Interest Group for Applied
Mathematics of the Association Francaise des Sciences et Techniques
de l'Information et de Systemes (AFCET). The topics covered in this
volume include abstract data types, algorithms and data structures,
automata and formal languages, complexity of concrete algorithms,
computational geometry, cryptography, computer systems theory,
logic and semantics, mathematics of computation, program
specification, theory of parallel and distributed computation,
structural complexity, theory of robotics, VLSI structures, and the
theory of databases.
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.
|
You may like...
The Creator
John David Washington, Gemma Chan, …
DVD
R325
Discovery Miles 3 250
|