Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben

1993 | Buch

Introduction Kapitel lesen Erstes Kapitel lesen

String-Rewriting Systems

verfasst von: Ronald V. Book, Friedrich Otto

Verlag: Springer New York

Buchreihe : Monographs in Computer Science

Enthalten in: Professional Book Archive

Einloggen, um Zugang zu erhalten
insite
SUCHEN

Über dieses Buch

The subject of this book is string-rewriting systems. It is generally accepted that string-rewriting was first introduced by Axel Thue in the early part of this century. In the 1960's and early 1970's, it received renewed attention due to interest in formal language theory. In the 1980's and 1990's, it has received more interest since it can be viewed as a special case of term­ rewriting, a subject that has become important in the study of automated deduction. Today, string-rewriting is studied by researchers in theoretical computer science and also by researchers interested in the foundations of artificial intelligence. A sketch of the way that the subject has developed is contained in Chapter 0, and the reader is advised to begin with that chapter. Both authors have been active in the field and have lectured on the subject in several universities. Lecture notes have been produced and dis­ tributed. This monograph is a result of revising and rewriting those notes. It represents an attempt by the authors to present the concepts that the authors consider to be most fundamental and to gather together the most useful results in such a way that they can be understood and used in studies relating to more general rewriting, to automated deduction, and to algo­ rithmic problems of algebraic structures. This monograph is written for independent study by researchers in the­ oretical computer science or in the foundations of artificial intelligence.

Inhaltsverzeichnis

Frontmatter
0. Introduction
Abstract
In the early part of the twentieth century, Axel Thue [Thu14] discussed the following problem: Suppose one has a set of objects and a set of transformations (“rules”) that when applied to these objects yield objects in the same set. Given two objects x and y in the set, can x be transformed into y, or is there perhaps a third object z such that both x and y can be transformed into z?
Ronald V. Book, Friedrich Otto
1. Preliminaries
Abstract
In this chapter we present basic notions on which the entire monograph is based. In the first section we consider rewriting in the abstract sense, discussing the idea of a set of objects with a binary relation that illustrates the properties that rewriting relations should have. It is in this setting that notions such as “confluence” are introduced, and this chapter is essential for the remainder of the book. It should be the first section to be read carefully. Since the second section extends the first but is aimed at material that is not needed until 3.6, the reader is advised to wait until Section 3.6 is reached before addressing Section 1.2. In Section 1.3 we describe basic properties of strings, languages, and automata (with which we anticipate that the reader is familiar), and this section should be referred to only as needed. This chapter closes with a description of some basic Turing machine constructions, which again should be referred to only as needed.
Ronald V. Book, Friedrich Otto
2. String-Rewriting Systems
Abstract
In this chapter we introduce the string-rewriting systems and study their basic properties. Such systems are the primary subject of this work. We provide formal definitions of string-rewriting systems and their induced reduction relations and Thue congruences. Some of the basic ideas that occur in the study of term-rewriting systems are considered. We rely on Section 1.4 for basic definitions and notation for strings, and we rely on Section 1.1 for basic definitions and results on notions such as reduction, confluence, the Church-Rosser property, and so forth.
Ronald V. Book, Friedrich Otto
3. Length as the Basis for Reduction
Abstract
In this section we consider the notion of the length of a string to obtain an orientation for the rules of a string-rewriting system. It appears that this approach was introduced by work of Nivat.
Ronald V. Book, Friedrich Otto
4. Monadic String-Rewriting Systems
Abstract
Certain restrictions on the form of the rules of string-rewriting systems have yielded some extremely interesting results. Any finitely presented group can be presented by a finite special string-rewriting system (with no restriction to the notion of reduction). But special systems have a few undesirable limitations. Thus we turn to the study of “monadic” string-rewriting systems which extend the power of special string-rewriting systems in useful ways.
Ronald V. Book, Friedrich Otto
5. Length-Reducing Non-Monadic String-Rewriting Systems
Abstract
In the previous chapter we saw that there is a decision procedure to determine if a linear sentence is true for a monoid presented by a finite, monadic and confluent string-rewriting system. By using linear sentences many decision problems can be solved for these systems (see Section 4.4). Here we will show that in general for finite, length-reducing and confluent string-rewriting systems the truth of linear sentences in the monoids so prescribed is undecidable; in fact, many decision problems like the extended word problem, that can be expressed through linear sentences, are undecidable in this setting. All these undecidability results will be derived from a presentation of recursively enumerable languages through finite, length-reducing, and confluent string-rewriting systems.
Ronald V. Book, Friedrich Otto
6. Algebraic Protocols
Abstract
The topic of public key cryptosystems is important in the study of security of data in networks as well as cryptography. In this section we consider protocols for such systems, in particular we consider “algebraic” protocols whose syntax and semantics are given by finite string-rewriting systems that are monadic and confluent.
Ronald V. Book, Friedrich Otto
7. Algebraic Properties
Abstract
In this chapter we first review the notion in detail that string-rewriting systems can be seen as presentations of monoids. In particular, we will learn about the so-called Tietze transformations which are a means to change presentations without changing the monoid presented. Then we will address the following question: Given a finite string-rewriting system R on ∑, how much information on the algebraic structure of the monoid presented by (∑; R) can be obtained from R? We will establish a general undecidability result due to Markov and give some applications of it, before we finally derive some decidability results for presentations (∑; R), for which R satisfies certain additional restrictions, like being noetherian and confluent.
Ronald V. Book, Friedrich Otto
Backmatter
Metadaten
Titel
String-Rewriting Systems
verfasst von
Ronald V. Book
Friedrich Otto
Copyright-Jahr
1993
Verlag
Springer New York
Electronic ISBN
978-1-4613-9771-7
Print ISBN
978-1-4613-9773-1
DOI
https://doi.org/10.1007/978-1-4613-9771-7