Ebook: Automata Theory and Formal Languages 2nd GI Conference Kaiserslautern, May 20–23, 1975

---

Content:
Front Matter....Pages -
Formal language theory and theoretical computer science....Pages 1-15
Le cylindre des langages lineaires n'est pas principal....Pages 16-19
Langages algebriques deterministes et groupes abeliens....Pages 20-30
Best possible bounds on the weighted path length of optimum binary search trees....Pages 31-41
En?En?1-entscheidbare Gruppen....Pages 42-51
Statistical characterization of learnable sequences....Pages 52-56
?ber den mittleren Zeitbedarf bei der LR(k) — Analyse kontextfreier Sprachen....Pages 57-63
Zur endlichen Approximierbarkeit sequentieller Systeme....Pages 64-70
The complexity of negation-limited networks — A brief survey....Pages 71-82
The network-complexity of equivalence and other applications of the network complexity....Pages 83-92
Test d'isomorphie d'hypergraphes planaires....Pages 93-98
Obere und untere Schranke f?r die Komplexit?t von Booleschen Funktionen....Pages 99-102
On the entropy of a formal language....Pages 103-109
On the complexity of computations under varying sets of primitives....Pages 110-117
About the deterministic simulation of nondeterministic (log n)-tape bounded turing machines....Pages 118-126
Zur Entscheidbarkeit der funktionalen ?quivalenz....Pages 127-133
Quantifier elimination for real closed fields by cylindrical algebraic decompostion....Pages 134-183
Deterministische indizierte Grammatiken....Pages 184-189
Eine Beschreibung contextfreier Sprachen durch endliche Mengensysteme....Pages 190-197
On the generative capacity of the strict global grammars....Pages 198-201
Tree-transducers and syntax-connected transductions....Pages 202-208
Sur les relations rationnelles....Pages 209-213
Piecewise testable events....Pages 214-222
Die Gr?sse des zustandsminimalen LR(O)-Analysators....Pages 223-232
Formal translations and the containment problem for Szilard languages....Pages 233-238
A characterization of bounded regular sets....Pages 239-244
Eine universelle Lambda-Kalk?l-Programmiersprache und ihr Interpreter....Pages 245-251
Potenzkategorien und ihre Anwendung auf den Beweis von Programmeigenschaften....Pages 252-258
Welcher Art Ergebnisse erwartet der Compilerbau von der Theoretischen Informatik?....Pages 259-273
Pr?dikatives Programmieren....Pages 274-283
Analyzing families of grammars....Pages 284-288
Control structures and monadic languages....Pages 289-292

---

Content:
Front Matter....Pages -
Formal language theory and theoretical computer science....Pages 1-15
Le cylindre des langages lineaires n'est pas principal....Pages 16-19
Langages algebriques deterministes et groupes abeliens....Pages 20-30
Best possible bounds on the weighted path length of optimum binary search trees....Pages 31-41
En?En?1-entscheidbare Gruppen....Pages 42-51
Statistical characterization of learnable sequences....Pages 52-56
?ber den mittleren Zeitbedarf bei der LR(k) — Analyse kontextfreier Sprachen....Pages 57-63
Zur endlichen Approximierbarkeit sequentieller Systeme....Pages 64-70
The complexity of negation-limited networks — A brief survey....Pages 71-82
The network-complexity of equivalence and other applications of the network complexity....Pages 83-92
Test d'isomorphie d'hypergraphes planaires....Pages 93-98
Obere und untere Schranke f?r die Komplexit?t von Booleschen Funktionen....Pages 99-102
On the entropy of a formal language....Pages 103-109
On the complexity of computations under varying sets of primitives....Pages 110-117
About the deterministic simulation of nondeterministic (log n)-tape bounded turing machines....Pages 118-126
Zur Entscheidbarkeit der funktionalen ?quivalenz....Pages 127-133
Quantifier elimination for real closed fields by cylindrical algebraic decompostion....Pages 134-183
Deterministische indizierte Grammatiken....Pages 184-189
Eine Beschreibung contextfreier Sprachen durch endliche Mengensysteme....Pages 190-197
On the generative capacity of the strict global grammars....Pages 198-201
Tree-transducers and syntax-connected transductions....Pages 202-208
Sur les relations rationnelles....Pages 209-213
Piecewise testable events....Pages 214-222
Die Gr?sse des zustandsminimalen LR(O)-Analysators....Pages 223-232
Formal translations and the containment problem for Szilard languages....Pages 233-238
A characterization of bounded regular sets....Pages 239-244
Eine universelle Lambda-Kalk?l-Programmiersprache und ihr Interpreter....Pages 245-251
Potenzkategorien und ihre Anwendung auf den Beweis von Programmeigenschaften....Pages 252-258
Welcher Art Ergebnisse erwartet der Compilerbau von der Theoretischen Informatik?....Pages 259-273
Pr?dikatives Programmieren....Pages 274-283
Analyzing families of grammars....Pages 284-288
Control structures and monadic languages....Pages 289-292
....