Automata, Languages and Programming

The Second Colloquium on Automata, Languages and Programming is the successor of a similar Colloquium organized by IRIA in Paris, July 3-7, 1972. The present Colloquium which takes place at the Unl-­ versity of Saarbrucken from July 29th to August 2nd, 1974, is spon­ sored by the Gesellschaft fur. Informatik and organized in cooperation wlth the Special Interest Group on Automata and Computability Theory (SIGACT) and with the European Association for Theoretical Computer Science (EATCS). As its predecessor the present Colloquium is devoted to the theo­ retical bases of computer science. This volume contains the text of the different lectures of the Colloquium whlch have been selected by the Program Committee out of about 130 submitted papers. About one third of the papers of this volume is concerned with formal language theory, one other third with the theory of computation and the rest with complexity theory, automata theory, programming languages, etc.