Acta Informatica, Volume 22

Volume 22, Number 1, 1985

Michael Bechtold, Guy Pujolle, Otto Spaniol: Throughput of a Satellite Channel Communication. 1-14 BibTeX
Jeffrey H. Kingston: Analysis of Tree Algorithms for the Simulation Event List. 15-33 BibTeX
Fred B. Schneider, Richard Conway, Dale Skeen: Thrifty Execution of Task Pipelines. 35-45 BibTeX
Ali Mili, Jules Desharnais, Jean-Raymond Gagné: Strongest Invariant Functions: Their Use in the Systematic Analysis of While Statements. 47-66 BibTeX
Dean Jacobs, David Gries: General Correctness: A Unification of Partial and Total Correctness. 67-83 BibTeX
Thomas Ottmann, Michael Schrapp, Derick Wood: Purely Top-Down Updating Algorithms for Stratified Search Trees. 85-100 BibTeX
Donald W. Loveland: Performance Bounds for Binary Testing with Arbitrary Weights. 101-114 BibTeX
Burkhard Monien, Ewald Speckenmeyer: Ramsey Numbers and an Approximation Algorithm for the Vertex Cover Problem. 115-123 BibTeX

Carlo Meghini, Costantino Thanos: Querying Fragmented Relations in a Distributed Database. 125-138 BibTeX
John L. Bruno: On Scheduling Tasks with Exponential Service Times and In-Tree Precedence Constraints. 139-148 BibTeX
Jim Cunningham, A. J. J. Dick: Rewrite Systems on a Lattice of Types. 149-169 BibTeX
Jörg-Rüdiger Sack, Thomas Strothotte: An Algorithm for Merging Heaps. 171-186 BibTeX
Norishige Chiba, Kazunori Onoguchi, Takao Nishizeki: Drawing Plane Graphs Nicely. 187-201 BibTeX
Tsutomu Kamimura: An Effectively Given Initial Semigroup. 203-227 BibTeX
Paul E. S. Dunne: A 2.5n Lower Bound on the Monotone Network Complexity of T_3^n. 229-240 BibTeX

Bogdan Rembowski: A Priority Queue With Interruptions of Service Permitted After a Time Quantum. 241-251 BibTeX
Balakrishnan Krishnamurthy: Short Proofs for Tricky Formulas. 253-275 BibTeX
Jakob Gonczarowski: Decidable Properties of Monadic Recursive Schemas With a Depth Parameter. 277-310 BibTeX
Piotr Rudnicki, Wlodzimierz Drabent: Proving Properties of Pascal Programs in MIZAR 2. 311-331 BibTeX
John L. Bruno, Peter J. Downey: Probabilistic Bounds for Dual Bin-Packing. 333-345 BibTeX

A. J. Kfoury, Pawel Urzyczyn: Necessary and Sufficient Conditions for the Universality of Programming Formalisms. 347-377 BibTeX
Moon-Jung Chung, Michael Evangelist, Ivan Hal Sudborough: Complete Problems for Space Bounded Subclasses of NP. 379-395 BibTeX
Michael Sonnenschein: Global Storage Cells for Attributes in an Attribute Grammar. 397-420 BibTeX
Dung T. Huynh: Complexity of the Word Problem for Commutative Semigroups of Fixed Dimension. 421-432 BibTeX
Meurig Beynon: Replaceability and Computational Equivalence for Monotone Boolean Functions. 433-449 BibTeX
Errol L. Lloyd, Michael C. Loui: On the Worst Case Performance of Buddy Systems. 451-473 BibTeX

Masahiro Miyakawa: Optimum Decision Trees - An Optimal Variable Theorem and its Related Applications. 475-498 BibTeX
Stephan Heilbrunner: Truly Prefix-Correct Chain-Free LR (1) Parsers. 499-536 BibTeX
Bernhard Möller: On the Algebraic Specification of Infinite Objects - Ordered and Continuous Models of Algebraic Types. 537-578 BibTeX
Michel Latteux, B. Leguy, B. Ratoandromanana: The Family of One-Counter Languages is Closed Under Quotient. 579-588 BibTeX
Juraj Hromkovic: Fooling a Two-Way Nondeterministic Multihead Automaton with Reversal Number Restriction. 589-594 BibTeX

Paul Caspi, Nicolas Halbwachs: A Functional Model for Describing and Reasoning About Time Behaviour of Computing Systems. 595-627 BibTeX
Tobias Nipkow: Non-deterministic Data Types: Models and Implementations. 629-661 BibTeX
Bernd Reusch, Wolfgang Merzenich: Minimal Coverings for Incompletely Specified Sequential Machines. 663-678 BibTeX
Volker Diekert: Investigations on Hotz Groups for Arbitrary Grammars. 679-698 BibTeX
Piotr Rudnicki, Wlodzimierz Drabent: Proving Properties of Pascal Programs in MIZAR 2. 699-707 BibTeX