Automata, languages and programming : fourth colloquium, University of Turku, Finland, July 18-22, 1977

edited by Arto Salomaa and Magnus Steinby


  • How hard is compiler code generation?.- "Natural" complexity measures and time versus memory: Some definitional proposals.- Semantics and proof theory of pascal procedures.- On the structure of combinatorial problems and structure preserving reductions.- Factor graphs, failure functions and Bi-Trees.- Parallel decomposition of LR(k) parsers.- Some recursively unsolvable problems relating to isolated cutpoints in probabilistic automata.- Termination tests inside ?-calculus.- On the computational power of reversal-bounded machines.- The contextsensitivity bounds of contextsensitive grammars and languages.- Serial composition of 2-way finite-state transducers and simple programs on strings.- The sequence equivalence problem for dol systems is decidable.- Languages defined by higher type program schemes.- Parsing and syntactic error recovery for context-free grammars by means of coarse structures.- On three types of unambiguity of context-free language.- The mathematics of record handling.- Macro grammars, lindenmayer systems and other copying devices.- On the time and tape complexity of hyper(1)-AFL's.- Renaming and erasing in szilard languages.- Some matching problems.- Complexite des demi - Groupes de matrices.- On the proper treatment or referencing, dereferencing and assignment.- Complexity of some problems concerning L systems.- Left-fitting translations.- Dynamic binary search.- About the derivation languages of grammars and machines.- Simple chain grammars.- Time-space trade-offs in a pebble game.- Non-deterministic polynomial optimization problems and their approximation.- Simple programs and their decision problems.- Theory of data structures by relational and graph grammars.- On backtracking and greatest fixpoints.- L systems of finite index.- The safety of a coroutine system.- Linear time simulation of multihead turing machines with head - To-head jumps.- Data types as objects.- On the difference between one and many.- On defining error recovery in context-free parsing.- LL(k) languages are closed under union with finite languages.- The time and tape complexity of developmental languages.- Rational relations of binary trees.- Structural equivalence of context-free grammar forms is decidable.- On the definition of classes of interpretations.

「Nielsen BookData」より


書名 Automata, languages and programming : fourth colloquium, University of Turku, Finland, July 18-22, 1977
著作者等 European Association for Theoretical Computer Science
International Colloquium on Automata, Languages and Programming
Salomaa, Arto
Steinby, Magnus
Steinby M.
Salomaa A.
シリーズ名 Lecture notes in computer science
出版元 Springer-Verlag
刊行年月 1977
ページ数 x, 569 p.
大きさ 25 cm
ISBN 0387083421
NCID BA01334898
※クリックでCiNii Booksを表示
言語 フランス語
出版国 ドイツ

Clip to Evernote