Skip to main content
main-content

Über dieses Buch

The need for a comprehensive survey-type exposition on formal languages and related mainstream areas of computer science has been evident for some years. In the early 1970s, when . the book Formal Languages by the second­ mentioned editor appeared, it was still quite feasible to write a comprehensive book with that title and include also topics of current research interest. This would not be possible anymore. A standard-sized book on formal languages would either have to stay on a fairly low level or else be specialized and restricted to some narrow sector of the field. The setup becomes drastically different in a collection of contributions, where the best authorities in the world join forces, each of them concentrat­ ing on their own areas of specialization. The present three-volume Handbook constitutes such a unique collection. In these three volumes we present the current state of the art in formal language theory. We were most satisfied with the enthusiastic response given to our request for contributions by specialists representing various subfields. The need for a Handbook of Formal Languages was in many answers expressed in different ways: as an easily accessible his­ torical reference, a general source of information, an overall course-aid, and a compact collection of material for self-study. We are convinced that the final result will satisfy such various needs. The theory of formal languages constitutes the stem or backbone of the field of science now generally known as theoretical computer science.

Inhaltsverzeichnis

Frontmatter

Tree Languages

Abstract
The theory of tree automata and tree languages emerged in the middle of the 1960s quite naturally from the view of finite automata as unary algebras advocated by J. R. Büchi and J. B. Wright. From this perspective the generalization from strings to trees means simply that any finite algebra of finite type can be regarded as an automaton which as inputs accepts terms over the ranked alphabet formed by the operation symbols of the algebra, and these terms again can be seen as (formal representations of) labeled trees with a left-to-right ordering of the branches. Strings over a finite alphabet can then be regarded as terms over a unary ranked alphabet, and hence finite automata become special tree automata and string languages unary tree languages. The theory of tree automata and tree languages can thus be seen as an outgrowth of Büchi’s and Wright’s program which had as its goal a general theory that would encompass automata, universal algebra, equational logic, and formal languages. Some interesting vistas of this program and its development are opened by Büchi’s posthumous book [Büc89] in which many of the ideas are traced back to people like Thue, Skolem, Post, and even Leibniz.
Ferenc Gécseg, Magnus Steinby

Tree-Adjoining Grammars

Abstract
In this paper, we will describe a tree generating system called tree-adjoining grammar (TAG) and state some of the recent results about TAGs. The work on TAGs is motivated by linguistic considerations. However, a number of formal results have been established for TAGs, which we believe, would be of interest to researchers in formal languages and automata, including those interested in tree grammars and tree automata.
Aravind K. Joshi, Yves Schabes

Context-Free Graph Grammars

Summary
Graph languages are sets of labeled graphs. They can be generated by graph grammars, and in particular by context-free graph grammars. There are several types of context-free graph grammars, depending, e.g., on whether (hyper)edges or nodes are rewritten by graphs. Basic properties of the main types of context-free graph grammars are discussed. Other, equivalent, ways of defining context-free graph languages are: generating graph expressions by regular tree grammars, and translating trees into graphs by formulas of monadic second-order logic. Context-free graph grammars can be used to generate string languages and tree languages.
Joost Engelfriet

Two-Dimensional Languages

Abstract
The aim of this chapter is to generalize concepts and techniques of formal language theory to two dimensions. Informally, a two-dimensional string is called a picture and is defined as a rectangular array of symbols taken from a finite alphabet. A two-dimensional language (or picture language) is a set of pictures.
Dora Giammarresi, Antonio Restivo

Basics of Term Rewriting

Abstract
Terms and trees are important structured objects that can be found almost everywhere in Computer Science, not only in connection with their mathematical foundations. In any axiomatic definition of structures and equationally defined calculi one will find the combination of axioms, i.e., equations, and a method of deriving new theorems from those by using deduction rules. This situation traditionally can be found in logic and became important in applications such as symbolic algebraic computation, program specification and verification using abstract data types, and automated theorem proving. Term rewriting can be seen as a generalization of string rewriting as studied early in this century by Axel Thue. Terms are structured strings that can well be visualized by rooted, node-labelled, and ordered trees. This was already recognized by Axel Thue in 1910, [Thue10]. In his paper he investigated the formulation of new concepts from already given ones and designed a theory of terms or trees and how to create and use them. He posed what we now call the word problem for equational theories and thereby introduced the idea of a universal algebra and the free algebra over sets of equations. The theorems deduced syntactically from a set of axioms within a calculus are useful only in the context of a semantic interpretation in an algebraic structure that models the theory specified by the axioms and the deduction rules. The semantic equality means that a theorem a = b is true in each model of a given theory whereas syntactic equality a = E b is its deducibility (provability) from the axioms E. From Birkhoff 1935, [Birk35], we know that semantic and syntactic equality coincides and thus the deduction rules specified in the calculus could in general be used for deciding semantic equality.
Matthias Jantzen

ω-Languages

Abstract
The purpose of this chapter is to give an introduction into languages of infinite strings (of order type ω), so-called ω-languages. The set of all infinite strings over a finite alphabet may be considered, as we shall see below, in a natural way as a metric space.
Ludwig Staiger

Languages, Automata, and Logic

Abstract
The subject of this chapter is the study of formal languages (mostly languages recognizable by finite automata) in the framework of mathematical logic.
Wolfgang Thomas

Partial Commutation and Traces

Abstract
Parallelism and concurrency are fundamental concepts in computer science. Specification and verification of concurrent programs are of first importance. It concerns our daily life whether software written for distributed systems behaves correctly.
Volker Diekert, Yves Métivier

Visual Models of Plant Development

Summary
In these notes we survey applications of L-systems to the modeling of plants, with an emphasis on the results obtained since the comprehensive presentation of this area in The Algorithmic Beauty of Plants [99]. The new developments include:
  • extensions to the L-system formalism that increase its expressive power as needed for practical biological applications
  • introduction of programming constructs that enhance the use of L-systems as a language for describing developmental algorithms and as input for simulation programs, and
  • new biological applications of L-systems.
Przemyslaw Prusinkiewicz, Mark Hammel, Jim Hanan, Radomír Měch

Digital Images and Formal Languages

Summary
We discuss the application of (weighted) finite automata to image specification and image-data compression and applications of (weighted) finite transducers to image manipulation.
Karel Culik, Jarkko Kari

Backmatter

Weitere Informationen