%A Martin Davis %T Why Godel didn't have Church's thesis %J Information & Control %K infctrl %V 54 %N 1/2 %D July/August 1982 %P 3-24 %A Howard A. Blair %T The recursion-theoretic complexity of the semantics of predicate logic as a programming language %J Information & Control %K infctrl %V 54 %N 1/2 %D July/August 1982 %P 25-47 %A Kenneth L. Manders %A Robert F. Daley %T The complexity of the validity problem for dynamic logic %J Information & Control %K infctrl %V 54 %N 1/2 %D July/August 1982 %P 48-69 %A J.W. de\ Bakker %A J.L. Zucker %T Processes and the denotational semantics of concurrency %J Information & Control %K infctrl %V 54 %N 1/2 %D July/August 1982 %P 70-120 %A Robert S. Streett %T Propositional dynamic logic of looping and converse is elementarily decidable %J Information & Control %K infctrl %V 54 %N 1/2 %D July/August 1982 %P 121-141 %A Stathis Zachos %T Robustness of probabilistic computational complexity classes under definitional perturbation %J Information & Control %K infctrl %V 54 %N 3 %D September 1982 %P 143-154 %A H.A. Maurer %A G. Rozenberg %A E. Welzl %T Using string languages to describe picture languages %J Information & Control %K infctrl %V 54 %N 3 %D September 1982 %P 155-185 %A J.A. Bergstra %A J.V. Tucker %T The completeness of the algebraic specification methods for computable data types %J Information & Control %K infctrl %V 54 %N 3 %D September 1982 %P 186-200 %A Simonetta Ronchi della Rocca %T Characterization theorems for a filter lambda model %J Information & Control %K infctrl %V 54 %N 3 %D September 1982 %P 201-216 %A Pavol Duris %A Zvi Galil %T On reversal-bounded counter machines and on pushdown automata with a bound on the size of the pushdown store %J Information & Control %K infctrl %V 54 %N 3 %D September 1982 %P 217-227 %A Ronald L. Rivest %A Adi Shamir %T How to reuse a "write once" memory %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 1-19 %A Paul M.B. Vitanyi %T On efficient simulations of multicounter machines %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 20-39 %A R. Kannan %T Circuit-size lower bounds and non-reducibility to sparse sets %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 40-56 %A D. Dolev %A S. Even %A R.M. Karp %T On the security of ping pong protocols %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 57-68 %A Yuri Gurevich %A Harry R. Lewis %T The inference problem for template dependencies %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 69-79 %A Andreas Blass %A Yuri Gurevich %T On the unique satisfiability problem %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 80-88 %A Klaus J. Berkling %A Elfriede Fehr %T A consistent extension of the lambda calculus as a base for functional programming languages %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 89-101 %A Hans-Ulrich Simon %T A tight Omega(log log n) bound on the time for parallel RAM's to compute nondegenerated boolean functions %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 102-107 %A Sara Porat %A Nissim Francez %A Shlomo Moran %A Shmuel Zaks %T Fair derivations in context-free grammars %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 108-116 %A Shimon Even %A Timothy J. Long %A Yacov Yacobi %T A note on deterministic and nondeterministic time complexity %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 117-124 %A Bernhard Eisenbarth %A Nivio Ziviani %A Gaston H. Gonnet %A Kurt Mehlhorn %A Derick Wood %T The theory of fringe analysis and its application to 2-3 trees and B-trees %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 125-174 %A D. Harel %A R. Sherman %T Looping vs. repeating in dynamic logic %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 175-192 %A Akira Ito %A Katsushi Inoue %A Itsuo Takanami %A Hiroshi Taniguchi %T Two-dimensional alternating Turing machines with only universal states %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 193-221 %A Ian F. Blake %T The enumeration of certain run length sequences %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 222-237 %A D.L. Neuhoff %A P.C. Shields %T Channel distances and representation %J Information & Control %K infctrl %V 55 %N 1/2/3 %D October/November/December 1982 %P 238-264 %A Gary L. Miller %T Isomorphism of k-contractible graphs. A generalization of bounded valence and bounded genus %J Information & Control %K infctrl %V 56 %N 1/2 %D January/February 1983 %P 1-20 %A Gary L. Miller %T Isomorphism of graphs which are pairwise k-separable %J Information & Control %K infctrl %V 56 %N 1/2 %D January/February 1983 %P 21-33 %A Burchard von Vraunmuhl %A Stephen Cook %A Kurt Mehlhorn %A Rutger Verbeek %T The recognition of deterministic CFLs in small time and space %J Information & Control %K infctrl %V 56 %N 1/2 %D January/February 1983 %P 34-51 %A Martin D. Davis %A Elaine J. Weyuker %T A formal notion of program-based test data adequacy %J Information & Control %K infctrl %V 56 %N 1/2 %D January/February 1983 %P 52-71 %A Pierre Wolper %T Temporal logic can be more expensive %J Information & Control %K infctrl %V 56 %N 1/2 %D January/February 1983 %P 72-99 %A John Case %T Pseudo-extensions of computable functions %J Information & Control %K infctrl %V 56 %N 1/2 %D January/February 1983 %P 100-111 %A Albert R. Meyer %A John C. Mitchell %T Termination assertions for recursive programs: completeness and axiomatic definability %J Information & Control %K infctrl %V 56 %N 1/2 %D January/February 1983 %P 112-138 %A Karel Culik,\ II %A Arto Salomaa %T Ambiguity and decision problems concerning number systems %J Information & Control %K infctrl %V 56 %N 3 %D March 1983 %P 139-153 %A John C. Mitchell %T The implication problem for functional and inclusion dependencies %J Information & Control %K infctrl %V 56 %N 3 %D March 1983 %P 154-182 %A Uzi Vishkin %A Avi Widgerson %T Dynamic parallel memories %J Information & Control %K infctrl %V 56 %N 3 %D March 1983 %P 183-198 %A Hana Galpern %A Avi Widgerson %T Sucinct representations of graphs %J Information & Control %K infctrl %V 56 %N 3 %D March 1983 %P 199-211 %A H.S. Witsenhausen %A A.D. Wyner %T On storage media with aftereffects %J Information & Control %K infctrl %V 56 %N 3 %D March 1983 %P 212-219 %A Tsutomu Kamimura %T Tree automata and attribute grammars %J Information & Control %K infctrl %V 57 %N 1 %D April 1983 %P 1-20 %A Dung T. Huynh %T Commutative grammars: the complexity of uniform word problems %J Information & Control %K infctrl %V 57 %N 1 %D April 1983 %P 21-39 %A Stuart A. Kurtz %T On the random oracle hypothesis %J Information & Control %K infctrl %V 57 %N 1 %D April 1983 %P 40-47 %A A.P. Stolboushkin %A M.A. Taitslin %T Deterministic dynamic logic is strictly weaker than dynamic logic %J Information & Control %K infctrl %V 57 %N 1 %D April 1983 %P 48-55 %A Joseph Y. Halpern %T Deterministic process logic is elementary %J Information & Control %K infctrl %V 57 %N 1 %D April 1983 %P 56-90 %A Larry Stockmeyer %T Optimal orientations of cells in slicing floorplan designs %J Information & Control %K infctrl %V 57 %N 2/3 %D May/June 1983 %P 91-101 %A William G. Golson %A William C. Rounds %T Connections between two theories of concurrency: metric spaces and synchronization trees %J Information & Control %K infctrl %V 57 %N 2/3 %D May/June 1983 %P 102-124 %A U. Goltz %A W. Resig %T The non-sequential behaviour of Petri nets %J Information & Control %K infctrl %V 57 %N 2/3 %D May/June 1983 %P 125-147 %A Mitchell Wand %T Loops in combinator-based compilers %J Information & Control %K infctrl %V 57 %N 2/3 %D May/June 1983 %P 148-164 %A L. Csirmaz %T On the strength of "sometimes" and "always" in program verification %J Information & Control %K infctrl %V 57 %N 2/3 %D May/June 1983 %P 165-179 %A Etienne Grandjean %T Complexity of the first-order theory of almost all finite structures %J Information & Control %K infctrl %V 57 %N 2/3 %D May/June 1983 %P 180-204 %A Antonio Restivo %A Chrisophe Reutenauer %T Some applications of a theorem of Shirshov to language theory %J Information & Control %K infctrl %V 57 %N 2/3 %D May/June 1983 %P 205-213 %A Aivar A. Lorenc %A Janis K. Lapins %T Discrete random process stabilization %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 1-18 %A Jean-Marc Steyaert %A Philippe Flajolet %T Patterns and pattern-matching in trees: an analysis %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 19-58 %A Pawel Urzyczyn %T Nontrivial definability by flow-chart programs %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 59-87 %A W. Ian Gasarch %A Steven Homer %T Relativizations comparing NP and exponential time %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 88-100 %A Stavros S. Cosmadakis %T The complexity of evaluating relational queries %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 101-112 %A A. Borodin %A S. Cook %A N. Pippenger %T Parallel computations for well-endowed rings and space-bounded probabilistic machines %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 113-136 %A Kurt Mehlhorn %A Franco P. Preparata %T Area-time optimal VLSI integer multiplier with minimum computation time %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 137-156 %A Ker-I Ko %T On the computational complexity of ordinary differential equations %J Information & Control %K infctrl %V 58 %N 1/2/3 %D July/August/September 1983 %P 157-194 %A Susumu Yamasaki %A Shuki Doshita %T The satisfiability problem for a class consisting of Horn sentences and some non-Horn sentences in proportional logic %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 1-12 %A A. Ehrenfeucht %A G. Rozenberg %T Repetition of subwords in D0L languages %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 13-35 %A M. Hennessy %T Synchronous and asynchronous experiments on processes %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 36-83 %A Imre Barany %A Zoltan Furedi %T Mental poker with three or more players %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 84-93 %A A.P. Stolboushkin %T Regular dynamic logic is not interpretable in deterministic context-free dynamic logic %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 94-107 %A Hartmut Schmeck %T Algebraic semantics of recursive flowchart schemes %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 108-126 %A Henk Barenbrecht %A Adrian Rezus %T Semantics for classical AUTOMATH and related systems %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 127-147 %A Ludwig Staiger %T Subspaces of GF(q)^omega and convolutional codes %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 148-183 %A Jurgen Weiss %T An n^3/2 lower bound on the monotone network complexity of the boolean convolution %J Information & Control %K infctrl %V 59 %N 1/2/3 %D October/November/December 1983 %P 184-188 %A Pavol Duris %A Zvi Galil %A Wolfgang Paul %A Ruediger Reischuk %T Two nonlinear lower bounds for on-line computations %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 1-11 %A Jerzy Tiutyn %T Unbounded program memory adds to the expressive power of first-order programming logic %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 12-35 %A M. Falaschi %A G. Levi %A C. Palamidessi %T A synchronization logic: axiomatics and formal semantics of generalized Horn clauses %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 36-69 %K GHC %A Michael C. Loui %T The complexity of sorting on distributed systems %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 70-85 %A D. Harel %A D. Peleg %T On static logics, dynamic logics, and complexity classes %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 86-102 %A Eljas Soisalon-Soininen %A Peter Widmayer %T On the complexity of concurrency control by locking in distributed database systems %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 103-108 %A J.A. Bergstra %A J.W. Klop %T Process algebra for synchronous communication %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 109-137 %A R.J.R. Back %A H. Mannila %T A semantic approach to program modularity %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 138-167 %A P. Papantoni-Kazakos %T A game theoretic approach to robust filtering %J Information & Control %K infctrl %V 60 %N 1/2/3 %D January/February/March 1983 %P 168-191 %A E.G. Coffman,\ Jr. %A E.N. Gilbert %T Dynamic, first-fit packings in two or more dimensions %J Information & Control %K infctrl %V 61 %N 1 %D April 1983 %P 1-14 %A Leonid A. Levin %T Randomness conservation inequalities; information and independence in mathematical theories %J Information & Control %K infctrl %V 61 %N 1 %D April 1983 %P 15-37 %A C. Mohan %A D. Fussell %A A. Silberschatz %T Compatability and commutativity of lock modes %J Information & Control %K infctrl %V 61 %N 1 %D April 1983 %P 38-64 %A Yuri Gurevich %A Harry R. Lewis %T A logic for constant-depth circuits %J Information & Control %K infctrl %V 61 %N 1 %D April 1983 %P 65-74 %A Catriel Beeri %A Moshe Y. Vardi %T On acyclic database decomposition %J Information & Control %K infctrl %V 61 %N 2 %D May 1983 %P 75-84 %A P.S. Thiagarajan %A K. Voss %T A fresh look at free choice nets %J Information & Control %K infctrl %V 61 %N 2 %D May 1983 %P 85-113 %K Petri nets %A Ernst E. Doberkat %T An average case analysis of Floyd's algorithm to construct heaps %J Information & Control %K infctrl %V 61 %N 2 %D May 1983 %P 114-131 %A G.L. Feng %A K.K. Tzeng %T On quasi-perfect property of double-error-correcting Goppa codes and their complete decoding %J Information & Control %K infctrl %V 61 %N 2 %D May 1983 %P 132-146 %A Peter H. Schmitt %T Diamond formulas: a fragment of dynamic logic with recursively enumerable validity problem %J Information & Control %K infctrl %V 61 %N 2 %D May 1983 %P 147-158 %A Shimon Even %A Alan L. Selman %A Yacov Yacobi %T The complexity of promise problems with applications to public-key cryptography %J Information & Control %K infctrl %V 61 %N 2 %D May 1983 %P 159-173 %A E. Allen Emerson %A A. Prasad Sistla %T Deciding full branching time logic %J Information & Control %K infctrl %V 61 %N 3 %D June 1983 %P 175-201 %A Manfred Broy %T Semantics of communicating processes %J Information & Control %K infctrl %V 61 %N 3 %D June 1983 %P 202-246 %A Damiean Niwinski %T Fixed-point characterization of context-free inifinity-languages %J Information & Control %K infctrl %V 61 %N 3 %D June 1983 %P 247-276 %A H.A.G. Wijshoff %A J. van\ Leeuwen %T Arbitrary versus periodic storage schemes and tessalations of the plane using one type of polyomino %J Information & Control %K infctrl %V 62 %N 1 %D July 1984 %P 1-25 %A Yair Itzhaik %A Amiram Yehudai %T An intermediate machine technique for deciding between an DPDA and a linear DPDA %J Information & Control %K infctrl %V 62 %N 1 %D July 1984 %P 26-35 %A Paola Giannini %A Giuseppe Longo %T Effectively given domains and lambda-calculus models %J Information & Control %K infctrl %V 62 %N 1 %D July 1984 %P 36-63 %A R.E. Krichevsky %T Optimal hashing %J Information & Control %K infctrl %V 62 %N 1 %D July 1984 %P 64-92 %A Richard E. Ladner %A Larry J. Stockmeyer %A Richard J. Lipton %T Alternation between auxiliary pushdown automata %J Information & Control %K infctrl %V 62 %N 2/3 %D August/September 1984 %P 93-108 %A Jia-Wei Hong %T On similarity and duality of computation (I) %J Information & Control %K infctrl %V 62 %N 2/3 %D August/September 1984 %P 109-128 %A Ingo Wegener %T Optimal decision trees and one-time-only branching programs for symmetric boolean functions %J Information & Control %K infctrl %V 62 %N 2/3 %D August/September 1984 %P 129-143 %A Michael G. Main %A David B. Benson %T Functional behavior of nondeterministic and concurrent programs %J Information & Control %K infctrl %V 62 %N 2/3 %D August/September 1984 %P 144-189 %A Jennifer Lundelius %A Nancy Lynch %T An upper and lower bound for clock synchronization %J Information & Control %K infctrl %V 62 %N 2/3 %D August/September 1984 %P 190-204 %A Harvey Friedman %T On the spectra of universal relational sentences %J Information & Control %K infctrl %V 62 %N 2/3 %D August/September 1984 %P 205-209 %A J. Ian Munro %A Patricio V. Poblete %T Fault tolerance and storage reduction in binary search trees %J Information & Control %K infctrl %V 62 %N 2/3 %D August/September 1984 %P 210-218 %A Benjamin Arazi %T An approach for generating different types of Gray codes %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 1-10 %A Yishai A. Feldman %T A decidable propositional dynamic logic with explicit probabilities %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 11-38 %A Richard Cole %A Chee K. Yap %T Geometric retrieval problems %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 39-57 %A Paliath Narendran %A Friedrich Otto %A Karl Winklmann %T The uniform conjugacy problem for finite Church-Rosser Thue systems is NP-complete %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 58-66 %A J.M. Robson %T Fast probabilistic RAM simulation of single-tape Turing machine computations %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 67-87 %A A.P. Sistla %A E.M. Clarke %A N. Francez %A A.R. Meyer %T Can message buffers be axiomatized in linear temporal logic ? %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 88-112 %A H.C.M. Kleijn %A M. Penttonen %A G. Rozenberg %A K. Salomaa %T Direction independent context-sensitive grammars %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 113-117 %A David Harel %A Dexter Kozen %T A programming language for the inductive sets, and applications %J Information & Control %K infctrl %V 63 %N 1/2 %D October/November 1984 %P 118-139 %A Ralf Hartmut Guting %T Dynamic C-oriented polygonal intersection searching %J Information & Control %K infctrl %V 63 %N 3 %D December 1984 %P 143-163 %A D.S. Franzblau %A D.J. Kleitman %T An algorithm for covering polygons with rectangles %J Information & Control %K infctrl %V 63 %N 3 %D December 1984 %P 164-189 %A Andrzei Ehrenfeucht %A Grzegorz Rozenberg %T An easy proof of Greibach normal form %J Information & Control %K infctrl %V 63 %N 3 %D December 1984 %P 190-199 %A M.G. Gouda %A E.G. Manning %A Y.T. Yu %T On the progress of communication between two finite-state machines %J Information & Control %K infctrl %V 63 %N 3 %D December 1984 %P 200-216 %A M. Ajtai %A M. Fredman %A J. Komlos %T Hash functions for priority queues %J Information & Control %K infctrl %V 63 %N 3 %D December 1984 %P 217-226 %A Ravi Kannan %T Unraveling k-page graphs %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 1-5 %A William C. Rounds %T On the relationship between Scott domains, synchronization trees, and metric spaces %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 6-28 %A Michal Grabowski %T On relative completeness of Hoare logics %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 29-44 %A Norbert Blum %T An area-maximum edge length trade-off for VLSI layout %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 45-52 %A Foto Afrati %A Christos H. Papadimitriou %A George Papageorgiou %T The complexity of cubical graphs %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 53-60 %A Greg N. Frederickson %T Implicit data structures for weighted elements %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 61-82 %A Orna Grumberg %A Nissim Francez %A Johann A. Makowsky %A Willem P. de\ Roever %T A proof rule for fair termination of guarded commands %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 83-102 %A Dung T. Huynh %T The complexity of equivalence problems for commutative grammars %J Information & Control %K infctrl %V 66 %N 1/2 %D July/August 1985 %P 103-121 %A J.M. Robson %T Alternation with restrictions on looping %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 2-11 %A Wojciech Rytter %T Fast recognition of pushdown automaton and context-free languages %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 12-22 %A Matthew Hennessy %A Colin Stirling %T The power of the future perfect in program logics %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 23-52 %A Jose L. Balcazar %A Josep Diaz %A Joaquim Gabarro %T Uniform characterizations of non-uniform complexity measures %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 53-69 %A Andreas Blass %A Yuri Gurevich %A Dexter Kozen %T A zero-one law for logic with a fixed-point operator %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 70-90 %A Uzi Vishkin %T Optimal parallel pattern matching in strings %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 91-113 %A Oscar H. Ibarra %A Sam M. Kim %A Louis E. Rosier %T Some characterizations of multihead finite automata %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 114-125 %A Oscar H. Ibarra %A Sam M. Kim %A Louis E. Rosier %T On space and time efficient TM simulations of some restricted classes of PDA's %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 126-143 %A Zvi Galil %T Optimal parallel algorithms for string matching %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 144-157 %A Marek Karpinski %A Rutger Verbeek %T There is no polynomial deterministic space simulation of probabilistic space with a two-way random-tape generator %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 158-162 %A Helge Szwerinski %T Symmetrical one-dimensional cellular spaces %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 163-172 %A Athanasios K. Tsakalidis %T AVL-trees for localized search %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 173-194 %A Friedhelm Meyer\ auf\ der\ Heide %T Lower time bounds for solving linear Diophantine equations on several parallel computational models %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 195-211 %A Ingo Wegener %T The critical complexity of all (monotone) boolean functions and monotone graph properties %J Information & Control %K infctrl %V 67 %N 1/2/3 %D October/November/December 1985 %P 212-222 %A Paolo Atzeni %A Nicola M. Morfuni %T Functional dependencies and constraints on null values in database relations %J Information & Control %K infctrl %V 70 %N 1 %D July 1986 %P 1-31 %A Richard Cole %A Uzi Vishkin %T Deterministic coin tossing with applications to optimal parallel list ranking %J Information & Control %K infctrl %V 70 %N 1 %D July 1986 %P 32-53 %A Pekka Orponen %A Uwe Schoning %T The density and complexity of polynomial cores for intractable sets %J Information & Control %K infctrl %V 70 %N 1 %D July 1986 %P 54-68 %A Paolo Atzeni %A Nicola M. Morfuni %T Functional dependencies and constraints on null values in database relations %J Information & Control %K infctrl %V 70 %N 1 %D July 1986 %P 1-31 %A Richard Cole %A Uzi Vishkin %T Deterministic coin tossing with applications to optimal parallel list ranking %J Information & Control %K infctrl %V 70 %N 1 %D July 1986 %P 32-53 %A Pekka Orponen %A Uwe Schoning %T The density and complexity of polynomial cores for intractable sets %J Information & Control %K infctrl %V 70 %N 1 %D July 1986 %P 54-68 %A Daniel N. Osherson %A Michael Stob %A Scott Weinstein %T Aggregating inductive expertise %J Information & Control %K infctrl %V 70 %N 1 %D July 1986 %P 69-95 %A Sergiu Hart %A Michar Sharir %T Probabilistic propositional temporal logics %J Information & Control %K infctrl %V 70 %N 2/3 %D August/September 1986 %P 97-155 %A James S. Royer %T Inductive inference of approximations %J Information & Control %K infctrl %V 70 %N 2/3 %D August/September 1986 %P 156-178 %A Etsuro Moriya %A Shigeki Iwata %A Takumi Kasai %T A note on some simultaneous relations among time, space, and reversal for single work tape nondeterministic Turing machines %J Information & Control %K infctrl %V 70 %N 2/3 %D August/September 1986 %P 179-185 %A Peter Gacs %T Every sequence is reducible to a random one %J Information & Control %K infctrl %V 70 %N 2/3 %D August/September 1986 %P 186-192 %A Georg Lausen %A Eljas Soisalon-Soininen %A Peter Widmayer %T Pre-analysis locking %J Information & Control %K infctrl %V 70 %N 2/3 %D August/September 1986 %P 193-215 %A Larry Denenberg %A Yuri Gurevich %A Sharan Shelah %T Definability by constant-depth polynomial-size circuits %J Information & Control %K infctrl %V 70 %N 2/3 %D August/September 1986 %P 216-240 %A Werner Damm %A Andreas Goerdt %T An automata-theoretical characterization of the OI-hierarchy %J Information & Control %K infctrl %V 71 %N 1/2 %D October/November 1986 %P 1-32 %A Hirofumi Yokoguchi %T Retraction map categories and their applications to the construction of lambda calculus models %J Information & Control %K infctrl %V 71 %N 1/2 %D October/November 1986 %P 33-86 %A Stanislav Zak %T An exponential lower bound for real-time branching programs %J Information & Control %K infctrl %V 71 %N 1/2 %D October/November 1986 %P 87-94 %A David MacQueen %A Gordon Plotkin %A Ravi Sethi %T An ideal model for recursive polymorphic types %J Information & Control %K infctrl %V 71 %N 1/2 %D October/November 1986 %P 95-130 %A Marek Karpinski %A Rutger Verbeek %T On the power of two-way random generators and the impossibility of deterministic poly-space simulation %J Information & Control %K infctrl %V 71 %N 1/2 %D October/November 1986 %P 131-142 %A H.L. Bodlaender %A J. van\ Leeuwen %T Simulation of large networks on smaller networks %J Information & Control %K infctrl %V 71 %N 3 %D December 1986 %P 143-180 %A Christos H. Papadimitriou %A Mihalis Yannakakis %T A note on succinct representations of graphs %J Information & Control %K infctrl %V 71 %N 3 %D December 1986 %P 181-185 %A Chilukuri K. Mohan %A Mandayan K. Srivas %T Function definitions in term rewriting and applicative programming %J Information & Control %K infctrl %V 71 %N 3 %D December 1986 %P 186-217 %A K. Culik,\ II %A J. Gruska %A A. Salomaa %T Systolic trellis automata: stability: decidability and complexity %J Information & Control %K infctrl %V 71 %N 3 %D December 1986 %P 218-230 %A Hans Heller %T On relativized exponential and probabilistic complexity classes %J Information & Control %K infctrl %V 71 %N 3 %D December 1986 %P 231-243