Alfred V. Aho, Ravi Sethi (auth.), Arto Salomaa, Magnus Steinby (eds.)3540083421, 9783540083429
Table of contents :
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
Reviews
There are no reviews yet.