Theoretical Computer Science 4th GI Conference: Aachen, March 26–28, 1979 [1 ed.] 3540091181, 9783540091189 [DJVU]

Table of contents :
Context-free sets of infinite words....Pages 1-9
New aspects of homomorphisms....Pages 10-24
Can partial correctness assertions specify programming language semantics?....Pages 25-26
An algebraic theory for synchronization....Pages 27-35
Storage modification machines....Pages 36-37
Negative results on counting....Pages 38-46
Strong non-deterministic context-free languages....Pages 47-57
Information content characterizations of complexity theoretic properties....Pages 58-66
Mittlere Anzahl von Rebalancierungsoperationen in gewichtsbalancierten Bäumen....Pages 67-78
A new recursion induction principle....Pages 79-90
Finite-change automata....Pages 91-100
Move rules and trade-offs in the pebble game....Pages 101-112
Transition diagrams and strict deterministic grammars....Pages 113-123
Exact expressions for some randomness tests....Pages 124-131
On storage optimization for automatically generated compilers....Pages 132-141
On continuous completions....Pages 142-152
A new method to show lower bounds for polynomials which are hard to compute....Pages 153-157
On zerotesting-bounded multicounter machines....Pages 158-169
When are two effectively given domains identical?....Pages 170-181
Sur deux langages linéaires....Pages 182-189
An efficient on-line position tree construction algorithm....Pages 190-198
Sorting presorted files....Pages 199-212
Node-visit optimal 1 – 2 brother trees....Pages 213-221
A graph theoretic approach to determinism versus non-determinism....Pages 222-232
Une caracterisation de trois varietes de langages bien connues....Pages 233-243
Über eine minimale universelle Turing-Maschine....Pages 244-259
Sur les varietes de langages et de monoïdes....Pages 260-265
Automaten in planaren graphen....Pages 266-275
Theoreme de transversale rationnelle pour les automates a pile deterministes....Pages 276-285
On the additive complexity of polynomials and some new lower bounds....Pages 286-297
Remarks on the nonexistence of some covering grammars....Pages 298-309
Zur Komplexität der Presburger Arithmetik und des Äquivalenzproblems einfacher Programme....Pages 310-318