Automata, Languages and Programming: Fourth Colloquium, University of Turku, Finland July 18–22, 1977

How hard is compiler code generation?....Pages 1-15
"Natural" complexity measures and time versus memory: Some definitional proposals....Pages 16-29
Semantics and proof theory of pascal procedures....Pages 30-44
On the structure of combinatorial problems and structure preserving reductions....Pages 45-60
Factor graphs, failure functions and Bi-Trees....Pages 61-75
Parallel decomposition of LR(k) parsers....Pages 76-86
Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata....Pages 87-94
Termination tests inside λ-calculus....Pages 95-110
On the computational power of reversal-bounded machines....Pages 111-119
The contextsensitivity bounds of contextsensitive grammars and languages....Pages 120-134
Serial composition of 2-way finite-state transducers and simple programs on strings....Pages 135-147
The sequence equivalence problem for dol systems is decidable....Pages 148-163
Languages defined by higher type program schemes....Pages 164-179
Parsing and syntactic error recovery for context-free grammars by means of coarse structures....Pages 180-192
On three types of unambiguity of context-free language....Pages 193-205
The mathematics of record handling....Pages 206-220
Macro grammars, lindenmayer systems and other copying devices....Pages 221-229
On the time and tape complexity of hyper(1)-AFL's....Pages 230-243
Renaming and erasing in szilard languages....Pages 244-257
Some matching problems....Pages 258-268
Complexite des demi — Groupes de matrices....Pages 269-281
On the proper treatment or referencing, dereferencing and assignment....Pages 282-300
Complexity of some problems concerning L systems....Pages 301-308
Left-fitting translations....Pages 309-322
Dynamic binary search....Pages 323-336
About the derivation languages of grammars and machines....Pages 337-351
Simple chain grammars....Pages 352-364
Time-space trade-offs in a pebble game....Pages 365-369
Non-deterministic polynomial optimization problems and their approximation....Pages 370-379
Simple programs and their decision problems....Pages 380-390
Theory of data structures by relational and graph grammars....Pages 391-411
On backtracking and greatest fixpoints....Pages 412-429
L systems of finite index....Pages 430-439
The safety of a coroutine system....Pages 440-452
Linear time simulation of multihead turing machines with head — To-head jumps....Pages 453-464
Data types as objects....Pages 465-479
On the difference between one and many....Pages 480-491
On defining error recovery in context-free parsing....Pages 492-503
LL(k) languages are closed under union with finite languages....Pages 504-508
The time and tape complexity of developmental languages....Pages 509-523
Rational relations of binary trees....Pages 524-538
Structural equivalence of context-free grammar forms is decidable....Pages 539-553
On the definition of classes of interpretations....Pages 554-569