Bulletin of the EATCS, Volume 26

Volume 26, June 1985

Technical Contributions

Leonidas J. Guibas, John Hershberger: Computing the visibility graphs of n line segments in O(n_n) time. 13-20
Christos H. Papadimitriou: A note the expressive power of Prolog. 21-22
Athanasios K. Tsakalidis: The nearest common ancestor in a dynamic tree. 23-31
Manfred Broy, Andrzej Tarlecki: Algebraic specification of the abstract data type "Continuum". 32-35
Joost Engelfriet: The non-computability of computability. 36-39
W. Erni, R. Geibel: Recognition of EOL by polynomial Boolean circuits. 40-42
Haim Gaifman, Moshe Y. Vardi: A simple proof that connectivity of finite graphs is not first-order definable. 43-44
Marian Gheorghe: Descriptional complexity measures suggested by Hartmann's error recovery scheme. 45-54
Klaus-Jörn Lange: Addendum to "A note on the closure of EOL languages under erasing homomorphismus". 55
Jean-Jacques Pansiot: Subword complexities and iteration. 55-62
K. G. Subramanian: Regular control on NLC grammars. 63-64
Moshe Y. Vardi: A responce to "A complete axiomatisation for full join dependencies in relations". 65-66
Jozef Vyskoc: Pigeon-hole principle and Booleanmatrix multipication. 67-68