Research Catalog

Title

String-rewriting systems / Ronald V. Book, Friedrich Otto.

Author

Book, Ronald V.

Publication

New York : Springer-Verlag, [1993]

Items in the Library & Off-site

Holdings

Details

Additional Authors

Otto, Friedrich.

Description

viii, 189 pages : illustrations; 24 cm.

Series Statement

Texts and monographs in computer science

Uniform Title

Texts and monographs in computer science.

Subject

• Rewriting systems (Computer science)

Bibliography (note)

• Includes bibliographical references (p. [175]-183) and index.

Contents

• 0. Introduction -- 1. Preliminaries. 1.1. Abstract Reduction Systems. 1.2. Reduction Modulo an Equivalence Relation. 1.3. Strings, Languages and Automata. 1.4. Some Turing Machine Constructions -- 2. String-Rewriting Systems. 2.1. Rewriting Systems for Strings. 2.2. Computing Normal Forms. 2.3. Testing for Local Confluence. 2.4. The Knuth-Bendix Completion Procedure. 2.5. Some Undecidable Properties -- 3. Length as the Basis for Reduction. 3.2. Testing for Confluence. 3.3. Confluence on a Single Class. 3.4. Equivalent Systems. 3.5. Church-Rosser Congruences. 3.6. Other Systems Based on Length -- 4. Monadic String-Rewriting Systems. 4.2. Specification of Formal Languages. 4.3. A Decision Procedure. 4.4. Applications of the Decision Procedure. 4.5. Limitations of the Decision Procedure -- 5. Length-Reducing Non-Monadic String-Rewriting Systems. 5.1. Presenting Recursively Enumerable Languages. 5.2. Some Undecidability Results. 5.3. Some Questions on Congruential Languages.
• 6. Algebraic Protocols. 6.2. Security and Cascade Protocols. 6.3. Security and Name-Stamp Protocols -- 7. Algebraic Properties. 7.1. Finite Monoid-Presentations. 7.2. Tietze Transformations. 7.3. Some Undecidability Results. 7.4. The Free Monoid Problem. 7.5. The Group Problem.

ISBN

0387979654

LCCN

92037370

OCLC

• 26850824
• ocm26850824

Owning Institutions

Columbia University Libraries