Automata, Languages and Programming
Fourth Colloquium, University of Turku, Finnland, July 18-22, 1977
Published on 11. July 1977
Book
Paperback/Softback
XII, 572 pages
978-3-540-08342-9 (ISBN)
Description
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 acoroutine 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.
More details
Series
Edition
1977 ed.
Language
English
Place of publication
Berlin
Germany
Publishing group
Springer Berlin
Target group
Professional and scholarly
Research
Illustrations
XII, 572 p.
Dimensions
Height: 235 mm
Width: 155 mm
Thickness: 32 mm
Weight
873 gr
ISBN-13
978-3-540-08342-9 (9783540083429)
DOI
10.1007/3-540-08342-1
Schweitzer Classification
Content
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 acoroutine 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.