Last update:
Sat Jun 11 12:06:53 MDT 2016
Mike V. D. Burmester and
Yvo Desmedt All Languages in NP Have Divertible
Zero-Knowledge Proofs and Arguments
under Cryptographic Assumptions
(Extended Abstract) . . . . . . . . . . 1
George I. Davida and
Yvo Desmedt and
René Peralta On the Importance of Memory Resources in
the Security of Key Exchange Protocols
(Extended Abstract) . . . . . . . . . . 11
S. Shinozaki and
Toshiya Itoh and
Atsushi Fujioka and
Shigeo Tsujii Provably Secure Key-Updating Schemes in
Identity-Based Systems . . . . . . . . . 16
Bert den Boer Oblivious Transfer Protecting Secrecy
--- An Implementation for Oblivious
Transfer Protecting Secrecy Almost
Unconditionally and a Bitcommitment
Based on Factoring Protecting Secrecy
Unconditionally . . . . . . . . . . . . 31
Alfredo De Santis and
Giuseppe Persiano Public-Randomness in Public-Key
Cryptography (Extended Abstract) . . . . 46
Ernest F. Brickell and
Kevin S. McCurley An Interactive Identification Scheme
Based on Discrete Logarithms and
Factoring (Extended Abstract) . . . . . 63
Arjen K. Lenstra and
Mark S. Manasse Factoring with Two Large Primes
(Extended Abstract) . . . . . . . . . . 72
Jan-Hendrik Evertse and
Eug\`ene van Heyst Which New RSA Signatures Can Be from
Some Given RSA Signatures? (Extended
Abstract) . . . . . . . . . . . . . . . 83
Renate Scheidler and
Johannes A. Buchmann and
Hugh C. Williams Implementation of a Key Exchange
Protocol Using Real Quadratic Fields
(Extended Abstract) . . . . . . . . . . 98
François Morain Distributed Primality Proving and the
Primality of $ (2^{3539} + 1) / 3 $ . . 110
Sheelagh Lloyd Properties of Binary Functions . . . . . 124
Józef P. Pieprzyk How to Construct Pseudorandom
Permutations from Single Pseudorandom
Functions . . . . . . . . . . . . . . . 140
Kaisa Nyberg Constructions of Bent Functions and
Difference Sets . . . . . . . . . . . . 151
Bart Preneel and
Werner Van Leekwijck and
Luc Van Linden and
René Govaerts and
Joos Vandewalle Propagation Characteristics of Boolean
Functions . . . . . . . . . . . . . . . 161
Harald Niederreiter The Linear Complexity Profile and the
Jump Complexity of Keystream Sequences 174
Zong-Duo Dai and
Thomas Beth and
Dieter Gollmann Lower Bounds for the Linear Complexity
of Sequences over Residue Rings . . . . 189
Cees J. A. Jansen On the Construction of Run Permuted
Sequences . . . . . . . . . . . . . . . 196
Willi Meier and
Othmar Staffelbach Correlation Properties of Combiners with
Memory in Stream Ciphers (Extended
Abstract) . . . . . . . . . . . . . . . 204
Agnes Hui Chan and
Mark Goresky and
Andrew Klapper Correlation Functions of Geometric
Sequences . . . . . . . . . . . . . . . 214
Yacov Yacobi Exponentiating Faster with Addition
Chains . . . . . . . . . . . . . . . . . 222
Stephen R. Dusse and
Burt S. Kaliski Jr. A Cryptographic Library for the Motorola
DSP56000 . . . . . . . . . . . . . . . . 230
Holger Orup and
Erik Svendsen and
Erik Andreasen VICTOR --- an Efficient RSA Hardware
Implementation . . . . . . . . . . . . . 245
Charles H. Bennett and
François Bessette and
Gilles Brassard and
Louis Salvail and
John Smolin Experimental Quantum Cryptography . . . 253
Ingemar Ingemarsson and
Gustavus J. Simmons A Protocol to Set Up Shared Secret
Schemes without the Assistance of
Mutually Trusted Party . . . . . . . . . 266
Andrea Sgarro Lower Bounds for Authentication Codes
with Splitting . . . . . . . . . . . . . 283
Albrecht Beutelspacher and
Ute Rosenbaum Essentially $ \ell $-fold Secure
Authentication Systems . . . . . . . . . 294
Ben Smeets and
Peter Vanroose and
Zhe-xian Wan On the Construction of Authentication
Codes with Sand Codes Withstanding
Spoofing Attacks of Order $ {L} \geq 2 $ 306
Jacques Stern and
Philippe Toffin Cryptanalysis of a Public-Key
Cryptosystem Based on Approximations by
Rational Numbers . . . . . . . . . . . . 313
Paul C. van Oorschot and
Michael J. Wiener A Known-Plaintext Attack on Two-Key
Triple Encryption . . . . . . . . . . . 318
Shoji Miyaguchi and
Kazuo Ohta and
Masahiko Iwata Confirmation that Some Hash Functions
Are Not Collision Free . . . . . . . . . 326
Fritz Bauspieß and
Hans-Joachim Knobloch and
Peer Wichmann Inverting the Pseudo Exponentiation . . 344
Tzonelih Hwang Cryptosystem for Group Oriented
Cryptography . . . . . . . . . . . . . . 352
Ueli M. Maurer A Provably-Secure Strongly-Randomized
Cipher . . . . . . . . . . . . . . . . . 361
Kaoru Kurosawa and
Yutaka Katayama and
Wakaha Ogata and
Shigeo Tsujii General Public Key Residue Cryptosystems
and Mental Poker Protocols . . . . . . . 374
Xuejia Lai and
James L. Massey A Proposal for a New Block Encryption
Standard . . . . . . . . . . . . . . . . 389
Valtteri Niemi A New Trapdoor in Knapsacks . . . . . . 405
Alfredo De Santis and
Moti Yung On the Design of Provably-Secure
Cryptographic Hash Functions (Extended
Summary) . . . . . . . . . . . . . . . . 412
H. Ong and
Claus P. Schnorr Fast Signature Generation with a Fiat
Shamir-Like Scheme . . . . . . . . . . . 432
Gerrit Bleumer and
Birgit Pfitzmann and
Michael Waidner A Remark on Signature Scheme Where
Forgery Can Be Proved . . . . . . . . . 441
Kazuo Ohta and
Tatsuaki Okamoto and
Kenji Koyama Membership Authentication for
Hierarchical Multigroups Using the
Extended Fiat--Shamir Scheme . . . . . . 446
David Chaum Zero-Knowledge Undeniable Signatures
(Extended Abstract) . . . . . . . . . . 458
Louis C. Guillou and
Jean-Jacques Quisquater and
Mike Walker and
Peter Landrock and
Caroline Shaer Precautions Taken against Various
Potential Attacks in ISO/IEC DIS 9796 $
\ll $Digital Signature Scheme Giving
Message Recovery$ \gg $ . . . . . . . . 465
Josep Domingo-Ferrer Software Run-Time Protection: A
Cryptographic Issue . . . . . . . . . . 474
Marc Girault An Identity-Based Identification Scheme
Based on Discrete Logarithms Modulo a
Composite Number . . . . . . . . . . . . 481
Jovan Dj. Golic and
Miodrag J. Mihaljevic A Noisy Clock-Controlled Shift Register
Cryptanalysis Concept Based on Sequence
Comparison Approach . . . . . . . . . . 487
Burt S. Kaliski Jr. The MD4 Message Digest Algorithm . . . . 492
Mike V. D. Burmester A Remark on the Efficiency of
Identification Schemes . . . . . . . . . 493
Gisela Meister On an Implementation of the Mohan-Adiga
Algorithm . . . . . . . . . . . . . . . 496
W. Brauer and
R. Gold and
W. Vogler A survey of behaviour and equivalence
preserving refinements of Petri nets . . 1
B. Butler and
R. Esser and
R. Mattmann A distributed simulator for high order
Petri nets . . . . . . . . . . . . . . . 47
J. Cardoso and
R. Valette and
D. Dubois Petri nets with uncertain markings . . . 64
J. M. Colom and
M. Silva Convex geometry and semiflows in P/T
nets. A comparative study of algorithms
for computation of minimal P-semiflows 79
J. M. Colom and
M. Silva Improving the linearly based
characterization of P/T nets . . . . . . 113
J. M. Couvreur and
J. Martinez Linear invariants in commutative high
level nets . . . . . . . . . . . . . . . 146
J. Desel and
A. Merceron Vicinity respecting net morphisms . . . 165
C. Dutheillet and
S. Haddad Regular stochastic Petri nets . . . . . 186
J. Esparza and
M. Silva Circuits, handles, bridges and nets . . 210
J. Esparza and
M. Silva On the analysis and synthesis of free
choice systems . . . . . . . . . . . . . 243
G. Florin and
C. Kaiser and
S. Natkin Petri net models of a distributed
election protocol on a unidirectional
ring . . . . . . . . . . . . . . . . . . 287
P. Huber and
K. Jensen and
R. M. Shapiro Hierarchies in coloured Petri nets . . . 313
K. Jensen Coloured Petri nets: A high level
language for system design and analysis 342
G. J. Nutt A simulation system architecture for
graph models . . . . . . . . . . . . . . 417
L. Pomello and
C. Simone A state transformation preorder over a
class of EN systems . . . . . . . . . . 436
Y. Souissi and
G. Memmi Composition of nets via a communication
medium . . . . . . . . . . . . . . . . . 457
P. D. Stotts and
R. Furuta alpha Trellis: A system for writing and
browsing Petri-net-based hypertext . . . 471
A. Valmari Stubborn sets for reduced state space
generation . . . . . . . . . . . . . . . 491
Anonymous Introduction . . . . . . . . . . . . . . 1
Anonymous Genetic Algorithms . . . . . . . . . . . 3--3
A. E. Eiben and
E. H. L. Aarts and
K. M. Van Hee Global Convergence of Genetic
Algorithms: A Markov Chain Analysis . . 4
D. E. Goldberg The Theory of Virtual Alphabets . . . . 13
J. Hesser and
R. Manner Towards an Optimal Mutation Probability
for Genetic Algorithms . . . . . . . . . 23
J. Hesser and
R. Manner An Alternative Genetic Algorithm . . . . 33
K. A. De Jong and
W. M. Spears An Analysis of the Interacting Roles of
Population Size and Crossover in Genetic
Algorithms . . . . . . . . . . . . . . . 38
C. Blume GLEAM --- A System for Simulated
Intuitive Learning . . . . . . . . . . . 48
A. Colorni and
M. Dorigo and
V. Maniezzo Genetic Algorithms and Highly
Constrained Problems: The Time-Table
Case . . . . . . . . . . . . . . . . . . 55
Y. Davidor and
Y. Goldberg An Evolution Standing on the Design of
Redundant Manipulators . . . . . . . . . 60
M. Gerrits and
P. Hogeweg Redundant Coding of an NP-Complete
Problem Allows Effective Genetic
Algorithm Search . . . . . . . . . . . . 70
M. Hulin Circuit Partitioning with Genetic
Algorithms Using a Coding Scheme to
Preserve the Structure of a Circuit . . 75
P. Husbands and
F. Mill and
S. Warrington Genetic Algorithms, Production Plan
Optimisation, and Scheduling . . . . . . 80
T. Johnson and
P. Husbands System Identification Using Genetic
Algorithms . . . . . . . . . . . . . . . 85
C. B. Lucasius and
S. Werten and
A. H. J. M. van Aert and
G. Kateman and
M. J. J. Blommers Conformational Analysis of DNA Using
Genetic Algorithms . . . . . . . . . . . 90
J.-Y. Suh and
C.-D. Lee Operator-Oriented Genetic Algorithm and
its Application to the Sliding Block
Puzzle Problem . . . . . . . . . . . . . 98
D. Thierens and
L. Vercauteren A Topology Exploiting Genetic Algorithm
to Control Dynamic Systems . . . . . . . 104
N. L. J. Ulder and
E. H. L. Aarts and
H.-J. Bandelt and
P. J. M. van Laarhoven and
E. Pesch Genetic Local Search Algorithms for the
Travelling Salesman Problem . . . . . . 109
H. de Garis Genetic Programming: Artificial Nervous
Systems, Artificial Embryos and
Embryological Electronics . . . . . . . 117
J. R. Koza Concept Formation and Decision Tree
Induction Using the Genetic Programming
Paradigm . . . . . . . . . . . . . . . . 124
H. C. Braun On Solving Travelling Salesman Problems
by Genetic Algorithms . . . . . . . . . 129
J. P. Cohoon and
W. N. Martin and
D. S. Richards Genetic Algorithms and Punctuated
Equilibria in VLSI . . . . . . . . . . . 134
T. C. Fogarty and
R. Huang Implementing the Genetic Algorithm on
Transputer Based Parallel Processing
Systems . . . . . . . . . . . . . . . . 145
M. Gorges-Schleuter Explicit Parallelism of Genetic
Algorithms through Population Structures 150
B. Kroger and
P. Schwenderling and
O. Vornberger Parallel Genetic Packing of Rectangles 160
G. von Laszewski and
H. Muhlenbein Partitioning a Graph with a Parallel
Genetic Algorithm . . . . . . . . . . . 165
P. Neuhaus Solving the Mapping-Problem ---
Experiences with a Genetic Algorithm . . 170
T. Starkweather and
D. Whitley and
K. Mathias Optimization Using Distributed Genetic
Algorithms . . . . . . . . . . . . . . . 176
M. Herdy Application of the Evolutionsstrategie
to Discrete Optimization Problems . . . 188
F. Kursawe A Variant of Evolution Strategies for
Vector Optimization . . . . . . . . . . 193
R. Lohmann Application of Evolution Strategy in
Parallel Populations . . . . . . . . . . 198
G. Rudolph Global Optimization by Means of
Distributed Evolution Strategies . . . . 209
I. Exman Solving Sequential Games with
Boltzmann-Learned Tactics . . . . . . . 216
K. H. Hoffmann and
M. Christoph and
M. Hanf Optimizing Simulated Annealing . . . . . 221
L. Kreuzer and
K. Goser A Local Timing Model for Parallel
Optimization with Boltzmann Machines . . 226
P. Roussel-Ragot and
N. Kouicem and
G. Dreyfus Error-Free Parallel Implementation of
Simulated Annealing . . . . . . . . . . 231
R. L. Shoemaker and
H. H. Barrett and
R. H. Seacat TRIMM: A Parallel Processor for Image
Reconstruction by Simulated Annealing 242
A. M. Andrew The Response-Time Constraint in Neural
Evolution . . . . . . . . . . . . . . . 254
R. J. Collins and
D. R. Jefferson An Artificial Neural Network
Representation for Artificial Organisms 259
S. Piramuthu Feature Construction for
Back-Propagation . . . . . . . . . . . . 264
R. Salomon Improved Convergence Rate of
Back-Propagation with Dynamic Adaption
of the Learning Rate . . . . . . . . . . 269
W. Schiffmann and
M. Joost and
R. Werner Performance Evaluation of Evolutionarily
Created Neural Network Topologies . . . 274
A. A. Vedenov and
M. V. Zurin and
E. B. Levchenko and
G. D. Myl'nikov and
A. N. Timashev and
A. Yu. Turygin Optical Image Preprocessing for Neural
Network Classifier Systems . . . . . . . 284
P. J. B. Hancock and
L. S. Smith GANNET: Genetic Design of a Neural Net
for Face Recognition . . . . . . . . . . 292
J. Heistermann The Application of a Genetic Approach as
an Algorithm for Neural Networks . . . . 297
K.-U. Hoffgen and
H. P. Siemon and
A. Ultsch Genetic Improvements of Feedforward Nets
for Approximating Functions . . . . . . 302
P. M. Todd and
G. F. Miller Exploring Adaptive Agency III:
Simulating the Evolution of Habituation
and Sensitization . . . . . . . . . . . 307
M. Scholz A Learning Strategy for Neural Networks
Based on a Modified Evolutionary
Strategy . . . . . . . . . . . . . . . . 314
S. Forrest and
A. S. Perelson Genetic Algorithms and the Immune System 320
B. Manderick Selectionist Categorization . . . . . . 326
A. Schachtner A Classifier System with Integrated
Genetic Operators . . . . . . . . . . . 331
M. Valenzuela-Rendon The Fuzzy Classifier System: Motivations
and First Results . . . . . . . . . . . 338
H. Bersini and
F. J. Varela Hints for Adaptive Problem Solving
Gleaned from Immune Networks . . . . . . 343
J. Decuyper and
D. Keymeulen A Reactive Robot Navigation System Based
on a Fluid Dynamics Metaphor . . . . . . 356
R. C. Paton and
H. S. Nwana and
M. J. R. Shave and
T. J. M. Bench-Capon and
S. Hughes Transfer of Natural Metaphors to
Parallel Problem Solving Applications 363
H.-M. Voigt and
J. Born and
I. Santibanez-Koref Modelling and Simulation of Distributed
Evolutionary Search Processes for
Function Optimization . . . . . . . . . 373
M. J. Mataric Parallel, Decentralized Spatial Mapping
for Robot Navigation and Path Planning 381
N. Adachi and
K. Matsuo Ecological Dynamics under Different
Selection Rules in Distributed and
Iterated Prisoner's Dilemma Games . . . 388
S. T. Barnard and
A. Bergman Adaptation in Signal Spaces . . . . . . 395
L. R. Lopez and
H. J. Caulfield A Principle of Minimum Complexity in
Evolution . . . . . . . . . . . . . . . 405
J. Paredis The Emergence of Data Structures from
Local Interactions . . . . . . . . . . . 410
J. Schull The View from the Adaptive Landscape . . 415
T. Boseniuk and
W. Ebeling Boltzmann-, Darwin-, and
Haeckel-Strategies in Optimization
Problems . . . . . . . . . . . . . . . . 430
C. de Groot and
D. Wurtz and
K. H. Hoffmann Optimizing Complex Problems by Nature's
Algorithms: Simulated Annealing and
Evolution Strategy --- A Comparative
Study . . . . . . . . . . . . . . . . . 445
F. Hoffmeister and
T. Back Genetic Algorithms and Evolution
Strategies --- Similarities and
Differences . . . . . . . . . . . . . . 455
P. Bock Building the Ultimate Machine: The
Emergence of Artificial Cognition . . . 472
E. C. R. Hehner What's Wrong With Formal Programming
Methods? . . . . . . . . . . . . . . . . 2
R. L. Probert Computer Science and Communications
Protocols: Research Relationships . . . 24
S. J. Smith Reaping the Benefits of Mass Production
with Massively Parallel Computing ---
Four Example Applications . . . . . . . 33
Y.-C. Hung and
G.-H. Chen On the Quickest Path Problem . . . . . . 44
V. Estivill-Castro and
D. Wood Practical Adaptive Sorting . . . . . . . 47
N. H. Bshouty Lower Bounds for Algebraic Computation
Trees of Functions with Finite Domains 55
J. Haralambides and
F. Makedon Approximation Algorithms for the
Bandwidth Minimization Problem for a
Large Class of Trees . . . . . . . . . . 66
M. A. Ouksel and
A. Yaagoub The Interpolation-Based Bintree and its
Application to Graphics . . . . . . . . 78
M. C. Carlisle and
E. L. Lloyd On the $k$-Coloring of Intervals . . . . 90
A. A. Kooshesh and
B. M. E. Moret Folding a Triangulated Simple Polygon:
Structural and Algorithmic Results . . . 102
T. W. Lai and
D. Wood A Relationship Between Self-Organizing
Lists and Binary Search Trees . . . . . 111
H. Cameron and
D. Wood How Costly Can Red-Black Trees Be? . . . 117
H. Cameron and
D. Wood Balance in AVL Trees . . . . . . . . . . 127
M. Cosnard and
A. G. Ferreira A Tight Lower Bound for Selection in
Sorted $ {X} + {Y} $ . . . . . . . . . . 134
C. Levcopoulos and
A. Lingas Greedy Triangulation Approximates the
Optimum and Can Be Implemented in Linear
Time in the Average Case . . . . . . . . 139
R. Raman Generating Random Graphs Efficiently . . 149
I. Rival and
S. Zhan Linear Extensions with Backtracking . . 161
J. Chen and
Y. Han Storing Shortest Paths for a Polyhedron 169
K. P. Tan and
T. C. Tan An Improved Join Dependency for
Efficient Constraint Checking . . . . . 182
J. Han On the Power of Query-Independent
Compilation . . . . . . . . . . . . . . 185
A. A. Toptsis Parallel Transitive Closure Computation
in Highly Scalable Multiprocessors . . . 197
B. Czejdo and
M. Taylor Methods and Tools for Integrating
Database Systems and Object-Oriented
Programming Systems . . . . . . . . . . 207
K. Wang and
L. Y. Yuan Incremental Database Design Revisited 219
D. L. Lee and
W. Y. P. Wong Partial Document Ranking by Heuristic
Methods . . . . . . . . . . . . . . . . 231
L. Yu and
S. L. Osborn Context Inheritance and Content
Inheritance in an Object-Oriented Data
Model . . . . . . . . . . . . . . . . . 240
B. D. Czejdo and
R. P. Tucci and
D. W. Embley Graphical Specification of Recursive
Queries . . . . . . . . . . . . . . . . 252
M. Nakanishi and
Y. Katsuyama and
M. Ito and
A. Hashimoto On Designing Relational Database Schemes
for Efficient Query Processing . . . . . 264
M. El-Toweissy and
N. El-Makky and
M. Abougabal and
S. Fouad The Mean Value Approach to Performance
Evaluation of Time-Stamp Ordering
Algorithms . . . . . . . . . . . . . . . 276
B. Yuwono and
D. L. Lee A Backend Text Retrieval Machine for
Signature-Based Document Ranking . . . . 288
P. Maheshwari Partitioning and Scheduling of Parallel
Functional Programs Using Complexity
Information . . . . . . . . . . . . . . 300
R. Mittal and
B. N. Jain and
R. K. Patney Subtree Availability in Binary Tree
Architectures . . . . . . . . . . . . . 312
I.-W. Chan and
D. K. Friesen An Optimal Parallel Algorithm for the
Vertical Segment Visibility Reporting
Problem . . . . . . . . . . . . . . . . 323
S.-C. Chau and
A. L. Liestman A Fault-Tolerant Binary Tree
Architecture . . . . . . . . . . . . . . 335
L.-H. Hsu and
J. J. J. Wang Unordered Tree Contraction . . . . . . . 347
C.-B. Yang and
R. C. T. Lee and
W.-T. Chen Conflict-Free Sorting Algorithms Under
Single-Channel and Multi-Channel
Broadcast Communication Models . . . . . 350
K. Qiu and
H. Meijer and
S. G. Akl Parallel Routing and Sorting on the
Pancake Network . . . . . . . . . . . . 360
E. S. Kirsch and
J. R. S. Blair Practical Parallel Algorithms for
Chordal Graphs . . . . . . . . . . . . . 372
L. Chen Logarithmic Time NC Algorithms for
Comparability Graphs and Circle Graphs 383
A. J. Boals and
A. K. Gupta and
J. A. Hashmi and
N. A. Sherwani Compact Hypercubes: Properties and
Recognition . . . . . . . . . . . . . . 395
Z. Liu and
J.-H. You Increasing Communication Bandwidth on
Hypercube . . . . . . . . . . . . . . . 403
D. Herman and
L. Trilling Programming a Parallel Sort Using
Distributed Procedure Calls . . . . . . 415
D. Krizanc A Note on Off-Line Permutation Routing
on a Mesh-Connected Processor Array . . 418
J. F. Myoupo A Fully-Pipelined Solutions Constructor
for Dynamic Programming Problems . . . . 421
M. Baumslag On the Fault-Tolerance of Quasi-Minimal
Cayley Networks . . . . . . . . . . . . 431
S. K. Das and
C. C.-Y. Chen and
G. Lewis and
S. Prasad Some Fast Parallel Algorithms for
Parentheses Matching . . . . . . . . . . 443
R. Lin and
S. Olariu A Simple Optimal Parallel Algorithm to
Solve the Lowest Common Ancestor Problem 455
S. Biswas and
A. Sanyal and
L. M. Tewari Extended Cycle Shrinking: A
Restructuring Method for Parallel
Compilation . . . . . . . . . . . . . . 462
J. B. Rosen and
G.-L. Xue Sequential and Distributed Algorithms
for the All Pairs Quickest Path Problem 471
A. Boals and
A. Gupta and
J. Hashmi and
N. Sherwani An Efficient Approximation Algorithm for
Hypercube Scheduling . . . . . . . . . . 474
S. Olariu and
M. Overstreet and
Z. Wen An Optimal Parallel Algorithm to
Reconstruct a Binary Tree from its
Traversals . . . . . . . . . . . . . . . 484
H. Y. Youn An Efficient Multiprocessor Architecture
for Image Processing in VLSI . . . . . . 496
P. K. Srimani Generalized Fault Tolerance Properties
of Star Graphs . . . . . . . . . . . . . 510
B. Gopinath and
A. K. Singh and
P. Uppaluru A Formal Description of the ICsup *
Model Parallel Computation . . . . . . . 520
S. P. Rana An Efficient Algorithm for Quiescence
Detection in a Distributed System . . . 532
C. M. Woodside and
S. Majumdar and
J. E. Neilson Interval Arithmetic for Computing
Performance Guarantees in Client-Server
Software . . . . . . . . . . . . . . . . 535
G. S. Alijani and
H. F. Wedde Enhanced Reliability in Scheduling
Critical Tasks for Hard Real-Time
Distributed Systems . . . . . . . . . . 547
R. Ammar and
P. Zhang A Design and Modeling Environment to
Develop Real-Time, Distributed Software
Systems . . . . . . . . . . . . . . . . 559
W. Zhou and
B. Molinari On the Management of Remote Procedure
Call Transactions . . . . . . . . . . . 571
L. M. Kirousis and
P. Spirakis and
P. Tsigas Simple Atomic Snapshots: A Linear
Complexity Solution with Unbounded
Time-Stamps . . . . . . . . . . . . . . 582
O. ZeinElDine and
M. El-Toweissy and
R. Mukkamala A Distributed Scheduling Algorithm for
Heterogeneous Real-Time Systems . . . . 588
M. Raynal A Distributed Solution to the $k$-out
of-$ {M} $ Resources Allocation Problem 599
H. F. Wedde and
D. C. Daniels and
D. Huizinga Efficient Distributed Resource
Scheduling for Adaptive Real-Time
Operation Support . . . . . . . . . . . 610
U. Bhattacharya and
S. Bhattacharya Mapping of Fault-Tolerant Permutations
in Omega Interconnection Network . . . . 628
A. B. Bulsari and
H. Saxen Artificial Neural Networks for
Predicting Silicon Content in Raw Iron
From Blast Furnaces . . . . . . . . . . 642
A. B. Bulsari and
B. Saxen and
H. Saxen A Chemical Reactor Selection Expert
System Created by Training an Artificial
Neural Network . . . . . . . . . . . . . 645
R. Hewett A Modeling Technique for Generating
Causal Explanations of Physical Systems 657
L. Yang and
S. Szpakowicz Planning in Conceptual Networks . . . . 669
P. Cerrito and
W. Karwowski and
Krzysztof Ostaszewski Empirical Study of the Meaning of the
Hedge ``VERY'' . . . . . . . . . . . . . 672
M. A. N. Abdallah Kernel Knowledge Versus Belt Knowledge
in Default Reasoning: a Logical Approach 675
E. Eberbach Neural Network Processing Elements as a
News Generation of ``Flip-Flops'' . . . 687
L. Y. Yuan and
J.-H. You and
C. Wang A Proof-Theoretic Framework for
Nonmonotonic Reasoning and Logic
Programming . . . . . . . . . . . . . . 699
L. Y. Yuan On Semantics, Syntactics and Fixpoints
of General Programs . . . . . . . . . . 709
A. Basu and
X. Li A Framework for Variable-Resolution
Vision . . . . . . . . . . . . . . . . . 721
V. Sundararajan and
H. N. Dholakia and
N. Parameswaran An RMS for Temporal Reasoning with
Abstraction . . . . . . . . . . . . . . 733
G. Wille The Information Industry Scenario in
Year 2000, Trends and Change of Focus,
for the IT Professional and for the
End-User . . . . . . . . . . . . . . . . 1
L. Chung Representation and Utilization of
Non-Functional Requirements for
Information System Design . . . . . . . 5
C. Cauvet and
C. Proix and
C. Rolland ALECSI: An Expert System for
Requirements Engineering . . . . . . . . 31
M. Fugini and
M. Guggino and
B. Pernici Reusing Requirements Through a Modeling
and Composition Support Tool . . . . . . 50
M. Ahlsen and
A. D'Atri and
P. Johannesson and
E. Laenens and
N. Leone and
P. Rullo and
P. Rossi and
F. Staes and
L. Tarantino and
L. Van Beirendonck and
others The KIWIS Knowledge Base Management
System . . . . . . . . . . . . . . . . . 79
M. E. Orlowska and
K. G. Jeffery A Functional Method of Data Processing
Based on Relational Algebra . . . . . . 98
G. Wiederhold and
S. Jajodia and
W. Litwin Dealing with Granularity of Time in
Temporal Databases . . . . . . . . . . . 124
J. Olaisen Information as a Strategic Resource: A
Question of Communication . . . . . . . 141
K. Smolander and
K. Lyytinen and
V.-P. Tahvanainen and
P. Marttiin MetaEdit --- A Flexible Graphical
Environment for Methodology Modelling 168
J. A. Gulla and
O. I. Lindland and
G. Willumsen PPP --- An Integrated CASE Environment 194
V. Seppanen and
M. Heikkinen and
R. Lintulampi SPADE --- Towards CASE Tools That can
Guide Design . . . . . . . . . . . . . . 222
D. Bitton and
J. C. Millman and
S. Torgersen DBE: An Expert Tool for Database Design 240
F. Adreit and
M. Bonjour EcrinsDesign --- A Graphical Editor for
Semantic Structures . . . . . . . . . . 264
J. Hillston and
A. L. Opdahl and
R. Pooley A Case Study Using the IMSE
Experimentation Tool . . . . . . . . . . 284
P. McBrien and
M. Niezette and
D. Pantazis and
A. H. Seltveit and
U. Sundin and
B. Theodoulidis and
G. Tziallas and
R. Wohed A Rule Language to Capture and Model
Business Policy Specifications . . . . . 307
J. Krogstie and
P. McBrien and
R. Owens and
A. H. Seltveit Information Systems Development Using a
Combination of Process and Rule Based
Approaches . . . . . . . . . . . . . . . 319
S. Jarzabek and
K. Tham Towards Automating Software Maintenance 336
C. Liu Software Process Planning and Execution:
Coupling vs. Integration . . . . . . . . 356
R. Conradi and
C. C. Malm Cooperating Transactions and Workspaces
in EPOS: Design and Preliminary
Implementation . . . . . . . . . . . . . 375
K. Kalman Implementation and Critique of an
Algorithm which Maps a Relational
Database to a Conceptual Model . . . . . 393
B. Wangler Attribute Abstraction . . . . . . . . . 416
J. L. G. Dietz The Essential System Model . . . . . . . 441
S. Papahristos and
W. A. Gray Federated CASE Environment . . . . . . . 461
A. Kieback and
J. Niemeier An Organizational Information Systems
Enhancement Advice Unit (OISEAU) . . . . 479
T. F. Verhoef and
A. H. M. ter Hofstede and
G. M. Wijers Structuring Modelling Knowledge for CASE
Shells . . . . . . . . . . . . . . . . . 502
V. Wuwongse and
J. Ma An Object-Oriented Approach to Model
Management . . . . . . . . . . . . . . . 525
A. Oelmann Representing a System Specification with
a Temporal Dimension in an
Object-Oriented Language . . . . . . . . 540
O. De Troyer The OO-Binary Relationship Model: A
Truly Object Oriented Conceptual Model 561
B. Nilsson Organisation's IT Needs in the Next
Decade --- The Swedish Vision . . . . . 579
M. C. Curtis and
V. J. D. Sivess Modelling the Temporal Summation of
Neural Membranes Using the Ada Language 2
T. Elrad and
V. Winans The Use of Ada in Reactive Systems: A
$3$-Dimensional Model . . . . . . . . . 20
F. A. Maymir-Ducharme Ada 9X Real-Time Scheduling Alternatives 37
S. Bjornson Information Engineering for Systems in
Ada . . . . . . . . . . . . . . . . . . 50
C. T. Tsalidis and
A. E. Hatzimanikatis AFADA, a Measurement Tool for Ada . . . 65
T. Curley An Approach To Benchmarking Ada
Compilation Systems . . . . . . . . . . 87
J. Wolff von Gudenberg Modelling SIMD --- Type Parallel
Arithmetic Operations in Ada . . . . . . 110
J. Cheng and
K. Ushijima Analyzing Ada Tasking Deadlocks and
Livelocks Using Extended Petri Nets . . 125
L. Lundberg A Coprocessor for High Performance
Multiprocessor Ada Tasking . . . . . . . 147
K. M. Gutzmann and
D. L. Remkes and
J. L. Ragsdale Software Project Activity Network for
Managing the Development and Testing
Process . . . . . . . . . . . . . . . . 168
A. Welz Ada in Safety Critical Applications . . 193
J. Willain and
P. Baesens and
J. Sanzot and
S. van Vlierberghe Real-Time Electronic Funds Transfer and
Ada . . . . . . . . . . . . . . . . . . 199
J. R. Larre and
N. Alfaro and
J. J. Galan and
J. Garbajosa Introducing HOOD into Software Process
Modelling Based Environments . . . . . . 212
A. Delis and
W. M. Thomas Design Assessment of Ada Systems Using
Static Analysis . . . . . . . . . . . . 227
P. Soupos and
S. Goutas Using Ada to Implement the Transaction
Mechanism of a Distributed
Object-Oriented DBMS . . . . . . . . . . 252
U. Baumgarten Distributed Systems and Ada --- Current
Projects and Approaches Comparative
Study's Results . . . . . . . . . . . . 260
D. C. Levy and
M. C. Randelhoff and
J. L. Tokar Reconfigurable Ada Distributed Control
System Software . . . . . . . . . . . . 279
N. Badaro and
Th. Moineau ROSE-Ada: a Method and a Tool to Help
Reuse of Ada Codes . . . . . . . . . . . 304
T. Syms and
C. L. Braun Software Reuse: Customer vs. Contractor
Point-Counterpoint . . . . . . . . . . . 326
A. Rosskopf Reusable Input/Output Packages for Ada
Avionic Applications . . . . . . . . . . 338
J. L. Fernandez and
J. A. de la Puente Constructing a Pilot Library of
Components for Avionic Systems . . . . . 362
D. Guaspari Formally Specifying the Logic of an
Automatic Guidance Controller . . . . . 372
C. Colombini and
A. della Torre and
R. Palotti Ada as High Level Language for Real-Time
Systems Exploiting RDBMS Techniques . . 384
B. Gilbert and
M. Taylor and
G. Bek Experience Developing two Ada
Applications for Embedded Real-Time
Systems Using Different Software
Processes . . . . . . . . . . . . . . . 394
J.-M. Lippens and
J. Arnol Testing and Integrating a Large Embedded
Real-Time System . . . . . . . . . . . . 404
M. Held On the Computational Geometry of Pocket
Machining . . . . . . . . . . . . . . . 3
M. Bidoit and
H.-J. Kreowski and
P. Lescanne and
F. Orejas and
D. Sannella Algebraic System Specification and
Development: A Survey and Annotated
Bibliography . . . . . . . . . . . . . . 1
M. Bidoit and
H.-J. Kreowski and
P. Lescanne and
F. Orejas and
D. Sannella Algebraic System Specification and
Development: Basic Foundations . . . . . 7
M. Bidoit and
H.-J. Kreowski and
P. Lescanne and
F. Orejas and
D. Sannella Algebraic System Specification and
Development Models . . . . . . . . . . . 15
M. Bidoit and
H.-J. Kreowski and
P. Lescanne and
F. Orejas and
D. Sannella Algebraic System Specification and
Development Concepts . . . . . . . . . . 25
M. Bidoit and
H.-J. Kreowski and
P. Lescanne and
F. Orejas and
D. Sannella Algebraic System Specification and
Development: Support Tools . . . . . . . 35
M. Bidoit and
H.-J. Kreowski and
P. Lescanne and
F. Orejas and
D. Sannella Algebraic System Specification and
Development: Applications . . . . . . . 49
G. Mints and
E. Tyugu The Programming System PRIZ . . . . . . 1
G. Mints and
J. M. Smith and
E. Tyugu Type-theoretical Semantics of Some
Declarative Languages . . . . . . . . . 18
T. Tammet Using Resolution for Deciding Solvable
Classes and Building Finite Models . . . 33
M. Meriste and
J. Penjam Toward Knowledge-based Specifications of
Languages . . . . . . . . . . . . . . . 65
R. Freivalds Inductive Inference of Recursive
Functions: Qualitative Theory . . . . . 77
R. Freivalds and
J. Barzdins and
K. Podnieks Inductive Inference of Recursive
Functions: Complexity Bounds . . . . . . 111
A. Brazma Inductive Synthesis of Dot Expressions 156
E. Kinber Some Models of Inductive Syntactical
Synthesis from Sample Computations . . . 213
G. Barzdins Inductive Synthesis of Term Rewriting
Systems . . . . . . . . . . . . . . . . 253
A. Auzins and
J. Barzdins and
J. Bicevskis and
K. Cerans and
A. Kalnins Automatic Construction of Test Sets:
Theoretical Approach . . . . . . . . . . 286
J. Borzovs and
A. Kalnins and
I. Medvedis Automatic Construction of Test Sets:
Practical Approach . . . . . . . . . . . 360
H. Pranevitchius Aggregate Approach for Specification,
Validation, Simulation and
Implementation of Computer Network
Protocols . . . . . . . . . . . . . . . 433
K. Gecas A Compositional Proof System for
Distributed Programs . . . . . . . . . . 478
R. Pliuskevicius Investigation of Finitary Calculus for a
Discrete Linear Time Logic by means of
Infinitary Calculus . . . . . . . . . . 504
M. Auguston RIGAL --- a Programming Language for
Compiler Writing . . . . . . . . . . . . 529
R. Freivalds Complexity of Probabilistic Versus
Deterministic Automata . . . . . . . . . 565
Henri Bal Languages for Parallel Programming . . . 3
Kjell Bratbergsengen Relational Algebra Operations . . . . . 24
Filippo Cacace and
Stefano Ceri and
Maurice Houtsma An Overview of Parallel Strategies for
Transitive Closure on Algebraic Machines 44
Hector Garcia-Molina and
Robert Abbott and
Christopher Clifton and
Carl Staelin and
Kenneth Salem Data Management with Massive Memory: A
Summary . . . . . . . . . . . . . . . . 63
Theo Harder An Approach to Implement Dynamically
Defined Complex Objects . . . . . . . . 71
Anthony Hey Experience with MIMD Message-Passing
Systems: Towards General Purpose
Parallel Computing . . . . . . . . . . . 99
Simon Lavington Parallel Associative Processing for
Knowledge Bases . . . . . . . . . . . . 112
Suresh Patel Performance Estimates of a Join . . . . 124
Paul Watson and
Paul Townsend The EDS Parallel Relational Database
System . . . . . . . . . . . . . . . . . 149
Peter Apers and
Bob Hertzberger and
Ben Hulshof and
Hans Oerlemans and
Martin Kersten PRISMA, a Platform for Experiments with
Parallelism . . . . . . . . . . . . . . 169
Peter Apers and
Bob Hertzberger and
Ben Hulshof The PRISMA Experiment . . . . . . . . . 181
Marcel Beemster Back-End Aspects of a Portable POOL-X
Implementation . . . . . . . . . . . . . 193
Carel van den Berg and
Martin Kersten Logging and Recovery in PRISMA . . . . . 229
Paul Grefen and
Jan Flokstra and
Peter Apers Parallel Handling of Integrity
Constraints . . . . . . . . . . . . . . 242
Martin Kersten and
Satish Shair-Ali and
Carel van den Berg Performance Analysis of a Dynamic Query
Processing Scheme . . . . . . . . . . . 259
Henk Muller Evaluation of a Communication
Architecture by Means of Simulation . . 275
Jan Willem Spee A Parallel Implementation of the EQUIP
Expert System . . . . . . . . . . . . . 294
Juul van der Spek POOL-X and its Implementation . . . . . 309
Chengzheng Sun and
Bob Hertzberger Automatic Recovery of a Parallel Stable
File System . . . . . . . . . . . . . . 345
Nanda Verbrugge Duplicates and Translation of Nested SQL
Queries into XRA . . . . . . . . . . . . 354
Marnix Vlot The POOMA Architecture . . . . . . . . . 365
Rogier Wester and
Ben Hulshof The POOMA Operating System . . . . . . . 396
Annita Wilschut and
Peter Apers and
Jan Flokstra Parallel Query Execution in PRISMA/DB 424
R. Manthey Declarative Languages --- Paradigm of
the Past or Challenge of the Future? . . 1
H. Ait-Kaci A Glimpse of Paradise . . . . . . . . . 17
A. Formica and
M. Missikoff and
S. Vazzana An Object-Oriented Data Model for
Artificial Intelligence Applications . . 26
H. Ait-Kaci An Overview of LIFE . . . . . . . . . . 42
R. Hull and
D. Jacobs On the Semantics of Rules in Database
Programming Languages . . . . . . . . . 59
S. K. Lellahi and
N. Spyratos Towards a Categorical Data Model
Supporting Structured Objects and
Inheritance . . . . . . . . . . . . . . 86
F. Matthes and
A. Ohori and
J. W. Schmidt Typing Schemes for Objects with Locality 106
S. Ceri and
F. Cacace and
L. Tanca Object Orientation and Logic Programming
for Databases: A Season's Flirt or
Long-Term Marriage? . . . . . . . . . . 124
G. Gottlob and
G. Kappel and
M. Schrefl Semantics of Object-Oriented Data Models
--- The Evolving Algebra Approach . . . 144
B. Thalheim Extending the Entity-Relationship Model
for a High-Level, Theory-Based Database
Design . . . . . . . . . . . . . . . . . 161
F. Matthes and
J. W. Schmidt Towards Database Application Systems:
Types, Kinds and Other Open Invitations 185
J. Zlatuska Modelling Inheritance in a Strongly
Typed Functional Model . . . . . . . . . 212
M. Atkinson and
P. Richard and
P. Trinder Bulk Types for Large Scale Programming 228
A. Pirotte and
D. Roelants and
E. Zimanyi Controlled Generation of Intensional
Answers . . . . . . . . . . . . . . . . 251
J. Eder and
A. Rudloff and
F. Matthes and
J. W. Schmidt Data Construction with Recursive Set
Expressions . . . . . . . . . . . . . . 271
P. Atzeni and
L. Tanca The LOGIDATA+ Model and Language . . . . 294
D. Stemple and
T. Sheard A Recursive Base for Database
Programming Primitives . . . . . . . . . 311
S. Alagic Toward Multiparadigm Database Interfaces 333
P. Atzeni and
R. Torlone Updating Datalog Databases . . . . . . . 347
L. Kalinichenko SYNTHESIS: Towards a Query Facility for
Generalized Information Resources . . . 363
A. V. Zamulin and
V. A. Kositov and
G. A. Kucherov and
E. V. Pak and
V. D. Ryshkov The Database Programming Language
Atlant: Principal Features and
Implementation Techniques . . . . . . . 385
K. Subieta LOQIS: The Object-Oriented Database
Programming System . . . . . . . . . . . 403
I. Burdonov and
V. Ivannikov and
G. Kopytov and
A. Kosachev and
S. Kuznetsov The CLOS Project: Towards an
Object-Oriented Environment for
Application Development . . . . . . . . 422
R. Kirkova and
M. Ikonomova and
E. Dencheva The HYTECH Project: IP Tools Based on
Hypertext Technology . . . . . . . . . . 428
V. Kolinko and
A. Mendelev and
S. Shevchenko VISICOM: A Visual Interface to Databases 435
V. N. Red'ko and
I. A. Basarab and
A. I. Solodovnic The ADIS Project on ADaptive Information
Systems: Concepts and Language
Technology . . . . . . . . . . . . . . . 437
E. Zinovjev and
A. Strecalov and
O. Rogova ISTSPN: Integrated Software Tool
Supporting Petri Nets . . . . . . . . . 440
V. Zubenko and
A. Protasov The FOLI Project: Towards an Artificial
Intelligence Language . . . . . . . . . 441
D. Chereshkin and
M. Tsalenko Informatization and Restructuring of
Soviet Society . . . . . . . . . . . . . 443
Th. Johnsson Parallel Evaluation of Functional
Programs: The <v, G>-Machine Approach . . 1
Pilar de la Torre and
C. P. Kruskal Towards a Single Model of Efficient
Computation in Real Parallel Machines 6
P. C. Treleaven Neural Computing and the GALATEA Project 25
H. H. J. Hum and
G. R. Gao A Novel High-Speed Memory Organization
for Fine-Grain Multi-Thread Computing 34
K. G. Langendoen and
H. L. Muller and
L. O. Hertzberger Evaluation of Futurebus Hierarchical
Caching . . . . . . . . . . . . . . . . 52
J. M. Filloque and
E. Gautrin and
B. Pottier Efficient Global Computations on a
Processor Network with Programmable
Logic . . . . . . . . . . . . . . . . . 69
P. Hoogvorst and
R. Keryell and
Ph. Matherat and
N. Paris POMP or How to Design a Massively
Parallel Machine with Small Developments 83
Jonas Vasell and
Jesper Vasell The Function Processor: An Architecture
for Efficient Execution of Recursive
Functions . . . . . . . . . . . . . . . 101
R. Milikowski and
W. G. Vree The G-Line: A Distributed Processor for
Graph Reduction . . . . . . . . . . . . 119
G. Tel and
F. Mattern The Derivation of Distributed
Termination Detection Algorithms from
Garbage Collection Schemes . . . . . . . 137
J. M. Piquer Indirect Reference Counting: A
Distributed Garbage Collection Algorithm 150
J. H. M. Korst and
E. H. L. Aarts and
J. K. Lenstra and
J. Wessels Periodic Multiprocessor Scheduling . . . 166
M. Baumslag and
M. C. Heydemann and
J. Opatrny and
D. Sotteau Embeddings of Shuffle-Like Graphs in
Hypercubes . . . . . . . . . . . . . . . 179
V. Van Dongen Mapping Uniform Recurrences onto Small
Size Arrays . . . . . . . . . . . . . . 191
P. Ferianc and
O. Sykora Area Complexity of Multilective Merging 209
X. Zhong and
S. Rajopadhye Deriving Fully Efficient Systolic Arrays
by Quasi-Linear Allocation Functions . . 219
C. Mongenet Affine Timings for Systems of Affine
Recurrence Equations . . . . . . . . . . 236
I. Parberry On the Computational Complexity of
Optimal Sorting Network Verification . . 252
Sajal K. Das and
Horng Wen-Bing Managing a Parallel Heap Efficiently . . 270
C. Alvarez and
J. L. Balcazar and
J. Gabarro and
M. Santha Parallel Complexity in the Design and
Analysis of Concurrent Systems . . . . . 288
T. Hagerup and
A. Schmitt and
H. Seidl FORK: A High-Level Language for PRAMs 304
A. R. Hurson and
B. Jin and
S. H. Pakzad Neural Network-Based Decision Making for
Large Incomplete Databases . . . . . . . 321
A. Louri An Optical Content-Addressable Parallel
Processor for Fast Searching and
Retrieving . . . . . . . . . . . . . . . 338
G. R. Gao and
H. H. J. Hum and
J.-M. Monti Towards an Efficient Hybrid Dataflow
Architecture Model . . . . . . . . . . . 355
R. Govindarajan and
Yu Sheng Data Flow Implementation of Generalized
Guarded Commands . . . . . . . . . . . . 372
J. Duato On the Design of Deadlock-Free Adaptive
Routing Algorithms for Multicomputers:
Design Methodologies . . . . . . . . . . 390
H. Ilmberger and
S. Thurmel A Toolkit for Debugging Parallel Lisp
Programs . . . . . . . . . . . . . . . . 406
J. Misra Loosely-Coupled Processes . . . . . . . 1
J. W. de Bakker and
E. P. de Vink Rendezvous with Metric Semantics . . . . 27
R. Janicki and
M. Koutny Invariants and Paradigms of Concurrency
Theory . . . . . . . . . . . . . . . . . 59
L. M. Alonso and
R. Pena Acceptance Automata: A Framework for
Specifying and Verifying TCSP Parallel
Systems . . . . . . . . . . . . . . . . 75
J. Fanchon and
D. Millot Models for Dynamically Placed Concurrent
Processes . . . . . . . . . . . . . . . 92
Y. Sami and
G. Vidal-Naquet Formalisation of the Behavior of Actors
by Colored Petri Nets and Some
Applications . . . . . . . . . . . . . . 110
Ambuj K. Singh Program Refinement in Fair Transition
Systems . . . . . . . . . . . . . . . . 128
J. T. Yantchev Communication Abstraction and Refinement 148
L. Bouge On the Semantics of Languages for
Massively Parallel SIMD Architectures 166
J. Hooman A Denotational Real-Time Semantics for
Shared Processors . . . . . . . . . . . 184
E. G. J. M. H. Nocker and
J. E. W. Smetsers and
M. C. J. D. van Eekelen and
M. J. Plasmeijer Concurrent Clean . . . . . . . . . . . . 202
A. van Delft The Scriptic Programming Language . . . 220
S. Haridi and
C. Palamidessi Structural Operational Semantics for
Kernel Andorra Prolog . . . . . . . . . 238
S. Jagannathan Customization of First-Class
Tuple-Spaces in a Higher-Order Language 254
M. Factor A Formal Specification of the Process
Trellis . . . . . . . . . . . . . . . . 277
C. Autant and
Z. Belmesk and
Ph. Schnoebelen Strong Bisimilarity on Nets Revisited 295
J. Magee and
N. Dulay A Configuration Approach to Parallel
Programming . . . . . . . . . . . . . . 313
J.-L. Gaudiot and
Lin Chih-Ming Chaotic Linear System Solvers in a
Variable-Grain Data-Driven
Multiprocessor System . . . . . . . . . 331
M. Waite and
B. Giddings and
S. Lavington Parallel Associative Combinator
Evaluation . . . . . . . . . . . . . . . 349
C. Hankin Static Analysis of Term Graph Rewriting
Systems . . . . . . . . . . . . . . . . 367
J. Briat and
M. Favre and
C. Geyer and
J. Chassin de Kergommeaux Reconfigurable, Distributed-Memory
Multiprocessor . . . . . . . . . . . . . 385
A. Beaumont and
S. Muthu Raman and
P. Szeredi and
D. H. D. Warren Flexible Scheduling of OR-Parallelism in
Aurora: The Bristol Scheduler . . . . . 403
A. Veron and
Xu Jiyang and
S. A. Delgado-Rannauro and
K. Schuerman Virtual Memory Support for OR-Parallel
Logic Programming Systems . . . . . . . 421
P. Szeredi and
R. Yang and
M. Carlsson Interfacing Engines and Schedulers in
OR-Parallel Prolog Systems . . . . . . . 439
Zhiyi Hwang and
Shouren Hu and
Chengzheng Sun and
Yaoqing Gao Reduction of Code Space in Parallel
Logic Programming Systems . . . . . . . 454
S. Fujita and
M. Yamashita and
T. Ae Search Level Parallel Processing of
Production Systems . . . . . . . . . . . 471
Joseph Manning Computational Complexity of Geometric
Symmetry Detection in Graphs . . . . . . 1
Kunwarjit S. Bagga and
Frank W. Owens Low Dimensional Middle Cubes Are
Hamiltonian . . . . . . . . . . . . . . 8
Ewa Kubicka and
Grzegorz Kubicki and
Dionisios Kountanis Approximation Algorithms for the
Chromatic Sum . . . . . . . . . . . . . 15
Thomas J. Sager and
Lin Shi-Jen A Color-Exchange Algorithm for Exact
Graph Coloring . . . . . . . . . . . . . 22
Garry L. Johns and
Tai-Chi Lee S-Distance in Trees . . . . . . . . . . 29
Mo Zhugou and
Kenneth Williams Algorithms on Block-Complete Graphs . . 34
Stuart H. Rubin Heuristic-Based Learning . . . . . . . . 41
Ben Pinkowski A Template-based Approach for
Recognition of Intermittent Sounds . . . 51
Tzeng Chun-Hung A Mathematical Model of Uncertain
Information . . . . . . . . . . . . . . 58
Gary Gold A Word to Phoneme Translator . . . . . . 65
D. Christine Georgakis and
Martha Evens and
Frank Naeymi-Rad and
David A. Trace Performance Evaluation of Medical Expert
Systems . . . . . . . . . . . . . . . . 70
Hee Lee Yoon and
Martha Evens and
Joel A. Michael and
Allen A. Rovick Spelling Correction for an Intelligent
Tutoring System . . . . . . . . . . . . 77
Paul Buchheit An Informational Network for a Natural
Talking System . . . . . . . . . . . . . 84
Sanjiv K. Bhatia and
Jitender S. Deogun and
Vijay V. Raghavan Formation of Categories in Document
Classification Systems . . . . . . . . . 91
Vipa Ongwisesphaiboon and
Ilene Burnstein and
Martha Evens and
Anjali Puri and
Martin E. Ginn An Expert System for Creativity
Management . . . . . . . . . . . . . . . 98
Greg Makowski A More Flexible Method for Recognizing
Signals Using Back Propagation:
Piecewise Linear Regression Vectors . . 105
Gerald Leonard Gordon A Cooperative Algorithm for the Dynamic
Stereo Problem . . . . . . . . . . . . . 111
Richard E. Haskell and
Ali Noui-Mehidi Design of Hierarchical Classifiers . . . 118
Roy F. Keller and
R. Mark Meyer and
Thomas L. Seevers Designing and Implementing Parallel
Constructs . . . . . . . . . . . . . . . 125
Ashok Samal Performance of Parallel Consistency
Algorithms . . . . . . . . . . . . . . . 132
Mokhtar A. Aboelaze and
Catherine E. Houstis Delay Analysis of the $N$-Cube Network 139
Kazem U. Ahmed and
Yeh Der-Yun A Note on Conway's Parallel Sorting
Algorithm . . . . . . . . . . . . . . . 147
Diane T. Rover and
G. M. Prabhu and
Charles T. Wright Visualization of Program Performance on
Concurrent Computers . . . . . . . . . . 154
Robin W. Dawes Minimum Odd Neighbourhood Covers for
Trees . . . . . . . . . . . . . . . . . 161
Yehoshua Perl and
Ashish Mehta Cascading LZW Algorithm with Huffman
Coding: A Variable to Variable Length
Compression Algorithm . . . . . . . . . 170
John McAlpin and
Christos Nikolopoulos Dendrograms and Irreducible Prefix Codes 179
Michael S. Wainer Massively Parallel Implementations of
Adaptively Subdividing Fractal
Generating Algorithms with Parameter
Extensions . . . . . . . . . . . . . . . 185
Zheng Si-Qing A Simple and Powerful Representation of
Binary Search Trees . . . . . . . . . . 192
Spyros S. Magliveras and
Nasir D. Memon Random Permutations from Logarithmic
Signatures . . . . . . . . . . . . . . . 199
Paruvachi V. R. Raja Novel Design Techniques for RNS Systolic
VLSI Arrays . . . . . . . . . . . . . . 206
K. L. D. Gunawardena A Compound Decision Theory Approach to
Digital Signal Reconstruction . . . . . 213
Sarma R. Vishnubhotla Real-time Parameter Control in Space
Vehicles: A Parallel Architecture and
the Protocols . . . . . . . . . . . . . 220
Sarma R. Vishnubhotla A Microinstruction Based Procedure to
Diagnose Hardware Failures in Industrial
Robots . . . . . . . . . . . . . . . . . 227
Harbans Kaur and
James Brown Grier and
Graham Campbell A Specification and Verification Tool
for Communication Protocols . . . . . . 234
Phil G. Richards and
Chao Meng-Chun Structured On-Line Directory and File
Organization . . . . . . . . . . . . . . 242
Farshad Fotouhi and
Carlos E. Galarce Genetic Algorithms and the Search for
Optimal Database Index Selection . . . . 249
Hossein Saiedian An Object-Based Approach to the
Specification of Office Entities . . . . 256
Pin-Ngern Sumali and
Robert Strutz and
Martha Evens Lexical Acquisition for Lexical
Databases . . . . . . . . . . . . . . . 264
James N. Lyness and
W. Newman A Search for Good Lattice Rules Based on
the Reciprocal Lattice Generator Matrix 271
Alan Genz An Adaptive Numerical Integration
Algorithm for Simplices . . . . . . . . 279
L. Magnus Ewerbring and
Franklin T. Luk The HK Singular Value Decomposition of
Rank Deficient Matrix Triplets . . . . . 286
Ricolindo Carino and
Elise de Doncker and
Ian Robinson Approximate Integration Using Iterated
Levin Transformations . . . . . . . . . 293
Thomas Sprague Recent Advances in Shape Preserving
Piecewise Cubic Interpolation . . . . . 300
M. Ancona and
K. S. Bagga and
E. Bruzzone and
L. De Floriani and
J. S. Deogun Structured Graph Models: An Efficient
Tool for VLSI Design . . . . . . . . . . 307
Youssef Saab and
Vasant Rao A Stochastic Algorithm for Circuit
Bi-Partitioning . . . . . . . . . . . . 313
Dee Parks An Optimal Channel-Routing Algorithm for
a Restricted Class of Multi-Terminal
Nets . . . . . . . . . . . . . . . . . . 322
F. D. Lewis and
N. Van Cleave Correct and Provably Efficient Methods
for Rectilinear Steiner Spanning Tree
Generation . . . . . . . . . . . . . . . 329
Ghasem S. Alijani and
Horst F. Wedde A Three-Phase Task Scheduling Scheme in
A Hard Real-Time Distributed Environment 336
Sub Ramakrishnan A Broadcast Protocol: Functional
Properties and Specification . . . . . . 343
Mohamed El-Ruby and
James Kenevan and
Robert Carlson and
Khalid Khalil Leader Election in Distributed Computing
Systems . . . . . . . . . . . . . . . . 350
Guy W. Zimmerman and
Abdol-Hossein Esfahanian A New Approach to System-Level
Fault-Tolerance in Message-Passing
MultiComputers . . . . . . . . . . . . . 357
Mike Beaven and
Ryan Stansifer and
Dan Wetklow A Functional Language with Classes . . . 364
Steve J. Chapin and
Ryan Stansifer Using ML as a Command Language . . . . . 371
Natasha Ma Huei-Ning and
Martha Evens and
David A. Trace and
Frank Naeymi-Rad An Interactive System for Generating
Hospital Progress Notes . . . . . . . . 378
Mateen M. Rizki and
Louis A. Tamburino and
Michael A. Zmuda Biological Evolution as a Paradigm for
Performance Driven Design Processes . . 385
David W. Elrod and
Gerry M. Maggiora and
Robert G. Trenary Predicting Chemical Reactions with a
Neural Network . . . . . . . . . . . . . 392
Mateen M. Rizki and
Chen Jong Mutation and Recombination Effects on
the Adaptability of Sexual and Asexual
Organisms . . . . . . . . . . . . . . . 399
William P. Coleman and
David P. Sanford and
Andrea De Gaetano and
Fred Geisler Logical Structure of Neurobiological
Information Processing . . . . . . . . . 406
Gretchen Vogel and
Diane Rover and
Charles Wright and
Gurpur Prabhu Development of an Experimental Setup for
Studying Parallel Processing . . . . . . 412
Roger Yim and
Hu Gongzhu Compiler Course with a Semi-Challenging
Project . . . . . . . . . . . . . . . . 419
Bill E. Swafford Report on a PC Based System Designed to
Enhance the Teaching of IBM 370 Assembly
Language . . . . . . . . . . . . . . . . 426
Dean Sanders Teaching the Spirit of Computational
Science . . . . . . . . . . . . . . . . 433
G. D. Cohen Covering Radius and Writing on Memories 1
J. Heintz and
T. Krick and
M.-F. Roy and
P. Solerno Geometric Problems Solvable in Single
Exponential Time . . . . . . . . . . . . 11
J. Simonis A Description of the $ [16, 7, 6] $
Codes . . . . . . . . . . . . . . . . . 24
K. Yamaguchi and
H. Imai Periodic Sequences for Absolute Type
Shaft Encoders . . . . . . . . . . . . . 36
G. Sinaki Error-Coded Algorithms for On-Line
Arithmetic . . . . . . . . . . . . . . . 46
Y. Saitoh and
H. Imai Constructions of Codes Correcting Burst
Asymmetric Errors . . . . . . . . . . . 59
T. N. Ahn and
K. Sakaniwa and
T. R. N. Rao A Construction Method for $m$-ary
Unidirectional Error Control Codes . . . 71
L. Peizhong and
S. Guowen Feasible Calculation of the Generator
for Combined LFSR Sequences . . . . . . 86
I. Vajda and
T. Nemetz Substitution of Characters in $q$-ary
$m$-Sequences . . . . . . . . . . . . . 96
N. Suehiro Pseudo-Polyphase Orthogonal Sequence
Sets with Good Cross-Correlation
Property . . . . . . . . . . . . . . . . 106
S. Matsufuji and
K. Imamura Real-Valued Bent Function and Its
Application to the Design of Balanced
Quadriphase Sequences with Optimal
Correlation Properties . . . . . . . . . 113
G. Schnabl and
M. Bossert Coded Modulation with Generalized
Multiple Concatenation of Block Codes 122
R. Kohno and
Ch. Yim and
H. Imai Trellis Coded Modulation Based on
Time-Varying Mapping and Encoders for
Utilizing a Channel Intersymbol
Interference . . . . . . . . . . . . . . 132
N. M. Nikityuk Use of the Algebraic Coding Theory in
Nuclear Electronics . . . . . . . . . . 144
J. Abbott Some Ideas about Fault-Tolerant Chinese
Remaindering . . . . . . . . . . . . . . 155
J. R. Coma On a Categorial Isomorphism between a
Class of Completely Regular Codes and a
Class of Distance Regular Graphs . . . . 164
J. Heintz and
M.-F. Roy and
P. Solerno Single Exponential Path Finding in
Semialgebraic Sets. Part I: The Case of
a Regular Bounded Hypersurface . . . . . 180
M. E. Alonso and
T. Mora and
M. Raimondo On the Complexity of Algebraic Power
Series . . . . . . . . . . . . . . . . . 197
M. E. Alonso and
T. Mora and
M. Raimondo Local Decomposition Algorithms . . . . . 208
L. Langemyr An Asymptotically Fast Probabilistic
Algorithm for Computing Polynomial GCD's
over an Algebraic Number Field . . . . . 222
B. Mourrain Some Algebra with Formal Matrices . . . 234
M. Kalkbrener Implicitization of Rational Parametric
Curves and Surfaces . . . . . . . . . . 249
Ph. Glesser and
M. Mignotte An Inequality about Irreducible Factors
of Integer Polynomials (II) . . . . . . 260
Pr. L. Beneteau The Symplectic Trilinear Mappings: An
Algorithmic Approach of the
Classification; Case of the Field $
\mbox {GF(3)}^\dagger $ . . . . . . . . 267
S. Sakata A Gröbner Basis and a Minimal Polynomial
Set of a Finite $n$D Array . . . . . . . 280
L. Robbiano Bounds for Degrees and Number of
Elements in Gröbner Bases . . . . . . . . 292
F. Ollivier Standard Bases of Differential Ideals 304
M. Giusti Complexity of Standard Bases in
Projective Dimension Zero II . . . . . . 322
M. Diab Systolic Architectures for
Multiplication over Finite Field $ {\rm
GF}(2^m) $ . . . . . . . . . . . . . . . 329
W. Kuechlin PARSAC-2: A Parallel SAC-2 Based on
Threads . . . . . . . . . . . . . . . . 341
M. Morii and
Y. Takamatsu Exponentiation in Finite Fields Using
Dual Basis Multiplier . . . . . . . . . 354
G. Cooperman and
L. Finkelstein and
N. Sarawagi Applications of Cayley Graphs . . . . . 367
Y. Zheng and
T. Matsumoto and
H. Imai Duality between Two Cryptographic
Primitives . . . . . . . . . . . . . . . 379
Henk Obbink Systems Engineering Environments of
ATMOSPHERE . . . . . . . . . . . . . . . 1
Peter Gohner Building IPSE's by Combining
Heterogeneous CASE Tools . . . . . . . . 18
Gunter Merbeth On the Functional and Architectural
Integration of CASE Systems . . . . . . 31
Jonah Z. Lavi and
Michael Winokur Development of a Method Driven
CAS${}^2$E Tool . . . . . . . . . . . . 44
John N. Pocock VSF and its Relationship to Open Systems
and Standard Repositories . . . . . . . 53
Huw Oliver Adding Control Integration to PCTE . . . 69
Albert Alderson Meta-CASE Technology . . . . . . . . . . 81
Rainer Burchett Management Issues in Software
Development . . . . . . . . . . . . . . 92
Adolf Peter Brohl Standardization of Software Development
Environments . . . . . . . . . . . . . . 99
Lothar Kohler A Software Development Environment for
CIM Applications . . . . . . . . . . . . 109
Dieter Steinbauer A Repository and Other Tools in a
Commercial Development Center . . . . . 114
Johann Wagner Lessons Learned from DOMINO and GRAPES 130
Peter Hruschka Should CASE be Application Dependent? 143
Wolfgang Henhapl and
Stefan Kaes and
Gregor Snelting Utilizing Fifth Generation Technology in
Software Development Tools . . . . . . . 153
Dominique Clement and
Vincent Prunet and
Francis Montagnac Integrated Software Components: A
Paradigm for Control Integration . . . . 167
Dines Bjorner and
Soren Prehn Formal Methods in Software Development:
Requirements for a CASE . . . . . . . . 178
Manfred Nagl Modeling of Software Architectures:
Importance, Notions, Experiences . . . . 211
Jeff Kramer and
Anthony Finkelstein A Configurable Framework for Method and
Tool Integration . . . . . . . . . . . . 233
Watts S. Humphrey Recent Findings in Software Process
Maturity . . . . . . . . . . . . . . . . 258
Volker Gruhn Validation and Verification of Software
Process Models . . . . . . . . . . . . . 271
M. Gabbrielli and
G. Levi On the Semantics of Logic Programs
(Invited Lecture) . . . . . . . . . . . 1
Chen Hong and
Hsiang Jieh Logic Programming with Recurrence
Domains . . . . . . . . . . . . . . . . 20
A. Bucciarelli and
T. Ehrhard Extensional Embedding of a Strongly
Stable Model of PCF . . . . . . . . . . 35
C. Ernoult and
A. Mycroft Uniform Ideals and Strictness Analysis 47
V. Breazu-Tannen and
R. Subrahmanyam Logical and Computational Aspects of
Programming with Sets/Bags\slash Lists 60
A. Bouajjani and
J. C. Fernandez and
S. Graf and
C. Rodriguez and
J. Sifakis Safety for Branching Time Semantics . . 76
L. Fix and
N. Francez and
O. Grumberg Program Composition and Modular
Verification . . . . . . . . . . . . . . 93
R. Alur and
C. Courcoubetis and
D. Dill Model-checking for Probabilistic
Real-time Systems . . . . . . . . . . . 115
R. Cleaveland and
B. Steffen Computing Behavioural Relations,
Logically . . . . . . . . . . . . . . . 127
Y. Ben-Asher and
D. Peleg and
R. Ramaswami and
A. Schuster The Power of Reconfiguration . . . . . . 139
J.-D. Fouks General Resolution of Tseitin Formulas
is Hard . . . . . . . . . . . . . . . . 151
S. Kannan and
A. Yao Program Checkers for Probability
Generation . . . . . . . . . . . . . . . 163
J. Kaneps and
R. Freivalds Running Time to Recognize Nonregular
Languages by 2-Way Probabilistic
Automata . . . . . . . . . . . . . . . . 174
R. Casas and
J. Diaz and
C. Martinez Statistics on Random Trees (Invited
Lecture) . . . . . . . . . . . . . . . . 186
K. G. Larsen The Expressive Power of Implicit
Specifications . . . . . . . . . . . . . 204
Yi Wang CCS+Time = an Interleaving Model for
Real Time Systems . . . . . . . . . . . 217
V. Diekert and
E. Ochmanski and
K. Reinhardt On Confluent
Semi-Commutations-Decidability and
Complexity Results . . . . . . . . . . . 229
G. Duchamp and
D. Krob Lazard's Factorizations of Free
Partially Commutative Monoids . . . . . 242
P. Gastin and
A. Petit and
W. Zielonka A Kleene Theorem for Infinite Trace
Languages . . . . . . . . . . . . . . . 254
N. Dershowitz Canonical Sets of Horn Clauses . . . . . 267
K. Madlener and
P. Narendran and
F. Otto A Specialized Completion Procedure for
Monadic String-Rewriting Systems
Presenting Groups . . . . . . . . . . . 279
P.-L. Curien and
R. Di Cosmo A Confluent Reduction for the
lambda-Calculus with Surjective Pairing
and Terminal Object . . . . . . . . . . 291
T. Fernando Provably Recursive Programs and Program
Extraction . . . . . . . . . . . . . . . 303
T. Lengauer and
D. Theune Efficient Algorithms for Path Problems
with General Cost Criteria . . . . . . . 314
H. N. Djidjev and
G. E. Pantziou and
C. D. Zaroliagis Computing Shortest Paths and Distances
in Planar Graphs . . . . . . . . . . . . 327
Z. Galil and
G. F. Italiano Maintaining Biconnected Components of
Dynamic Planar Graphs . . . . . . . . . 339
M. Loebl Efficient Maximal Cubic Graph Cuts . . . 351
U. Vishkin Structural Parallel Algorithmics
(Invited Lecture) . . . . . . . . . . . 363
D. Ranjan and
S. Chari and
P. Rohatgi Improving Known Solutions is Hard . . . 381
L. A. Hemachandra and
A. Hoene Collapsing Degrees via Strong
Computation . . . . . . . . . . . . . . 393
T. Hagerup Fast Parallel Generation of Random
Permutations . . . . . . . . . . . . . . 405
H. Jung and
M. Serna and
P. Spirakis A Parallel Algorithm for two Processors
Precedence Constraint Scheduling . . . . 417
M. Furer and
B. Raghavachari An Efficient NC Algorithm for Finding
Hamiltonian Cycles in Dense Directed
Graphs . . . . . . . . . . . . . . . . . 429
W. Thomas On Logics, Tilings, and Automata
(Invited Lecture) . . . . . . . . . . . 441
J.-P. Jouannaud and
M. Okada Satisfiability of Systems of Ordinal
Notations with the Subterm Property is
Decidable . . . . . . . . . . . . . . . 455
H. Comon Complete Axiomatizations of some
Quotient Term Algebras . . . . . . . . . 469
R. Bol and
J. F. Groote The Meaning of Negative Premises in
Transition System Specifications . . . . 481
W. Vogler Deciding History Preserving Bisimilarity 495
L. Aceto and
M. Hennessy Adding Action Refinement to a Finite
Process Algebra . . . . . . . . . . . . 506
D. Bini and
L. Gemignani and
V. Pan Improved Parallel Computations with
Matrices and Polynomials . . . . . . . . 520
J. Lagergren and
S. Arnborg Finding Minimal Forbidden Minors Using a
Finite Congruence . . . . . . . . . . . 532
H. L. Bodlaender and
T. Kloks Better Algorithms for the Pathwidth and
Treewidth of Graphs . . . . . . . . . . 544
F. Cucker and
A. Torrecillas Two P-complete Problems in the Theory of
the Reals . . . . . . . . . . . . . . . 556
J. Honkala and
A. Salomaa L Morphisms: Bounded Delay and
Regularity of Ambiguity . . . . . . . . 566
V. Bruyere and
C. de Felice Degree et Decomposability of
Variable-Length Codes . . . . . . . . . 575
T. Wilke An EILENBERG Theorem for inf-Languages 588
K. Culik and
S. Dube Balancing Order and Chaos in Image
Generation . . . . . . . . . . . . . . . 600
Y. Gurevich Average Case Complexity (Invited
Lecture) . . . . . . . . . . . . . . . . 615
Jiang Tao and
B. Ravikumar Minimal NFA Problems are Hard . . . . . 629
K. Hashiguchi Algorithms for Determining the Smallest
Number of Nonterminals (States)
Sufficient for Generating (Accepting) a
Regular Language . . . . . . . . . . . . 641
B. Bhattacharya and
G. Toussaint Computing Shortest Transversals . . . . 649
B. Chazelle and
H. Edelsbrunner and
M. Grigni and
L. Guibas and
J. Hershberger and
M. Sharir and
J. Snoeyink Ray Shooting in Polygons Using Geodesic
Triangulations . . . . . . . . . . . . . 661
M. Bern and
D. Eppstein and
F. Yao The Expected Extremes in a Delaunay
Triangulation . . . . . . . . . . . . . 674
B. Chazelle Computational Geometry for the Gourmet:
Old Fare and New Dishes (Invited
Lecture) . . . . . . . . . . . . . . . . 686
P. Duris and
Z. Galil On the Power of Multiple Reads in a Chip 697
H. D. Groger and
G. Turan On Linear Decision Trees Computing
Boolean Functions . . . . . . . . . . . 707
Z. Galil and
O. Margalit An Almost Linear-Time Algorithm for the
Dense Subset-Sum Problem . . . . . . . . 719
S. Khuller and
S. G. Mitchell and
V. V. Vazirani On-line Algorithms for Weighted
Bipartite Matching and Stable Marriages 728
M. Naor String Matching with Preprocessing of
Text and Pattern . . . . . . . . . . . . 739
R. Ravi and
A. Agrawal and
P. Klein Ordering Problems Approximated:
Single-Processor Scheduling and Interval
Graph Completion . . . . . . . . . . . . 751
J. R. Saffer and
H. H. Barrett and
H. B. Barber and
J. M. Woolfenden Surgical probe design for a coincidence
imaging system without a collimator . . 8
G. Zubal and
C. Harrell Voxel based Monte Carlo calculations of
nuclear medicine images and applied
variance reduction techniques . . . . . 23
S. R. Meikle and
B. F. Hutton and
D. L. Bailey and
R. R. Fulton and
K. Schindhelm SPECT scatter correction in
non-homogeneous media . . . . . . . . . 34
R. Clack and
G. L. Zeng and
Y. Weng and
P. E. Christian and
G. T. Gullberg Cone beam single photon emission
computed tomography using two orbits . . 45
J-P. V. Guedon and
Y. J. Bizais Spline-based regularization for discrete
FBP reconstruction . . . . . . . . . . . 55
C. J. Henri and
D. L. Collins and
T. M. Peters Reconstruction of $3$-D branching
structures . . . . . . . . . . . . . . . 65
J. Llacer and
E. Veklerov and
J. Nunez Preliminary examination of the use of
case specific medical information as
``prior'' in Bayesian reconstruction . . 81
Z. Liang and
R. Jaszczak and
R. Coleman On reconstruction and segmentation of
piecewise continuous images . . . . . . 94
R. Leahy and
X. Yan Incorporation of anatomical MR data for
improved functional imaging with PET . . 105
G. Gindi and
M. Lee and
A. Rangarajan and
I. G. Zubal Bayesian reconstruction of functional
images using registered anatomical
images as priors . . . . . . . . . . . . 121
C. A. Pelizzari and
K. K. Tan and
D. N. Levin and
G. T. Y. Chen and
J. Balter Interactive $3$-D patient-image
registration . . . . . . . . . . . . . . 132
P. A. van den Elsen and
M. A. Viergever Marker guided registration of
electromagnetic dipole data with
tomographic images . . . . . . . . . . . 142
D. Lemoine and
C. Barillot and
B. Gibaud and
E. Pasqualini An anatomical-based $3$D registration
system of multimodality and atlas data
in neurosurgery . . . . . . . . . . . . 154
M. A. Oghabian and
A. Todd-Pokropek Registration of brain images by a
multi-resolution sequential method . . . 165
G. Gerig and
J. Martin and
R. Kikinis and
O. Kubler and
M. Shenton and
F. A. Jolesz Automating segmentation of dual-echo MR
head data . . . . . . . . . . . . . . . 175
M. E. Brummer and
R. M. Mersereau and
R. L. Eisner and
R. R. J. Lewine Automatic detection of brain contours in
MRI data sets . . . . . . . . . . . . . 188
M. Bister and
J. Cornelis and
Y. Taeymans Towards automated analysis in $3$D
cardiac MR imaging . . . . . . . . . . . 205
W. Snyder and
A. Logenthiran and
P. Santago and
K. Link and
G. Bilbro and
S. Rajala Segmentation of magnetic resonance
images using mean field annealing . . . 218
N. Karssemeijer A stochastic model for automated
detection of calcifications in digital
mammograms . . . . . . . . . . . . . . . 227
B. M. ter Haar Romeny and
L. M. J. Florack and
J. J. Koenderink and
M. A. Viergever Scale-space: its natural operators and
differential invariants . . . . . . . . 239
L. D. Griffin and
A. C. F. Colchester and
G. P. Robinson Scale and segmentation of grey-level
images using maximum gradient paths . . 256
O. Monga and
N. Ayache and
P. Sander Using uncertainty to link $3$D edge
detection and local surface modelling 273
W. J. Lin and
S. M. Pizer and
V. E. Johnson Boundary estimation in ultrasound images 285
G. Malandain and
G. Bertrand and
N. Ayache Topological classification in digital
space . . . . . . . . . . . . . . . . . 300
G. T. Herman and
C. A. Bucholtz Shape-based interpolation using a
chamfer distance . . . . . . . . . . . . 314
F. L. Bookstein Thin-plate splines and the atlas problem
for biomedical images . . . . . . . . . 326
A. A. Amini and
R. L. Owen and
P. Anandan and
J. S. Duncan Non-rigid motion models for tracking the
left ventricular wall . . . . . . . . . 343
H. I. Bozma and
J. S. Duncan Model-based recognition of multiple
deformable objects using a
game-theoretic framework . . . . . . . . 358
D. C. Barber and
W. B. Tindale Extraction of background distributions
from abnormal data sets: application to
radiolabelled leucocyte imaging . . . . 373
A. S. Houston and
K. S. Nijran A quantitative comparison of current
methods of factor analysis of dynamic
structures (FADS) in renal dynamic
studies . . . . . . . . . . . . . . . . 386
M. Samal and
M. Karny and
D. Zahalka Confirmatory aspects in factor analysis
of image sequences . . . . . . . . . . . 397
R. A. Baldock Trainable models for the interpretation
of echocardiogram images . . . . . . . . 408
A. Ovalle and
C. Garbay KIDS: A distributed expert system for
biomedical image interpretation . . . . 419
E. Binaghi and
A. Rampini Learning of uncertain classification
rules in biomedical images: the case of
colposcopic images . . . . . . . . . . . 434
S. Dellepiane and
G. Venturi and
G. Vernazza A fuzzy model for the processing and
recognition of MR pathological images 444
H. H. Barrett and
T. Gooley and
K. Girodias and
J. Rolland and
T. White and
J. Yao Linear discriminants and image quality 458
R. Cromartie and
S. M. Pizer Edge-affected context for adaptive
contrast enhancement . . . . . . . . . . 474
R. Ohbuchi and
H. Fuchs Incremental volume rendering algorithm
for interactive $3$D ultrasound imaging 486
B. Gudmundsson and
M. Randen Compression of sequences of $3$D-volume
surface projections . . . . . . . . . . 501
Alan Snyder Modeling the C++ Object Model: An
Application of an Abstract Object Model 1
Urs Hölzle and
Craig Chambers and
David Ungar Optimizing Dynamically-Typed
Object-Oriented Languages With
Polymorphic Inline Caches . . . . . . . 21
Angelo Morzenti and
Pierluigi San Pietro An Object-Oriented Logic Language for
Modular System Specification . . . . . . 39
Alan Wills Capsules and Types in Fresco: Program
Verification in Smalltalk . . . . . . . 59
Gilles Barbedette Schema Modifications in the LISPO2
Persistent Object-Oriented Language . . 77
Christine Delcourt and
Roberto Zicari The Design of an Integrity Consistency
Checker (ICC) for an Object Oriented
Database System . . . . . . . . . . . . 97
Christian Neusius Synchronizing Actions . . . . . . . . . 118
Kohei Honda and
Mario Tokoro An Object Calculus for Asynchronous
Communication . . . . . . . . . . . . . 133
Stefano Crespi Reghizzi and
Guido Galli de Paratesi and
Stefano Genolini Definition of Reusable Concurrent
Software Components . . . . . . . . . . 148--166
Elspeth Cusack Inheritance in Object Oriented Z . . . . 167
Antonio J. Alencar and
Joseph A. Goguen OOZE: An Object Oriented Z Environment 180
Jay Almarode Issues in the Design and Implementation
of a Schema Designer for an OODBMS . . . 200
Claudia Bauzer Medeiros and
Patrick Pfeffer Object Integrity Using Rules . . . . . . 219
Satoshi Matsuoka and
Takuo Watanabe and
Akinori Yonezawa Hybrid Group Reflective Architecture for
Object-Oriented Concurrent Reflective
Programming . . . . . . . . . . . . . . 231
Ramana Rao Implementational Reflection in Silica 251
Serge Lacourte Exceptions in Guide, an Object-Oriented
Language for Distributed Applications 268
Francis Wolinski and
Jean-François Perrot Representation of Complex Objects:
Multiple Facets with Part-Whole
Hierarchies . . . . . . . . . . . . . . 288
Warwick B. Mugridge and
John Hamer and
John G. Hosking Multi-Methods in a Statically-Typed
Programming Language . . . . . . . . . . 307
Jens Palsberg and
Michael I. Schwartzbach What is Type-Safe Code Reuse? . . . . . 325
Ernst Lippe and
Gert Florijn Implementation Techniques for Integral
Version Management . . . . . . . . . . . 342
Dennis de Champeaux Object-Oriented Analysis and Top-Down
Software Development . . . . . . . . . . 360
Dennis de Champeaux Object-Oriented Analysis and Top-Down
Software Development . . . . . . . . . . 360
Paul L. Bergstein and
Karl J. Lieberherr Incremental Class Dictionary Learning
and Optimization . . . . . . . . . . . . 377
N. M. Mattos An Approach to Knowledge Base Management 1
Th. Ericson and
V. A. Zinoviev Concatenated spherical codes . . . . . . 2
M. Elia and
G. Taricco A note on automorphism groups of codes
and symbol error probability computation 6
T. Berger A direct proof for the automorphism
group of Reed--Solomon codes . . . . . . 21
T. Beth and
D. E. Lazic and
V. Senk A family of binary codes with
asymptotically good distance
distribution . . . . . . . . . . . . . . 30
C. Carlet A transformation on Boolean functions,
its consequences on some problems
related to Reed--Muller codes . . . . . 42
P. Langevin Covering radius of RM (1,9) in RM (3,9) 51
F. Rodier The weights of the duals of binary BCH
codes of designed distance delta = 9 . . 60
D. Augot and
P. Charpin and
N. Sendrier The minimum distance of some binary
codes via the Newton's identities . . . 65
J. Burger and
H. Chabanne and
M. Girault Minimum-change binary block-codes which
are well balanced . . . . . . . . . . . 76
A. O. Mabogunje and
P. G. Farrell Construction of unequal error protection
codes . . . . . . . . . . . . . . . . . 87
G. D. Cohen and
L. Gargano and
U. Vaccaro Unidirectional error-detecting codes . . 94
A. Montpetit Coherent partitions and codes . . . . . 106
A. Astie-Vidal and
V. Dugat (1/lambda)-regular and
(1/lambda)-homogeneous tournaments . . . 114
D. Le Brigand Decoding of codes on hyperelliptic
curves . . . . . . . . . . . . . . . . . 126
D. Rotillon and
J. A. Thiong Ly Decoding of codes on the Klein Quartic 135
C. Voss Asymptotically good families of
geometric Goppa codes and the
Gilbert--Varshamov bound . . . . . . . . 150
M. Perret Multiplicative character sums and non
linear geometric codes . . . . . . . . . 158
M. Girault A survey of identification schemes . . . 168
S. Harari A correlation cryptographic scheme . . . 180
J. Patarin Pseudorandom permutations based on the
DES scheme . . . . . . . . . . . . . . . 193
H. J. Fell Linear complexity of transformed
sequences . . . . . . . . . . . . . . . 205
G. Chasse Some remarks on a LFSR ``disturbed'' by
other sequences . . . . . . . . . . . . 215
R. Creutzburg Parameters for complex FFTs infinite
residue class rings . . . . . . . . . . 222
J. Domingo-Ferrer and
L. Huguet-Rotger A cryptographic tool for programs
protection . . . . . . . . . . . . . . . 227
D. Haccoun Decoding techniques for convolutional
codes . . . . . . . . . . . . . . . . . 242
R. Sfez and
G. Battail A weighted-output variant of the Viterbi
algorithm for concatenated schemes using
a convolutional inner code . . . . . . . 259
R. Baldini Filho and
P. G. Farrell Coded modulation with convolutional
codes over rings . . . . . . . . . . . . 271
A. Sgarro A Shannon-theoretic coding theorem in
authentication theory . . . . . . . . . 282
A. Fioretto and
A. Sgarro Joint fractional entropy . . . . . . . . 292
G. Battail and
M. Guazzo On the adaptive source coding . . . . . 298
R. M. Capocelli and
A. De Santis Minimum codeword length and redundancy
of Huffman codes . . . . . . . . . . . . 309
A. R. Calderbank Binary covering codes and high speed
data transmission . . . . . . . . . . . 320
G. Battail and
H. Magalhaes De Oliviera and
Z. Weidong Coding and modulation for the Gaussian
channel, in the absence or in the
presence of fluctuations . . . . . . . . 337
R. Sfez and
J. C. Belfiore and
K. Leeuwin and
A. Fihel Comparison of two modulation-coding
schemes for low-rate digital land mobile
radio communication . . . . . . . . . . 350
K. Leeuwin and
J. C. Belfiore and
G. Kawas Kaleh Chernoff bound of trellis coded
modulation over correlated Rayleigh
channel . . . . . . . . . . . . . . . . 364
M. M. Darmon and
P. R. Sadot A hybrid FEC-ARQ communication system
using sequential decoding . . . . . . . 378
J.-L. Politano and
D. Deprey A 30 Mbits/s (255,223) Reed--Solomon
decoder . . . . . . . . . . . . . . . . 385
Oskar Dressler and
Adam Farquhar Putting the Problem Solver Back in the
Driver's Seat: Contextual Control of the
AMTS . . . . . . . . . . . . . . . . . . 1
Ulrich Junker Variations on Backtracking for TMS . . . 17
Katsumi Inoue An Abductive Procedure for the CMS/ATMS 34
A. C. Kakas and
P. Mancarella Knowledge Assimilation and Abduction . . 54
Laura Giordano and
Alberto Martelli Truth Maintenance Systems and Belief
Revision . . . . . . . . . . . . . . . . 71
Didier Dubois and
Jerome Lang and
Henri Prade A Possibilistic Assumption-Based Truth
Maintenance System with Uncertain
Justifications, and its Application to
Belief Revision . . . . . . . . . . . . 87
Pierre Tayrac ARC: An Extended ATMS Based on Directed
CAT-Correct Resolution . . . . . . . . . 107
Yasushi Fujiwara and
Shinichi Honiden On Logical Foundations of the ATMS . . . 125
Cees Witteveen A Skeptical Semantics for Truth
Maintenance . . . . . . . . . . . . . . 136
Peter Jackson and
John Pais Semantic Accounts of Belief Revision . . 155
Francois Bronsard and
Uday S. Reddy Conditional Rewriting in Focus . . . . . 2
Nachum Dershowitz A Maximal-Literal Unit Strategy for Horn
Clauses . . . . . . . . . . . . . . . . 14
Jan Willem Klop and
Roel de Vrijer Extended Term Rewriting Systems (invited
paper) . . . . . . . . . . . . . . . . . 26
Emmanuel Kounalis and
Michael Rusinowitch A Proof System for Conditional Algebraic
Specifications . . . . . . . . . . . . . 51
Jose Meseguer Conditional Rewriting Logic: Deduction,
Models and Concurrency (invited paper) 64
Chilukuri K. Mohan Equivalences of Rewrite Programs (*) . . 92
Chen Hong and
Hsiang Jieh and
Kong Hwa-Chung On Finite Representations of Infinite
Sequences of Terms . . . . . . . . . . . 100
Chen Yiyun and
Michael J. O'Donnell Infinite Terms and Infinite Rewritings 115
Chen Yiyun and
Michael J. O'Donnell Testing Confluence of Nonterminating
Rewriting Systems . . . . . . . . . . . 127
Bernard R. Hodgson and
Clement F. Kent A Survey of Ordinal Interpretations of
Type $ \epsilon_0 $ for Termination of
Rewriting Systems (*) . . . . . . . . . 137
Helene Kirchner and
Miki Hermann Meta-rule Synthesis from Crossed Rewrite
Systems . . . . . . . . . . . . . . . . 143
Siva Anantharaman and
Maria Paola Bonacina An Application of Automated Equational
Reasoning to Many-Valued Logic (*) . . . 156
Leo Bachmair and
Harald Ganzinger Completion of First-Order Clauses with
Equality by Strict Superposition
(invited paper) . . . . . . . . . . . . 162
Hubert Bertling Knuth--Bendix Completion of Horn Clause
Programs for Restricted Linear
Resolution and Paramodulation . . . . . 181
Eddy Bevers and
Johan Lewi Proof by Consistency in Conditional
Equational Theories . . . . . . . . . . 194
Maria Paola Bonacina and
Hsiang Jieh Completion Procedures as Semi-Decision
Procedures (invited paper) . . . . . . . 206
Herve Devie Linear Completion . . . . . . . . . . . 233
Robert Nieuwenhuis and
Fernando Orejas Clausal Rewriting . . . . . . . . . . . 246
Franco Barbanera Adding Algebraic Rewriting to the
Calculus of Constructions: Strong
Normalization Preserved . . . . . . . . 262
Wadoud Bousdira and
Jean-Luc Remy On Sufficient Completeness of
Conditional Specifications . . . . . . . 272
N. Lichtenstein and
S. Kaplan FPL: Functional Plus Logic Programming.
An Integration of the FP and Prolog
Languages . . . . . . . . . . . . . . . 287
Aart Middeldorp Confluence of the Disjoint Union of
Conditional Term Rewriting Systems . . . 295
Detlef Plump Implementing Term Rewriting by Graph
Reduction: Termination of Combined
Systems . . . . . . . . . . . . . . . . 307
Hitoshi Aida and
Joseph Goguen and
Jose Meseguer Compiling Concurrent Rewriting onto the
Rewrite Rule Machine . . . . . . . . . . 320
Sergio Antoy Design Strategies for Rewrite Rules . . 333
Louis Galbiati and
Carolyn Talcott A Simplifier for Untyped Lambda
Expressions . . . . . . . . . . . . . . 342
M. C. J. D. van Eekelen and
M. J. Plasmeijer and
J. E. W. Smetsers Parallel Graph Rewriting on Loosely
Coupled Machine Architectures . . . . . 354
Roberto M. Amadio Typed Equivalence, Type Assignment and
Type Containment . . . . . . . . . . . . 372
Martin Emele and
Remi Zajac A Fixed-Point Semantics for Feature Type
Systems (*) . . . . . . . . . . . . . . 383
John G. Stell Unique-Sort Order-Sorted Theories: A
Description as Monad Morphisms . . . . . 389
Sun Yong Equational Logics (Birkhoff's Method
Revisited) (*) . . . . . . . . . . . . . 401
Uwe Waldmann Compatibility of Order-Sorted Rewrite
Rules . . . . . . . . . . . . . . . . . 407
G. Aguzzi and
U. Modigliani and
M. C. Verri A Universal Termination Condition for
Solving Goals in Equational Languages
(*) . . . . . . . . . . . . . . . . . . 418
John Darlington and
Guo Yike Constrained Equational Deduction . . . . 424
Tobias Nipkow Higher-Order Unification, Polymorphism,
and Subsorts . . . . . . . . . . . . . . 436
Qian Zhenyu Second-Order Unification in the Presence
of Linear Shallow Algebraic Equations
(*) . . . . . . . . . . . . . . . . . . 448
Wayne Snyder and
Christopher Lynch An Inference System for Horn Clause
Logic with Equality: A Foundation for
Conditional E-Unification and for Logic
Programming in the Presence of Equality 454
K. Nokel Temporally Distributed Symptoms in
Technical Diagnosis . . . . . . . . . . 1
J. G. Williams Instantiation Theory: On the Foundations
of Automated Deduction . . . . . . . . . 1
W. Cunto and
J. I. Munro and
P. V. Poblete A Case Study in Comparison Based
Complexity: Finding the Nearest Value(s) 1
B. Aronov and
M. Sharir On the Zone of a Surface in a Hyperplane
Arrangement . . . . . . . . . . . . . . 13
M. Pellegrini Ray-shooting and Isotopy Classes of
Lines in $3$-Dimensional Space . . . . . 20
P. F. Dietz Finding Level-Ancestors in Dynamic Trees 32
R. Sundaram and
K. S. Singh and
C. Pandu Rangan Treewidth of Circular-Arc Graphs . . . . 41
O. Devillers and
S. Meiser and
M. Teillaud Fully Dynamic Delaunay Triangulation in
Logarithmic Expected Time Per Operation 42
H. Djidjev and
A. Lingas On Computing the Voronoi Diagram for
Restricted Planar Figures . . . . . . . 54
J. Diaz and
A. M. Gibbons and
M. S. Paterson and
J. Toran The Minsumcut Problem . . . . . . . . . 65
N. Katoh and
K. Iwano Efficient Algorithms For The Minimum
Range Cut Problems . . . . . . . . . . . 80
S. G. Akl Memory Access in Models of Parallel
Computation: From Folklore to Synergy
and Beyond . . . . . . . . . . . . . . . 92
P. K. Agarwal and
J. Matousek and
S. Suri Farthest Neighbors, Maximum Spanning
Trees and Related Problems in Higher
Dimensions . . . . . . . . . . . . . . . 105
J. S. Salowe Shallow Interdistance Selection and
Interdistance Enumeration . . . . . . . 117
O. R. Aguilar and
A. Kumar Datta and
S. Ghosh Sharing Memory in Asynchronous Message
Passing Systems . . . . . . . . . . . . 129
L. Yu and
D. J. Rosenkrantz A Linear-Time Scheme for Version
Reconstruction . . . . . . . . . . . . . 141
E. N. Hanson The Interval Skip List: A Data Structure
for Finding All Intervals That Overlap a
Point . . . . . . . . . . . . . . . . . 153
E. M. Arkin and
S. Khuller and
J. S. B. Mitchell Geometric Knapsack Problems . . . . . . 165
Y. Han A Fast Derandomization Scheme and Its
Applications . . . . . . . . . . . . . . 177
T. Lengauer and
D. Theune Unstructured Path Problems and the
Making of Semirings . . . . . . . . . . 189
F. Yao Neighborhood Graphs and Geometric
Embedding . . . . . . . . . . . . . . . 201
J. S. B. Mitchell and
E. L. Wynters Finding Optimal Bipartitions of Points
and Polygons . . . . . . . . . . . . . . 202
J. Czyzowicz and
I. Stojmenovic and
J. Urrutia Immobilizing a Polytope . . . . . . . . 214
P. Jacquet and
W. Szpankowski What Can We Learn About Suffix Trees
From Independent Tries? . . . . . . . . 228
F. d'Amore and
A. Marchetti-Spaccamela and
U. Nanni Competitive Algorithms for the Weighted
List Update Problem . . . . . . . . . . 240
B. J. Nilsson and
S. Schuierer An Optimal Algorithm for the Rectilinear
Link Center of a Rectilinear Polygon . . 249
G. Das and
G. Narasimhan Geometric Searching and Link Distance 261
D. Naor and
V. V. Vazirani Representing and Enumerating Edge
Connectivity Cuts in RNC . . . . . . . . 273
G. Kant and
H. L. Bodlaender Planar Graph Augmentation Problems . . . 286
G. N. Frederickson Parametric Search and Locating Supply
Centers in Trees . . . . . . . . . . . . 299
C. D. Yang and
D. T. Lee and
C. K. Wong On Bends and Lengths of Rectilinear
Paths: A Graph-Theoretic Approach . . . 320
J. Hershberger and
J. Snoeyink Computing Minimum Length Paths of a
Given Homotopy Class . . . . . . . . . . 331
J. Bar-Ilan and
D. Peleg Approximation Algorithms for Selecting
Network Centers . . . . . . . . . . . . 343
S. S. Ravi and
D. J. Rosenkrantz and
G. K. Tayi Facility Dispersion Problems: Heuristics
and Special Cases . . . . . . . . . . . 355
S. Carlsson and
B. J. Nilsson and
S. Ntafos Optimum Guard Covers and $m$-Watchmen
Routes for Restricted Polygons . . . . . 367
P. K. Agarwal and
M. U. Sharir Applications of a New Space Partitioning
Technique . . . . . . . . . . . . . . . 379
D. Eppstein Offline Algorithms for Dynamic Minimum
Spanning Tree Problems . . . . . . . . . 392
B. M. E. Moret and
H. D. Shapiro An Empirical Analysis of Algorithms for
Constructing a Minimum Spanning Tree . . 400
B. K. Bhattacharya and
A. Mukhopadhyay and
G. T. Toussaint A Linear Time Algorithm for Computing
the Shortest Line Segment From Which a
Polygon is Weakly Externally Visible . . 412
G. Vegter Dynamically Maintaining the Visibility
Graph . . . . . . . . . . . . . . . . . 425
P. J. Heffernan and
J. S. B. Mitchell An Optimal Algorithm for Computing
Visibility in the Plane . . . . . . . . 437
G. F. Italiano and
N. Sarnak Fully Persistent Data Structures for
Disjoint Set Union Problems . . . . . . 449
S. Kapoor and
H. Ramesh Algorithms for Generating all Spanning
Trees of Undirected, Directed and
Weighted Graphs . . . . . . . . . . . . 461
J. I. Munro and
V. Raman Sorting Multisets and Vectors In-Place 473
K. Abrahamson and
A. Adler and
L. Higham and
D. Kirkpatrick Probabilistic Leader Election on Rings
of Known Size . . . . . . . . . . . . . 481
J.-L. Lassez and
M. Maher and
K. Marriott Elimination of negation in term algebras 1
P. Lescanne Rewrite orderings and termination of
rewrite systems . . . . . . . . . . . . 17
Z. Manna and
A. Pnueli On the faithfulness of formal models . . 28
M. Nielsen Models for concurrency . . . . . . . . . 43
A. Salwicki On a hierarchy of file types and a tower
of their theories . . . . . . . . . . . 47
F. Alessi and
F. Barbanera Strong conjunction and intersection
types . . . . . . . . . . . . . . . . . 64
E. Astesiano and
M. Cerioli Partial higher-order specifications . . 74
S. Bonnier Unification in incompletely specified
theories: a case study . . . . . . . . . 84
G. Boudol and
I. Castellani and
M. Hennessy and
A. Kiehn Observing localities . . . . . . . . . . 93
G. Costa and
G. Reggio Abstract dynamic data types: a temporal
logic approach . . . . . . . . . . . . . 103
A. Cerny Generating words by cellular automata 113
P. Degano and
R. Gorrieri Atomic refinement in process description
languages . . . . . . . . . . . . . . . 121
V. Diekert and
P. Gastin and
A. Petit Recognizable complex trace languages . . 131
E. Domenjoud Solving systems of linear Diophantine
equations: an algebraic approach . . . . 141
G. Dowek A second-order pattern matching
algorithm for the cube of typed
lambda-calculi . . . . . . . . . . . . . 151
L. Egidi and
F. Honsell and
S. Ronchi della Rocca The lazy call-by-value lambda-calculus 161
R. Gorrieri and
C. Laneve The limit of split ${}_n$-bisimulations
for CCS agents . . . . . . . . . . . . . 170
G. Hansel and
D. Krob and
Ch. Michaux Stochastic automata and length
distributions of rational languages . . 181
B. P. Hilken and
D. E. Rydeheard Towards a categorical semantics type
classes . . . . . . . . . . . . . . . . 191
R. R. Howell and
P. Jancar and
L. E. Rosier Single-path Petri nets . . . . . . . . . 202
J. Hromkovic and
B. Monien The bisection problem for graphs of
degree 4 (configuring Transputer
systems) . . . . . . . . . . . . . . . . 211
O. H. Ibarra and
Jiang Tao and
Wang Hui Some results concerning $2$-D on-line
tessellation acceptors and $2$-D
alternating finite automata . . . . . . 221
P. Inverardi and
M. Nesi Infinite normal forms for non-linear
term rewriting systems . . . . . . . . . 231
P. Jokinen and
E. Ukkonen Two algorithms for approximate string
matching in static texts . . . . . . . . 240
J. Karhumaki and
W. Rytter and
S. Jarominek Efficient constructions of test sets for
regular and context-free languages . . . 249
D. Kavadias and
L. M. Kirousis and
P. Spirakis The complexity of the reliable
connectivity problem . . . . . . . . . . 259
D. Kesner Pattern matching in order-sorted
languages . . . . . . . . . . . . . . . 267
B. Konikowska Two over three: a two-valued logic for
software specification and validation
over a three-valued predicate calculus 277
E. Kounalis and
D. Lugiez and
L. Pottier A solution of the complement problem in
associative-commutative theories . . . . 287
Padmanabhan Krishnan A model for real-time systems . . . . . 298
Huong Lam Nguyen and
Long Van Do On strict codes . . . . . . . . . . . . 308
H. Leib and
F. Henglein A decidable case of the semi-unification
problem . . . . . . . . . . . . . . . . 318
C. Leopold Maintaining dictionaries in a
hierarchical memory . . . . . . . . . . 328
Ch. Meinel and
S. Waack Upper and lower bounds for certain
graph-accessibility problems on bounded
alternating omega-branching programs . . 337
U. Montanari and
V. Sassone CCS dynamic bisimulation is progressing 346
M. A. Nait Abdallah Syntax and semantics of a monotonic
framework for non-monotonic reasoning 357
D. Niwinski On the cardinality of sets of infinite
trees recognizable by finite automata 367
B. Paech Extending temporal logic by explicit
concurrency . . . . . . . . . . . . . . 377
R. Pino Perez An extensional partial combinatory
algebra based on lambda-terms . . . . . 387
A. Poigne Once more on order-sorted algebras . . . 397
Y. Roos and
P. A. Wacrenier Composition of two semi commutations . . 406
P. Ruzicka An efficient decision algorithm for the
uniform semi-unification problem . . . . 415
K. V. Shvachko Different modifications of pointer
machines and their computational power 426
P. P. Shenoy On Spohn's Theory of Epistemic Beliefs 2
R. Kennes and
P. Smets Fast Algorithms for Dempster-Shafer
Theory . . . . . . . . . . . . . . . . . 14
R. Kruse and
E. Schwecke On the Combination of Information
Sources . . . . . . . . . . . . . . . . 24
M. Spies Application Aspects of Qualitative
Conditional Independence . . . . . . . . 31
M. Deutsch-McLeish A Study of Probabilities and Belief
Functions under Conflicting Evidence:
Comparisons and New Methods . . . . . . 41
J. Kohlas and
P.-A. Monney Propagating Belief Functions Through
Constraints Systems . . . . . . . . . . 50
S. Moral and
L. M. de Campos Updating Uncertain Information . . . . . 58
Hsia Yen-Teh Assessing Multiple Beliefs According to
One Body of Evidence --- Why It May Be
Necessary, and How We Might Do It
Correctly . . . . . . . . . . . . . . . 68
G. Paass Probabilistic Default Reasoning . . . . 76
B. Abramson On Knowledge Representation in Belief
Networks . . . . . . . . . . . . . . . . 86
Z. Luo and
A. Gammerman STOSS --- A Stochastic Simulation System
for Bayesian Belief Networks . . . . . . 97
G. Coletti and
A. Gilio and
R. Scozzafava Conditional Events with Vague
Information in Expert Systems . . . . . 106
D. E. O'Leary On Representation of Source Reliability
in Weight of Evidence . . . . . . . . . 115
T. P. Martin and
J. F. Baldwin An Abstract Mechanism for Handling
Uncertainty . . . . . . . . . . . . . . 126
O. Bobrowicz and
C. Choulet and
A. Haurat and
F. Sandoz and
M. Tebaa A Method to Build Membership Functions 136
Gao Jian-Ming and
A. Nakamura Algebraic Analysis of Fuzzy
Indiscernibility . . . . . . . . . . . . 143
S. Ovchinnikov On Modelling Fuzzy Preference Relations 154
J. Aguilar-Martin and
M. Martin and
N. Piera Conceptual Connectivity Analysis by
Means of Fuzzy Partitions . . . . . . . 165
A. di Nola and
W. Kolodziejczyk and
S. Sessa Transitive Solutions of Relational
Equations on Finite Sets and Linear
Lattices . . . . . . . . . . . . . . . . 173
M. Wygralak Generalized Cardinal Numbers and Their
Ordering . . . . . . . . . . . . . . . . 183
A. Gonzalez and
M.-A. Vila An Interval-Based Approach for Working
With Fuzzy Numbers . . . . . . . . . . . 193
H. E. Kyburg Beyond Specificity . . . . . . . . . . . 204
E. Gregoire About the Logical Interpretation of
Ambiguous Inheritance Hierarchies . . . 213
P. Balbiani Non-monotonic Reasoning and Modal Logic,
from Negation as Failure to Default
Logic . . . . . . . . . . . . . . . . . 223
C. Bernasconi and
S. Rivoira and
S. Termini On the Notion of Uncertain Belief
Revision Systems . . . . . . . . . . . . 232
M. Cori Non-monotonic Reasoning in a Semantic
Network . . . . . . . . . . . . . . . . 239
D. Dubois and
H. Prade Inference in Possibilistic Hypergraphs 250
J. Lang Semantic Evaluation in Possibilistic
Logic, Application to Min-Max Discrete
Optimisation Problems . . . . . . . . . 260
J. Agusti-Cullell and
F. Esteva and
P. Garcia and
L. Godo Formalizing Multiple-Valued Logics as
Institutions . . . . . . . . . . . . . . 269
P. Bottoni and
L. Mari and
P. Mussio Empirical Plausible Reasoning by
Multiple-Valued Logic . . . . . . . . . 279
F. D. Anger and
R. V. Rodriguez Time, Tense and Relativity Revisited . . 286
G. Longo Information and the Mind-Body Problem 298
P. Benvenuti and
D. Vivona and
M. Divari A General Information for Fuzzy Sets . . 307
A. Ramer Information Theory Based on Fuzzy
(Possibilistic) Rules . . . . . . . . . 317
J. M. Morrissey Measuring Uncertainty Given Imprecise
Attribute Values . . . . . . . . . . . . 327
A. Zighed and
D. Tounissoux and
J. P. Auray and
C. Largeron Discrimination by Optimizing a Local
Consistency Criterion . . . . . . . . . 337
B. Forte and
V. Kolbas Minimum Loss of Information and Image
Segmentation . . . . . . . . . . . . . . 349
J. F. Baldwin Towards a General Theory of Evidential
Reasoning . . . . . . . . . . . . . . . 360
G. Longo and
A. Sgarro A Pragmatic Way Out of the Maze of
Uncertainty Measures . . . . . . . . . . 370
J. C. A. van der Lubbe and
E. Backer and
W. Krijgsman Models for Reasoning with Multitype
Uncertainty in Expert Systems . . . . . 377
A. Saffiotti A Hybrid Belief System for Doubtful
Agents . . . . . . . . . . . . . . . . . 393--402
N. Roos How to Reason With Uncertain Knowledge 403
P. A. Ligomenides Computation and Uncertainty in Regulated
Synergetic Machines . . . . . . . . . . 413
J. Kacprzyk and
C. Iwanski Inductive Learning From Incomplete and
Imprecise Examples . . . . . . . . . . . 424
P. Bosc and
O. Pivert Some Algorithms for Evaluating Fuzzy
Relational Queries . . . . . . . . . . . 431
M. H. Williams and
Q. Kong Time and Incompleteness in a Deductive
Database . . . . . . . . . . . . . . . . 443
R. R. Yager and
K. M. Ford and
A. J. Canas An Approach to the Linguistic
Summarization of Data . . . . . . . . . 456
P. Terenziani and
L. Lesmo and
E. Gerbino Management of Uncertainty in the
Attachment Problem in Natural Language
Processing . . . . . . . . . . . . . . . 469
J. Jacas and
J. Recasens A Topological Approach to Some Cluster
Methods . . . . . . . . . . . . . . . . 479
E. Binaghi and
A. della Ventura and
A. Rampini and
R. Schettini A Fuzzy Knowledge-Based System for
Biomedical Image Interpretation . . . . 488
E. Bernard-Weil Management of Chaotic Systems with the
Model for the Regulation of Agonistic
Antagonistic Couples . . . . . . . . . . 498
A. D. Pearman and
J. Montero and
J. Tejada Fuzzy Multicriteria Techniques: An
Application to Transport Planning . . . 510
A. Salski and
C. Sperlbaum Fuzzy Logic Approach to Modelling in
Ecosystem Research . . . . . . . . . . . 520
A. Kershenbaum and
T. Rubinson An Application of Fuzzy Multi-Criteria
Decision Making for Topological Design
of Large Networks . . . . . . . . . . . 528
F. Esposito and
D. Malerba and
G. Semeraro A Distance Measure for Decision Making
in Uncertain Domains . . . . . . . . . . 538
M. Cerf and
S. Poitrenaud and
J.-F. Richard and
M. Sebillotte and
C. A. Tijus Decisions and Lack of Precision in Crop
Management: The Role of Processing Both
Objects and Procedures Through Semantic
Networks . . . . . . . . . . . . . . . . 548
S. I. Gallant and
Y. Hayashi A Neural Network Expert System With
Confidence Measurements . . . . . . . . 562
L. Console and
C. Borlo and
A. Casale and
P. Torasso Dealing With Uncertainty in a
Distributed Expert System Architecture 568
R. J. Machado and
A. F. da Rocha The Combinatorial Neural Network: A
Connectionist Model for Knowledge Based
Systems . . . . . . . . . . . . . . . . 578
M. E. Cohen and
D. L. Hudson A Medical Decision Aid Based on a Neural
Network Model . . . . . . . . . . . . . 588
M. O'Hagan A Fuzzy Neuron Based Upon Maximum
Entropy Ordered Weighted Averaging . . . 598
Ruth Aylett and
Alan Fish and
Simon Bartrum HELP --- A Hierarchical Execution-Led
Planner for Robotic Domains . . . . . . 1
Joseph Downs and
Han Reichgelt Integrating Classical and Reactive
Planning within an Architecture for
Autonomous Agents . . . . . . . . . . . 13
Brian Drabble and
Richard Kirby Associating AI Planner Entities with an
Underlying Time Point Network . . . . . 27
Bertram Fronhofer Default Connections in a Modal Planning
Framework . . . . . . . . . . . . . . . 39
Reza Ghassem-Sani and
Sam Steel Recursive Plans . . . . . . . . . . . . 53
Richard Gobel and
Robert Rodosek A Language for Representing Planning
Problems . . . . . . . . . . . . . . . . 64
Gerd Große and
Richard Waldinger Towards a Theory of Simultaneous Actions 78
Stefan Materne and
Joachim Hertzberg MTMM --- Correcting and Extending Time
Map Management . . . . . . . . . . . . . 88
Pierre Regnier and
Bernard Fade Complete Determination of Parallel
Actions and Temporal Optimization in
Linear Plans of Action . . . . . . . . . 100
Sam Steel Knowledge Subgoals in Plans . . . . . . 112
Tobias Nipkow and
Gregor Snelting Type Classes and Overloading Resolution
via Order-Sorted Unification . . . . . . 1
Dennis M. Volpano and
Geoffrey S. Smith On the Complexity of ML Typability with
Overloading . . . . . . . . . . . . . . 15
Satish R. Thatte Coercive Type Isomorphism . . . . . . . 29
Klaus Erik Schauser and
David E. Culler and
Thorsten von Eicken Compiler-Controlled Multithreading for
Lenient Parallel Languages . . . . . . . 50
Kenneth R. Traub Multi-thread Code Generation for
Dataflow Architectures from Non-Strict
Programs . . . . . . . . . . . . . . . . 73
Luc Maranget GAML: a Parallel Implementation of Lazy
ML . . . . . . . . . . . . . . . . . . . 102
Erik Meijer and
Maarten Fokkinga and
Ross Paterson Functional Programming with Bananas,
Lenses, Envelopes and Barbed Wire . . . 124
John Launchbury A Strongly-Typed Self-Applicable Partial
Evaluator . . . . . . . . . . . . . . . 145
Daniel Weise and
Roland Conybeare and
Erik Ruf and
Scott Seligman Automatic Online Partial Evaluation . . 165
Vipin Swarup and
Uday S. Reddy and
Evan Ireland Assignments for Applicative Languages 192
David Wakeling and
Colin Runciman Linearity and Laziness . . . . . . . . . 215
Pascal Fradet Syntactic Detection of Single-Threading
Using Continuations . . . . . . . . . . 241
David J. Lillie and
Peter G. Harrison A Projection Model of Types . . . . . . 259
Gudmund S. Frandsen and
Carl Sturtivant What is an Efficient Implementation of
the lambda-calculus? . . . . . . . . . . 289
Harry G. Mairson Outline of a Proof Theory of
Parametricity . . . . . . . . . . . . . 313
Allen Leung and
Prateek Mishra Reasoning about Simple and Exhaustive
Demand in Higher-Order Lazy Languages 328
Thomas P. Jensen Strictness Analysis in Logical Form . . 352
Gebreselassie Baraki A Note on Abstract Interpretation of
Polymorphic Functions . . . . . . . . . 367
Shail Aditya and
Rishiyur S. Nikhil Incremental Polymorphism . . . . . . . . 379
Xavier Leroy and
Michel Mauny Dynamics in ML . . . . . . . . . . . . . 406
Alexander Aiken and
Brian R. Murphy Implementing Regular Tree Expressions 427
Fritz Henglein Efficient Type Inference for
Higher-Order Binding-Time Analysis . . . 448
Carsten Kehler Holst Finiteness Analysis . . . . . . . . . . 473
Charles Consel and
Olivier Danvy For a Better Support of Static Data Flow 496
Tzi-cker Chiueh An Architectural Technique for
Cache-level Garbage Collection . . . . . 520
Paul S. Barth and
Rishiyur S. Nikhil and
Arvind M-Structures: Extending a Parallel,
Non-strict, Functional Language with
State . . . . . . . . . . . . . . . . . 538
Michael L. Heytens and
Rishiyur S. Nikhil List Comprehensions in Agna, A Parallel
Persistent Object System . . . . . . . . 569
Sjaak Smetsers and
Eric Nocker and
John van Groningen and
Rinus Plasmeijer Generating Efficient Code for Lazy
Functional Languages . . . . . . . . . . 592
John Hannan Making Abstract Machines Less Abstract 618
Simon L. Peyton Jones and
John Launchbury Unboxed Values as First Class Citizens
in a Non-Strict Functional Language . . 636
C. Andre Delays in synchronized elementary net
systems . . . . . . . . . . . . . . . . 1
J. C. Bradfield Proving temporal properties of Petri
Nets . . . . . . . . . . . . . . . . . . 29
H. Carstensen The complexity of testing the
equivalence of transition sequences . . 48
G. Chehaibar Use of reentrant nets in modular
analysis of colored nets . . . . . . . . 58
J. Desel On abstractions of nets . . . . . . . . 78
C. Dimitrovici and
U. Hummert and
L. Petrucci Semantics, composition and net
properties of algebraic high-level nets 93
J. Esparza and
M. Silva Top-down synthesis of live and bounded
free choice nets . . . . . . . . . . . . 118
R. di Giovanni Hood nets . . . . . . . . . . . . . . . 140
R. P. Hopkins Distributable nets . . . . . . . . . . . 161
F. Itter and
C. Relewicz Computer supported design of Kanban
controlled production . . . . . . . . . 188
R. Janicki and
M. Koutny Optimal simulations, nets and
reachability graphs . . . . . . . . . . 205
V. O. Pinci and
R. M. Shapiro An integrated software development
methodology based on hierarchical
colored Petri nets . . . . . . . . . . . 227
E. Smith On net systems generated by process
foldings . . . . . . . . . . . . . . . . 253
Y. Souissi On liveness preservation by composition
of nets via a set of places . . . . . . 277
R. Valette and
B. Bako Software implementation of Petri nets
and compilation of rule-based systems 296
H. Plunnecke and
W. Reisig Bibliography on Petri nets 1990 . . . . 317
Th. Ottmann Geometric Algorithms and Their
Complexity . . . . . . . . . . . . . . . 3
H.-P. Kriegel and
Th. Brinkhoff and
R. Schneider The Combination of Spatial Access
Methods and Computational Geometry in
Geographic Database Systems . . . . . . 5
J. P. Cheiney and
A. Touir FI-Quadtree: A New Data Structure for
Content-Oriented Retrieval and Fuzzy
Search . . . . . . . . . . . . . . . . . 23
F. J. Radermacher The Importance of Metaknowledge for
Environmental Information Systems . . . 35
A. Gupta and
T. E. Weymouth and
R. Jain An Extended Object-Oriented Data Model
for Large Image Bases . . . . . . . . . 45
Q. Zhou and
B. J. Garner On the Integration for GIS and Remotely
Sensed Data: Towards an Integrated
System to Handle the Large Volume of
Spatial Data . . . . . . . . . . . . . . 63
A. Voisard Towards a Toolbox for Geographic User
Interfaces . . . . . . . . . . . . . . . 75
D. Calcinelli and
M. Mainguenaud The Management of the Ambiguities in a
Graphical Query Language for
Geographical Information Systems . . . . 99
P. Svensson and
H. Zhexue Geo-SAL: A Query Language for Spatial
Data Analysis . . . . . . . . . . . . . 119
M. J. Egenhofer Reasoning About Binary Topological
Relations . . . . . . . . . . . . . . . 143
S. Dutta Topological Constraints: A
Representational Framework for
Approximative Spatial and Temporal
Reasoning . . . . . . . . . . . . . . . 161
D. B. Lomet Grow and Post Index Trees: Role,
Techniques and Future Potential . . . . 183
K.-J. Li and
R. Laurini The Spatial Locality and a Spatial
Indexing Method by Dynamic Clustering in
Hypermap Systems . . . . . . . . . . . . 207
A. U. Frank Properties of Geographic Data:
Requirements for Spatial Access Methods 225
E. G. Hoel and
H. Samet Efficient Processing of Spatial Queries
in Line Segment Databases . . . . . . . 237
H.-P. Kriegel and
H. Horn and
M. Schiwietz The Performance of Object Decomposition
Techniques for Spatial Query Processing 257
B. Seeger Performance Comparison of Segment Access
Methods Implemented on Top of the
Buddy-Tree . . . . . . . . . . . . . . . 277
W. G. Aref and
H. Samet Extending a DBMS with Spatial Operations 299
R. A. Lorie The Use of a Complex Object Language in
Geographic Data Management . . . . . . . 319
S. Shekhar and
T. A. Yang Motion in a Geographical Database System 339
G. Vanecek and
V. Ferrucci A Spatial Index for Convex Simplical
Complexes in d Dimensions . . . . . . . 361
J. Orenstein An Algorithm for Computing the Overlay
of $k$-Dimensional Spaces . . . . . . . 381
W. de Jong and
A. Schijf and
P. Scheuermann Encoding and Manipulating Pictorial Data
with $ {S}^+ $-Trees . . . . . . . . . . 401
L. M. Haas and
W. F. Cody Exploiting Extensible DBMS in Integrated
Geographic Information Systems . . . . . 423
H. Lu and
B. C. Ooi and
A. D'Souza and
C. C. Low Storage Management in Geographic
Information Systems . . . . . . . . . . 451
H. Samet Panel: Why Does GIS Industry Ignore
University Research? . . . . . . . . . . 471
Gordon Plotkin A Semantics for Type Checking . . . . . 1
Paola Giannini and
Simona Ronchi Della Rocca Type Inference in Polymorphic Type
Discipline . . . . . . . . . . . . . . . 18
Makoto Tatsuta Monotone Recursive Definition of
Predicates and Its Realizability
Interpretation . . . . . . . . . . . . . 38
Masahiko Sato Adding Proof Objects and Inductive
Definition Mechanisms to Frege
Structures . . . . . . . . . . . . . . . 53
Wesley Phoa From Term Models to Domains . . . . . . 88
Carl A. Gunter and
Elsa L. Gunter and
David B. MacQueen An Abstract Interpretation for ML
Equality Kinds . . . . . . . . . . . . . 112
Trevor Jim and
Albert R. Meyer Full Abstraction and the Context Lemma 131
S. Arun-Kumar and
M. Hennessy An Efficiency Preorder for Processes . . 152
Alexander Rabinovich and
Boris A. Trakhtenbrot On Nets, Algebras and Modularity . . . . 176
Bengt Jonsson and
Joost N. Kok Towards a Complete Hierarchy of
Compositional Dataflow Models . . . . . 204
Robert L. Constable Type Theory as a Foundation for Computer
Science . . . . . . . . . . . . . . . . 226
A. Pnueli and
M. Shalev What is in a Step: On the Semantics of
Statecharts . . . . . . . . . . . . . . 244
Krzysztof R. Apt and
Dino Pedreschi Proving Termination of General Prolog
Programs . . . . . . . . . . . . . . . . 265
John C. Mitchell On Abstraction and the Expressive Power
of Programming Languages . . . . . . . . 290
Kazuhiro Fuchi and
Koichi Furukawa Role of Logic Programming in the FGCS
Project . . . . . . . . . . . . . . . . 311
M. Abadi and
M. Burrows and
C. Kaufman and
B. Lampson Authentication and Delegation with
Smart-cards . . . . . . . . . . . . . . 326
Bernhard Steffen Data Flow Analysis as Model Checking . . 346
Phil Pfeiffer and
Rebecca Parsons Selke On the Adequacy of Dependence-Based
Representations for Programs with Heaps 365
Masami Hagiya From Programming-by-Example to
Proving-by-Example . . . . . . . . . . . 387
Jean-Louis Lassez From LP to LP: Programming with
Constraints . . . . . . . . . . . . . . 420
Dieter Armbruster Polynomial Recursion Analysis in Pascal
Like Programs . . . . . . . . . . . . . 447
Hardi Hungar Complexity of Proving Program
Correctness . . . . . . . . . . . . . . 459
David A. Basin and
Douglas J. Howe Some Normalization Properties of
Martin-Lof's Type Theory, and
Applications . . . . . . . . . . . . . . 475
Ryu Hasegawa Parametricity of Extensionally Collapsed
Term Models of Polymorphism and Their
Categorical Properties . . . . . . . . . 495
Shin-ya Nishizaki Programs with Continuations and Linear
Logic . . . . . . . . . . . . . . . . . 513
David Walker pi-Calculus Semantics of Object-Oriented
Programming Languages . . . . . . . . . 532
Andreas V. Hense Wrapper Semantics of an Object-Oriented
Programming Language with State . . . . 548
Mark Ryan and
Jose Fiadeiro and
Tom Maibaum Sharing Actions and Attributes in Modal
Action Logic . . . . . . . . . . . . . . 569
Ralf Treinen First Order Data Types and First Order
Logic . . . . . . . . . . . . . . . . . 594
Max I. Kanovich Efficient Program Synthesis: Semantics,
Logic, Complexity . . . . . . . . . . . 615
Sachio Hirokawa Principal Type-Schemes of
BCI-Lambda-Terms . . . . . . . . . . . . 633
Franco Barbanera and
Mariangiola Dezani-Ciancaglini Intersection and Union Types . . . . . . 651
John C. Reynolds The Coherence of Languages with
Intersection Types . . . . . . . . . . . 675
Susumu Hayashi Singleton, Union and Intersection Types
for Program Extraction . . . . . . . . . 701
Pierre-Louis Curien and
Giorgio Ghelli Subtyping + Extensionality: Confluence
of betaeta top reduction in Flsim . . . 731
Luca Cardelli and
Simone Martini and
John C. Mitchell and
Andre Scedrov An Extension of system F with Subtyping 750
Dana S. Scott Will Logicians be Replaced by Machines?
(Abstract) . . . . . . . . . . . . . . . 771
P. America Formal Techniques for Parallel
Object-Oriented Languages . . . . . . . 1
A. Bouali and
R. de Simone Causal Models for Rational Algebraic
Processes . . . . . . . . . . . . . . . 18
R. De Nicola Action and State-based Logics for
Process Algebras . . . . . . . . . . . . 20
J.-C. Fernandez and
L. Mounier A Tool Set for Deciding Behavioral
Equivalences . . . . . . . . . . . . . . 23
U. Goltz Causality Based Models for the Design of
Concurrent Systems . . . . . . . . . . . 43
R. Milner and
J. Parrow and
D. Walker Modal Logics for Mobile Processes . . . 45
E.-R. Olderog Towards a Design Calculus for
Communicating Programs . . . . . . . . . 61
L. Aceto and
A. Ingolfsdottir A Theory of Testing for ACP . . . . . . 78
J. C. M. Baeten and
J. A. Bergstra Real Space Process Algebra . . . . . . . 96
F. S. de Boer and
J. N. Kok and
C. Palamidessi and
J. J. M. M. Rutten The Failure of Failures in a Paradigm
for Asynchronous Communication . . . . . 111
F. S. de Boer and
C. Palamidessi Embedding as a Tool for Language
Comparison: On the CSP Hierarchy . . . . 127
J. Camilleri A Conditional Operator for CCS . . . . . 142
N. J. Drost Algebraic Formulations of Trace Theory 157
J. Esparza and
M. Silva Compositional Synthesis of Live and
Bounded Free Choice Petri Nets . . . . . 172
G. L. Ferrari and
U. Montanari The Observation Algebra of Spatial
Pomsets . . . . . . . . . . . . . . . . 188
N. Francez and
I. R. Forman Synchrony Loosening Transformations for
Interacting Processes . . . . . . . . . 203
K. J. Goldman A Compositional Model for Layered
Distributed Systems . . . . . . . . . . 220
J. F. Groote and
A. Ponse Process Algebra with Guards . . . . . . 235
O. Grumberg and
D. E. Long Model Checking and Modular Verification 250
J. Gunawardena Geometric Logic, Causality and Event
Structures . . . . . . . . . . . . . . . 266
J.-M. Jacquet and
L. Monteiro Extended Horn Clauses: the Framework and
some Semantics . . . . . . . . . . . . . 281
W. Janssen and
M. Poel and
J. Zwiers Action Systems and Action Refinement in
the Development of Parallel Systems . . 298
R. Janicki and
M. Koutny Invariant Semantics of Nets with
Inhibitor Arcs . . . . . . . . . . . . . 317
A. Jeffrey Abstract timed Observation and Process
Algebra . . . . . . . . . . . . . . . . 332
B. Jonsson Simulations between Specifications of
Distributed Systems . . . . . . . . . . 346
R. Kaivola and
A. Valmari Using Truth-Preserving Reductions to
Improve the Clarity of Kripke-Models . . 361
A. S. Klusener Completeness in Real Time Process
Algebra . . . . . . . . . . . . . . . . 376
P. Krishnan Distributed CCS . . . . . . . . . . . . 393
M. Merritt and
F. Modugno and
M. R. Tuttle Time-Constrained Automata . . . . . . . 408
F. Moller and
C. Tofts Relating Processes With Respect to Speed 424
D. Murphy Testing, Betting and Timed True
Concurrency . . . . . . . . . . . . . . 439
D. Nolte and
L. Priese Fairness in Models with True Concurrency 455
H. Qin Efficient Verification of Determinate
Processes . . . . . . . . . . . . . . . 470
Ph. Schnoebelen Experiments on Processes with
Backtracking . . . . . . . . . . . . . . 480
P. Spruit and
R. Wieringa Some Finite-graph Models for Process
Algebra . . . . . . . . . . . . . . . . 495
K. Stolen A Method for the Development of Totally
Correct Shared-State Parallel Programs 510
A. Valmari and
M. Clegg Reduced Labelled Transition Systems Save
Verification Effort . . . . . . . . . . 526
A. W. Appel and
D. B. MacQueen Invited Lecture: Standard ML of New
Jersey . . . . . . . . . . . . . . . . . 1
L. Naish Adding Equations to NU-Prolog . . . . . 15
S. Yamasaki Extraction of Functional from Logic
Program . . . . . . . . . . . . . . . . 27
H. Kredel The Mas Specification Component . . . . 39
T. C. N. Graham and
G. Kock Domesticating Imperative Constructs so
that They Can Live in a Functional World 51
A. Poetzsch-Heffter Logic-Based Specification of Visibility
Rules . . . . . . . . . . . . . . . . . 63
M. A. Ertl and
A. Krall Optimal Instruction Scheduling Using
Constraint Logic Programming . . . . . . 75
F. Baiardi and
D. M. Di Bella An Architectural Model for
OR-Parallellism on Distributed Memory
Systems . . . . . . . . . . . . . . . . 87
K. G. Langendoen and
W. G. Vree FRATS: A Parallel Reduction Strategy for
Shared Memory . . . . . . . . . . . . . 99
M. Alpuente and
M. Falaschi Narrowing as an Incremental Constraint
Satisfaction Algorithm . . . . . . . . . 111
M. M. T. Chakravarty and
H. C. R. Lock The Implementation of Lazy Narrowing . . 123
C. Consel and
Cheng Khoo Siau Semantics-Directed Generation of a
Prolog Compiler . . . . . . . . . . . . 135
E. Boerger and
B. Demoen A Framework to Specify Database Update
Views for Prolog . . . . . . . . . . . . 147
S. Ferenczi Concepts for a Modular and Distributed
Prolog Language . . . . . . . . . . . . 159
A. Davison From Parlog to Polka in Two Easy Steps 171
A. Aasa Precedences in Specifications and
Implementations of Programming Languages 183
C. W. Kebler and
W. J. Paul and
T. Rauber A Randomized Heuristic Approach to
Register Allocation . . . . . . . . . . 195
N. Halbwachs and
P. Raymond and
C. Ratel Generating Efficient Code from Data-Flow
Programs . . . . . . . . . . . . . . . . 207
C. H. A. Koster and
J. G. Beney On the Borderline Between Grammars and
Programs . . . . . . . . . . . . . . . . 219
H. Vogt and
D. Swierstra and
M. Kuiper Efficient Incremental Evaluation of
Higher Order Attribute Grammars . . . . 231
J. Paakki PROFIT: A System Integrating Logic
Programming and Attribute Grammars . . . 243
H. Ait-Kaci and
A. Podelski Invited Lecture: Towards a Meaning of
LIFE . . . . . . . . . . . . . . . . . . 255
P. Y. Gloess U-Log, an Ordered Sorted Logic with
Typed Attributes . . . . . . . . . . . . 275
W. Chen and
D. S. Warren Compilation of Predicate Abstractions in
Higher-Order Logic Programming . . . . . 287
U. Nilsson Abstract Interpretation: A Kind of Magic 299
G. File and
P. Sottero Abstract Interpretation for Type
Checking . . . . . . . . . . . . . . . . 311
F. Giannotti and
M. Hermenegildo A Technique for Recursive Invariance
Detection and Selective Program
Specialization . . . . . . . . . . . . . 323
R. Loogen and
S. Winkler Dynamic Detection of Determinism in
Functional Logic Languages . . . . . . . 335
M. Proietti and
A. Pettorossi Unfolding-Definition-Folding, in this
Order, for Avoiding Unnecessary
Variables in Logic Programs . . . . . . 347
P. H. Cheong and
L. Fribourg Efficient Integration of Simplification
into Prolog . . . . . . . . . . . . . . 359
S. Antoy Lazy Evaluation in Logic . . . . . . . . 371
J. Boye S-SLD-Resolution --- An Operational
Semantics for Logic Programs with
External Procedures . . . . . . . . . . 383
P. Van Hentenryck and
Y. Deville Operational Semantics of Constraint
Logic Programming over Finite Domains 395
A. Brogi and
M. Gabbrielli Constraints for Synchronizing
Coarse-grained Sequential Logic
Processes . . . . . . . . . . . . . . . 407
D. Loyola Extending Execution Trees for Debugging
and Animation in Logic Programming . . . 419
U. Fraus and
H. HuBmann A Narrowing-Based Theorem Prover . . . . 421
M. Hanus The ALF System . . . . . . . . . . . . . 423
J. Vollmer Experiences with Gentle: Efficient
Compiler Construction Based on Logic
Programming . . . . . . . . . . . . . . 425
B. Baum and
P. Forbrig The System FLR (Fast Laboratory for
Recomposition) . . . . . . . . . . . . . 427
G. Attardi and
M. Gaspari Multilanguage Interoperability . . . . . 429
B. Legeard and
E. Legros Short Overview of the CLPS System . . . 431
E. Allender and
V. Gore On Strong Separations from $ {AC}^0 $ 1
J. Buchmann Number Theoretic Algorithms and
Cryptology . . . . . . . . . . . . . . . 16
J.-y. Cai Computations Over Infinite Groups . . . 22
S. Heinrich Efficiency of Monte Carlo Algorithms in
Numerical Analysis . . . . . . . . . . . 33
M. Karpinski Approximation Algorithms for Counting
Problems in Finite Fields . . . . . . . 45
A. A. Razborov Lower Bounds for Deterministic and
Nondeterministic Branching Programs . . 47
R. Reischuk Graph Theoretical Methods for the Design
of Parallel Algorithms . . . . . . . . . 61
C. P. Schnorr and
M. Euchner Lattice Basis Reduction: Improved
Practical Algorithms and Solving Subset
Sum Problems . . . . . . . . . . . . . . 68
J. F. Traub Information-Based Complexity: Recent
Results and Open Problems . . . . . . . 86
G. Turan A Survey of Some Aspects of
Computational Learning Theory . . . . . 89
C. Baier and
M. E. Majster-Cederbaum The Consistency of a Noninterleaving and
an Interleaving Model for Full TCSP . . 105
B. Bank and
T. Krick and
R. Mandel and
P. Solerno A Geometrical Bound for Integer
Programming with Polynomial Constraints 121
E. Barcucci and
R. Pinzani and
E. Rodella and
R. Sprugnoli A Characterization of Binary Search
Networks . . . . . . . . . . . . . . . . 126
D. Beauquier and
M. Nivat and
D. Niwinski About the Effect of the Number of
Successful Paths in an Infinite Tree on
the Recognizability by a Finite
Automaton with Buchi Conditions . . . . 136
L. Breveglieri and
C. Citrini and
S. Crespi-Reghizzi Deterministic Dequeue Automata and LL(1)
Parsing of Breadth-Depth Grammars . . . 146
D. Bruschi and
G. Pighizzini The Complexity of Computing Maximal Word
Functions . . . . . . . . . . . . . . . 157
G. Buntrock and
B. Jenner and
K.-J. Lange and
P. Rossmanith Unambiguity and Fewness for Logarithmic
Space . . . . . . . . . . . . . . . . . 168
M. Chardin Differential Resultants and
Subresultants . . . . . . . . . . . . . 180
B. S. Chlebus and
I. Vrto Unifying Binary-Search Trees and
Permutations . . . . . . . . . . . . . . 190
J. Dassow and
K.-J. Lange Computational Complexity and Hardest
Languages of Automata with Abstract
Storages . . . . . . . . . . . . . . . . 200
E. Fachini and
A. Monti and
M. Napoli and
D. Parente Systolic Y-Tree Automata: Closure
Properties and Decision Problems . . . . 210
H. D. Groger A New Partition Lemma for Planar Graphs
and its Application to Circuit
Complexity . . . . . . . . . . . . . . . 220
T. Hofmeister and
W. Hohberg and
S. Kohling Some Notes on Threshold Circuits, and
Multiplication in Depth 4 . . . . . . . 230
J. Hromkovic Nonlinear Lower Bounds on the Number of
Processors of Circuits with Sublinear
Separators . . . . . . . . . . . . . . . 240
O. H. Ibarra and
N. Q. Tran On Space-Bounded Synchronized
Alternating Turing Machines . . . . . . 248
A. Joux and
J. Stern Improving the Critical Density of the
Lagarias--Odlyzko Attack Against Subset
Sum Problems . . . . . . . . . . . . . . 258
S. Jukna Optimal versus Stable in Boolean
Formulae . . . . . . . . . . . . . . . . 265
M. Kaib The GauBeta Lattice Basis Reduction
Algorithm Succeeds With Any Given Norm 275
J. Kaneps Regularity of One-Letter Languages
Acceptable by 2-Way Finite Probabilistic
Automata . . . . . . . . . . . . . . . . 287
P. Knijnenburg and
J. N. Kok On the Semantics of Atomized Statements:
The Parallel-Choice Option . . . . . . . 297
E. Kounalis and
M. Rusinowitch Automatic Proof Methods for Algebraic
Specifications . . . . . . . . . . . . . 307
D. Kratsch and
L. A. Hemachandra On the Complexity of Graph
Reconstruction . . . . . . . . . . . . . 318
C. Levcopoulos and
O. Petersson An Optimal Adaptive In-Place Sorting
Algorithm . . . . . . . . . . . . . . . 329
G. Louchard and
C. Kenyon and
R. Schott Data Structures Maxima . . . . . . . . . 339
C. Martinez Average-Case Analysis of Equality of
Binary Trees Under the BST Probability
Model . . . . . . . . . . . . . . . . . 350
J. Neraud On the Subsets of Rank Two in a Free
Monoid: A Fast Decision Algorithm . . . 360
W. Plandowski and
W. Rytter and
T. Szymacha Exact Analysis of Three Tree Contraction
Algorithms . . . . . . . . . . . . . . . 370
K. Salomaa and
S. Yu Degrees of Nondeterminism for Pushdown
Automata . . . . . . . . . . . . . . . . 380
H. Schroder and
O. Sykora and
I. Vrto Optimal Embedding of a Toroidal Array in
a Linear Array . . . . . . . . . . . . . 390
D. Uhlig Boolean Functions with a Large Number of
Subfunctions and Small Complexity and
Depth . . . . . . . . . . . . . . . . . 395
R. S. Valiveti and
B. J. Oommen and
J. R. Zgierski Adaptive Linear List Reorganisation for
a System Processing Set Queries . . . . 405
E. Wanke On the Decidability of Integer Subgraph
Problems on Context-Free Graph Languages 415
T. Ehrhard and
P. Malacaria Stone Duality for Stable Functions . . . 1
R. M. Amadio Bifinite Domains: Stable Case . . . . . 16
R. D. Tennent Local Variables and Non-Interference in
Algol-like Languages . . . . . . . . . . 34
A. Edalat and
M. B. Smyth Categories of Information Systems . . . 37
R. Hoofman and
H. Schellinx Collapsing Graph Models by Preorders . . 53
P. W. O'Hearn Linear Logic and Interference Control 74
A. Burroni Higher Dimensional Word Problem . . . . 94
S. Hirokawa BCK-Formulas Having Unique Proofs . . . 106
R. Blute Proof Nets and Coherence Theorems . . . 121
E. Moggi A Modular Approach to Denotational
Semantics . . . . . . . . . . . . . . . 138
G. Jarzembski Programs in Partial Algebras --- a
Categorical Approach . . . . . . . . . . 140
C. B. Jay Tail Recursion from Universal Invariants 151
T. Coquand A Direct Proof of the Intuitionistic
Ramsey Theorem . . . . . . . . . . . . . 164
D. Pavlovic Constructions and Predicates . . . . . . 173
B. Jacobs and
E. Moggi and
T. Streicher Relating Models of Impredicative Type
Theories . . . . . . . . . . . . . . . . 197
W. Phoa Two Results on Set-Theoretic
Polymorphism . . . . . . . . . . . . . . 219
A. Corradini and
U. Montanari An Algebra of Graphs and Graph Rewriting 236
E. W. Stark Dataflow Networks are Fibrations . . . . 261
P. Degano and
S. Kasangian and
S. Vigna Applications of the Calculus of Trees to
Process Description Languages . . . . . 282
Edmund M. Clarke Temporal Logic Model Checking: Two
Techniques for Avoiding the State
Explosion Problem . . . . . . . . . . . 1
Hans Eveking Automatic Verification of Extensions of
Hardware Descriptions . . . . . . . . . 2
G. Berthelot and
C. Johnen and
Laure Petrucci PAPETRI: Environment for the Analysis of
Petri Nets . . . . . . . . . . . . . . . 13
Olivier Coudert and
Jean Christophe Madre and
Christian Berthet Verifying Temporal Properties of
Sequential Machines Without Building
their State Diagrams . . . . . . . . . . 23
Randal E. Bryant and
Carl-Johan Seger Formal Verification of Digital Circuits
Using Symbolic Ternary System Models . . 33
Hiromi Hiraishi and
Shintaro Meki and
Kiyoharu Hamaguchi Vectorized Model Checking for
Computation Tree Logic . . . . . . . . . 44
Carl Pixley Introduction to a Computational Theory
and Implementation of Sequential
Hardware Equivalence . . . . . . . . . . 54
Valerie Roy and
Robert de Simone Auto/Autograph . . . . . . . . . . . . . 65
Hiroshi Nakamura and
Yuji Kukimoto and
Masahiro Fujita and
Hidehiko Tanaka A Data Path Verifier for Register
Transfer Level Using Temporal Logic
Language Tokio . . . . . . . . . . . . . 76
Paolo Camurati and
M. Gilli and
P. Prinetto and
M. Sonza Reorda The Use of Model Checking in ATPG for
Sequential Circuits . . . . . . . . . . 86
Jean Christophe Lloret and
Pierre Azema and
Francois Vernadat Compositional Design and Verification of
Communication Protocols, Using Labelled
Petri Nets . . . . . . . . . . . . . . . 96
Linda Ness Issues Arising in the Analysis of L.0 106
Michel Langevin Automated RTL Verification Based on
Predicate Calculus . . . . . . . . . . . 116
Richard Lai and
Ken R. Parker and
T. S. Dillon On Using Protean To Verify ISO FTAM
Protocol . . . . . . . . . . . . . . . . 126
E. Allen Emerson and
A. K. Mok and
A. Prasad Sistla and
Jai Srinivasan Quantitative Temporal Reasoning . . . . 136
David K. Probst and
Hon F. Li Using Partial-Order Semantics to Avoid
the State Explosion Problem in
Asynchronous Systems . . . . . . . . . . 146
Antti Valmari A Stubborn Attack On State Explosion . . 156
Ryszard Janicki and
Maciej Koutny Using Optimal Simulations to Reduce
Reachability Graphs . . . . . . . . . . 166
Patrice Godefroid Using Partial Orders to Improve
Automatic Verification Methods . . . . . 176
Susanne Graf and
Bernhard Steffen Compositional Minimization of Finite
State Systems . . . . . . . . . . . . . 186
A. Bouajjani and
Jean-Claude Fernandez and
Nicholas Halbwachs Minimal Model Generation . . . . . . . . 197
Bernhard Josko A Context Dependent Equivalence Relation
Between Kripke Structures . . . . . . . 204
Gil Shurek and
Orna Grumberg The Modular Framework of Computer-Aided
Verification . . . . . . . . . . . . . . 214
Jerry R. Burch Verifying Liveness Properties by
Verifying Safety Properties . . . . . . 224
Costas Courcoubetis and
Moshe Vardi and
Pierre Wolper and
Mihalis Yannakakis Memory Efficient Algorithms for the
Verification of Temporal Properties . . 233
Peng Wuxu and
S. Purushothaman A Unified Approach to the Deadlock
Detection Problem in Networks of
Communicating Finite State Machines . . 243
Kiyoharu Hamaguchi and
Hiromi Hiraishi and
Shuzo Yajima Branching Time Regular Temporal Logic
for Model Checking with Linear Time
Complexity . . . . . . . . . . . . . . . 253
Victor Yodaiken The Algebraic Feedback Product of
Automata . . . . . . . . . . . . . . . . 263
Howard Wong-Toi and
David L. Dill Synthesizing Processes and Schedulers
from Temporal Specifications . . . . . . 272
Christian H. Golaszewski and
Robert P. Kurshan Task-Driven Supervisory Control of
Discrete Event Systems . . . . . . . . . 282
Ugo Buy and
Robert Moll A Proof Lattice-Based Technique for
Analyzing Liveness of Resource
Controllers . . . . . . . . . . . . . . 292
Paul Loewenstein and
David L. Dill Verification of a Multiprocessor Cache
Protocol Using Simulation Relations and
Higher-Order Logic . . . . . . . . . . . 302
David A. Carrington and
K. A. Robinson Computer Assistance for Program
Refinement . . . . . . . . . . . . . . . 312
James M. Morris and
Mark Howard Program Verification by Symbolic
Execution of Hyperfinite Ideal Machines 322
Michel Barbeau and
Gregor V. Bochmann Extension of the Karp and Miller
Procedure to Lotos Specifications . . . 333
Mark B. Josephs and
Jan Tijmen Udding An Algebra for Delay-Insensitive
Circuits . . . . . . . . . . . . . . . . 343
Eric Madelaine and
Didier Vergamini Finiteness Conditions and Structural
Construction of Automata for All Process
Algebras . . . . . . . . . . . . . . . . 353
Rance Cleaveland On Automatically Explaining Bisimulation
Inequivalence . . . . . . . . . . . . . 364
F. Drewes and
H.-J. Kreowski A Note on Hyperedge Replacement . . . . 1
J. Engelfriet and
G. Rozenberg Graph Grammars Based on Node Rewriting:
An Introduction to NLC Graph Grammars 12
H. Ehrig and
M. Korff and
M. Lowe Tutorial Introduction to the Algebraic
Approach of Graph Grammars Based on
Double and Single Pushouts . . . . . . . 24
B. Courcelle The Logical Expression of Graph
Properties (Abstract) . . . . . . . . . 38
Anonymous Panel Discussion: The Use of Graph
Grammars in Applications . . . . . . . . 41
M. Himsolt $ \mbox {Graph}^{\mbox {Ed}} $: An
Interactive Tool for Developing Graph
Grammars . . . . . . . . . . . . . . . . 61
A. Schurr IPSEN-Environment: An Integrated and
Incremental Project Support ENvironment 66
A. Schurr PROGRESS-Editor: A Text-Oriented Hybrid
Editor for PROgrammed Graph REwriting
SyStems . . . . . . . . . . . . . . . . 67
E. Wanke PLEXUS: Tools for Analyzing Graph
Grammars . . . . . . . . . . . . . . . . 68
S. Arnborg and
B. Courcelle and
A. Proskurowski and
D. Seese An Algebraic Theory of Graph Reduction 70
D. A. Bailey and
J. E. Cuny and
C. D. Fisher Programming with Very Large Graphs . . . 84
K. Barthelmann Describing Gottler's Operational Graph
Grammars with Pushouts . . . . . . . . . 98
M. Bauderon General Solution to a System of
Recursive Equations on Hypergraphs . . . 113
M. J. M. de Boer Construction of Map OL-Systems for
Developmental Sequences of Plant Cell
Layers . . . . . . . . . . . . . . . . . 127
F. J. Brandenburg Layout Graph Grammars: The Placement
Approach . . . . . . . . . . . . . . . . 144
F. J. Brandenburg and
M. P. Chytil Cycle Chain Code Picture Languages . . . 157
H. Bunke and
T. Glauser and
T.-H. Tran An Efficient Implementation of Graph
Grammars Based on the RETE Matching
Algorithm . . . . . . . . . . . . . . . 174
D. Caucal An Application of Graph Grammars to the
Elimination of Redundancy from Functions
Defined by Schemes . . . . . . . . . . . 190
T. C. Chen Graphic Equivalence and Computer
Optimization . . . . . . . . . . . . . . 207
A. Corradini and
U. Montanari and
F. Rossi and
H. Ehrig and
M. Lowe Graph Grammars and Logic Programming . . 221
B. Courcelle Graphs as Relational Structures: An
Algebraic and Logical Approach . . . . . 238
B. Courcelle and
J. Engelfriet and
G. Rozenberg Context-free Handle-rewriting Hypergraph
Grammars . . . . . . . . . . . . . . . . 253
H. Ehrig and
A. Habel and
H.-J. Kreowski and
F. Parisi-Presicce From Graph Grammars to High Level
Replacement Systems . . . . . . . . . . 269
H. Ehrig and
F. Parisi-Presicce Algebraic Specification Grammars: A
Junction between Module Specifications
and Graph Grammars . . . . . . . . . . . 292
J. Engelfriet A Characterization of Context-Free NCE
Graph Languages by Monadic Second-Order
Logic on Trees . . . . . . . . . . . . . 311
J. Engelfriet and
L. Heyker The Term Generating Power of
Context-Free Hypergraph Grammars . . . . 328
G. Engels Elementary Actions on an Extended
Entity-Relationship Database . . . . . . 344
F. D. Fracchia and
P. Prusinkiewicz Physically-Based Graphical
Interpretation of Marker Cellwork L-
Systems . . . . . . . . . . . . . . . . 363
J. R. W. Glauert and
J. R. Kennaway and
M. R. Sleep Dactl: An Experimental Graph Rewriting
Language . . . . . . . . . . . . . . . . 378
H. Gottler and
J. Gunther and
G. Nieskens Use Graph Grammars to Design
CAD-Systems! . . . . . . . . . . . . . . 396
A. Habel and
H.-J. Kreowski Collage Grammars . . . . . . . . . . . . 411
L. Hess and
B. Mayoh The Four Musicians: Analogies and Expert
Systems --- A Graphic Approach . . . . . 430
D. Janssens and
G. Rozenberg Structured Transformations and
Computation Graphs for Actor Grammars 446
E. Jeltsch and
H.-J. Kreowski Grammatical Inference Based on Hyperedge
Replacement . . . . . . . . . . . . . . 461
S. M. Kaplan and
J. P. Loyall and
S. K. Goering Specifying Concurrent Languages and
Systems with Delta-Grammars . . . . . . 475
R. Kennaway Graph Rewriting in Some Categories of
Partial Morphisms . . . . . . . . . . . 490
M. Korff Application of Graph Grammars to
Rule-Based Systems . . . . . . . . . . . 505
C. Lautemann Tree Automata, Tree Decomposition and
Hyperedge Replacement . . . . . . . . . 520
U. Lichtblau Recognizing Rooted Context-free
Flowgraph Languages in Polynomial Time 538
I. Litovsky and
Y. Metivier Computing with Graph Relabelling Systems
with Priorities . . . . . . . . . . . . 549
H. B. Luck and
J. Luck Double-Wall Cellwork Systems for Plant
Meristems . . . . . . . . . . . . . . . 564
A. Maggiolo-Schettini and
J. Winkowski Programmed Derivations of Relational
Structures . . . . . . . . . . . . . . . 582
M. Nagl and
A. Schurr A Specification Environment for Graph
Grammars . . . . . . . . . . . . . . . . 599
A. Paz The Theory of Graphoids: A Survey . . . 610
D. Plump Graph-Reducible Term Rewriting Systems 622
A. Rosenfeld A Note on Graph Decimation . . . . . . . 637
A. Schurr PROGRESS: A VHL-Language Based on Graph
Grammars . . . . . . . . . . . . . . . . 641
G. Taentzer and
H. Schween Movement of Objects in Configuration
Spaces Modelled by Graph Grammars . . . 660
W. Vogler Recognizing Edge Replacement Graph
Languages in Cubic Time . . . . . . . . 676
H. Ehrig and
M. Lowe Computing by Graph Transformation:
Overall Aims and New Results . . . . . . 688
Stefan Arnborg and
Andrzej Proskurowski and
Detlef Seese Monadic Second Order Logic, Tree
Automata and Forbidden Minors . . . . . 1
Andreas Blass and
Yuri Gurevich On the Reduction Theory for Average Case
Complexity . . . . . . . . . . . . . . . 17
Egon Borger and
Dean Rosenzweig From Prolog Algebras Towards WAM -- A
Mathematical Study of Implementation . . 31
Egon Borger and
Peter H. Schmitt A Formal Operational Semantics for
Languages of Type Prolog III . . . . . . 67
Wolfram Burgard Efficiency Considerations on
Goal-Directed Forward Chaining for Logic
Programs . . . . . . . . . . . . . . . . 80
Domenico Cantone and
V. Cutello and
J. T. Schwartz Decision Problems for Tarski and
Presburger Arithmetics Extended with
Sets . . . . . . . . . . . . . . . . . . 95
Igor Durdanovic A Fast Garbage Collection Algorithm for
WAM-Based PROLOG . . . . . . . . . . . . 110
Christian Fermuller A Resolution Variant Deciding some
Classes of Clause Sets . . . . . . . . . 128
Andreas Flogel and
Marek Karpinski and
Hans Kleine Buning Subclasses of Quantified Boolean
Formulas . . . . . . . . . . . . . . . . 145
Dov M. Gabbay Algorithmic Proof with Diminishing
Resources Part 1 . . . . . . . . . . . . 156
Andreas Goerdt Cutting Plane versus Frege Proof Systems 174
Etienne Grandjean and
J. M. Robson RAM with Compact Memory: A Realistic and
Robust Model of Computation . . . . . . 195
Karol Habart Randomness and Turing Reducibility
Restraints . . . . . . . . . . . . . . . 234
Reiner Hahnle Towards an Efficient Tableau Proof
Procedure for Multiple-Valued Logics . . 248
Ulrich Hertrampf and
Klaus Wagner Interactive Proof Systems: Provers,
Rounds, and Error Bounds . . . . . . . . 261
Huang Zhisheng Logics for Belief Dependence . . . . . . 274
Jan Jaspars A Generalization of Stability and its
Application to Circumscription of
Positive Introspective Knowledge . . . . 289
Daniel Mundici The Complexity of Adaptive
Error-Correcting Codes . . . . . . . . . 300
Pavel Pudlak Ramsey's Theorem in Bounded Arithmetic 308
Solomampionona Ranaivoson Nontrivial Lower Bounds for some
NP-Problems on Directed Graphs . . . . . 318
Cecylia M. Rauszer Expansions and Models of Autoepistemic
Theories . . . . . . . . . . . . . . . . 340
Robert F. Stark On the Existence of Fixpoints in Moore's
Autoepistemic Logic and the
Non-Monotonic Logic of McDermott and
Doyle . . . . . . . . . . . . . . . . . 354
Manfred E. Szabo On the Tracking of Loops in Automated
Deductions . . . . . . . . . . . . . . . 366
Heribert Vollmer The Gap-Language-Technique Revisited . . 389
G. Barzdins ADT Implementation and Completion by
Induction from Examples . . . . . . . . 1
M. Bettaz An Association of Algebraic Term Nets
and Abstract Data Types for Specifying
Real Communication Protocols . . . . . . 11
S. Clerici and
F. Orejas The Specification Language GSBL . . . . 31
C. Dimitrovici and
U. Hummert Composition of Algebraic High-Level Nets 52
H. Ehrig and
F. Parisi-Presicce A Match Operation for Rule-Based Modular
System Design . . . . . . . . . . . . . 74
M. GroBe-Rhode Towards Object-Oriented Algebraic
Specifications . . . . . . . . . . . . . 98
S. Lange and
K. P. Jantke Inductive Completion for Transformation
of Equational Specifications . . . . . . 117
T. Lehmann A Notion of Implementation for the
Specification Language OBSCURE . . . . . 141
G. Mascari and
A. Vincenzi Model-Theoretic Specifications and
Back-and-Forth Equivalences . . . . . . 166
K. Meinke Universal Algebra in Higher Types
(Extended Abstract) . . . . . . . . . . 185
R. Nieuwenhuis and
F. Orejas Clausal Rewriting: Applications and
Implementation . . . . . . . . . . . . . 204
F. Orejas and
P. Nivela Constraints for Behavioural
Specifications . . . . . . . . . . . . . 220
G. Reggio Entities: An Institution for Dynamic
Systems . . . . . . . . . . . . . . . . 246
H. Reichel A 2-Category Approach to Critical Pair
Completion . . . . . . . . . . . . . . . 266
D. Sannella and
A. Tarlecki A Kernel Specification Formalism with
Higher-Order Parameterisation . . . . . 274
D. Sannella and
A. Tarlecki Extended ML: Past, Present and Future 297
T. Streicher and
M. Wirsing Dependent Types Considered Necessary for
Specification Languages . . . . . . . . 323
E. G. Wagner Generic Types in a Language for Data
Directed Design . . . . . . . . . . . . 341
D. Wolz Design of a Compiler for Lazy Pattern
Driven Narrowing . . . . . . . . . . . . 362
R. Caferra and
M. Herment and
N. Zabel User-oriented theorem proving with the
ATINF graphic proof editor . . . . . . . 2
L. Farinas del Cerro and
A. Herzig A modal analysis of possibility theory 11
D. Gabbay and
A. Hunter Making inconsistency respectable: a
logical framework for inconsistency in
reasoning . . . . . . . . . . . . . . . 19
E. Orlowska Relational proof systems for some AI
logics . . . . . . . . . . . . . . . . . 33
Gh. Paun Formal grammars and cognitive
architectures . . . . . . . . . . . . . 48
J. Wiedermann Efficient simulations of
nondeterministic computations and their
speed-up by the ring of cooperating
machines . . . . . . . . . . . . . . . . 59
M. Freund A semantic characterization of
disjunctive relations . . . . . . . . . 72
A. Hunter Execution of defeasible temporal clauses
for building preferred models . . . . . 84
M. Klopotek On the phenomenon of flattening
``flexible prediction'' concept
hierarchy . . . . . . . . . . . . . . . 99
J. Lang Possibilistic logic as a logical
framework for min-max discrete
optimisation problems and prioritized
constraints . . . . . . . . . . . . . . 112
Z. Markov An approach to data-driven learning . . 127
P. Marquis Extending abduction from propositional
to first-order logic . . . . . . . . . . 141
U. Petermann Building in equational theories into the
connection method . . . . . . . . . . . 156
J. Pfalzgraf Logical fiberings and polycontextural
systems . . . . . . . . . . . . . . . . 170
M. Rusinowitch and
L. Vigneron Automated deduction with associative
commutative operators . . . . . . . . . 185
A. Strasser Towards a lattice of knowledge
representation systems . . . . . . . . . 200
J. Sefranek Inconsistencies handling: nonmonotonic
and paraconsistent reasoning . . . . . . 214
G. Taucaite and
J. Laurinskas An approach to structural synthesis of
data processing programs . . . . . . . . 220
J. Vauzeilles Negation as failure and intuitionistic
three-valued logic . . . . . . . . . . . 227
A. Miola Symbolic Computation and Artificial
Intelligence . . . . . . . . . . . . . . 244
Steve Shafer Keynote Address: Soft Ware for Hard
Physics . . . . . . . . . . . . . . . . 1
Anonymous A Family Album of Software Project
Courses . . . . . . . . . . . . . . . . 3--4
Peter J. Knoke Medium Size Project Model: Variations on
a Theme . . . . . . . . . . . . . . . . 5
Frank W. Calliss and
Debra L. Trantina A Controlled Software Maintenance
Project . . . . . . . . . . . . . . . . 25
Mary Shaw and
James E. Tomayko Models for Undergraduate Project Courses
in Software Engineering . . . . . . . . 33
Anonymous Software Engineering Training in
Government and Industry . . . . . . . . 73--74
R. D. Kelly and
D. L. Lapay and
F. S. Pitcairn The Establishment of an Appropriate
Software Engineering Training Program 75
P. Mann and
A. Mason and
M. T. Norris Industrial Training for Software
Engineers . . . . . . . . . . . . . . . 99
Nancy R. Mead and
Patricia K. Lawlis Software Engineering: Graduate-Level
Courses for AFIT Professional Continuing
Education . . . . . . . . . . . . . . . 114
Anonymous Panel On Curriculum Issues . . . . . . . 127
Bruce H. Barnes and
Jean B. Rogers Computing Curricula 1991 --- Its
Implications for Software Engineering
Education . . . . . . . . . . . . . . . 129
Jonah Z. Lavi and
Ashok Agrawala and
Raymond Buhr and
Ken Jackson and
Michael Jackson and
Bernard Lang Computer Based Systems Engineering
Workshop . . . . . . . . . . . . . . . . 149
Anonymous Software Engineering Teaching Styles . . 165
David Budgen and
Chic Rattray Teaching about Process Issues in
Software Engineering . . . . . . . . . . 167
David Bustard A Layered Approach to Teaching Software
Project Management . . . . . . . . . . . 181
Anonymous Teaching Design . . . . . . . . . . . . 193
J. P. Jacquot and
J. Guyard Seven Lessons to Teach Design . . . . . 195
Linda M. Northrop and
William E. Richardson Design Evolution: Implications for
Academia and Industry . . . . . . . . . 205
Keith Pierce and
Linda Deneen and
Gary Shute Teaching Software Design in the Freshman
Year . . . . . . . . . . . . . . . . . . 219
Anonymous Special Topics in Real Time and
Environments . . . . . . . . . . . . . . 233
Conni Goodman Marchewka Teaching Software Engineering for
Real-Time Design . . . . . . . . . . . . 235
Laurie Honour Werth Industry-Academia Collaboration to
Provide CASE Tools for Software
Engineering Classes . . . . . . . . . . 245
Anonymous Developing Software Engineering
Expertise . . . . . . . . . . . . . . . 257--258
Julian S. Weitzenfeld Developing SE Expertise . . . . . . . . 259
Thomas R. Riedl and
Julian S. Weitzenfeld and
Jared T. Freeman and
Gary A. Klein and
John Musa What We Have Learned About Software
Engineering Expertise . . . . . . . . . 261
Jared T. Freeman and
Thomas R. Riedl and
Julian S. Weitzenfeld and
Gary A. Klein and
John Musa Instruction for Software Engineering
Expertise . . . . . . . . . . . . . . . 271
Julian S. Weitzenfeld and
Thomas R. Riedl and
Jared T. Freeman and
Gary A. Klein and
John Musa Knowledge Elicitation for Software
Engineering Expertise . . . . . . . . . 283
Eli Biham and
Adi Shamir Differential Cryptanalysis of DES-Like
Cryptosystems (Invited Talk), (Extended
Abstract) . . . . . . . . . . . . . . . 2
Henry Gilbert and
Guy Chassé A Statistical Attack of the FEAL-8
Cryptosystem . . . . . . . . . . . . . . 22
Kencheng Zeng and
C. H. Yang and
T. R. N. Rao An Improved Linear Syndrome Algorithm in
Cryptanalysis with Applications . . . . 34
Gilles Brassard and
Claude Crépeau Quantum Bit Commitment and Coin Tossing
Protocols . . . . . . . . . . . . . . . 49
Donald Beaver and
Joan Feigenbaum and
Joe Kilian and
Phillip Rogaway Security with Low Communication Overhead
(Extended Abstract) . . . . . . . . . . 62
Shafi Goldwasser and
Leonid Levin Fair Computation of General Functions in
Presence of Immoral Majority . . . . . . 77
Gilles Brassard and
Moti Yung One-Way Group Actions . . . . . . . . . 94
B. A. LaMacchia and
Andrew M. Odlyzko Solving Large Sparse Linear Systems over
Finite Fields . . . . . . . . . . . . . 109--133
Johannes A. Buchmann and
Stephan Düllmann On the Computation of Discrete
Logarithms in Class Groups (Extended
Abstract) . . . . . . . . . . . . . . . 134
Chih-Chwen C. Chuang and
James George Dunham Matrix Extensions of the RSA Algorithm 140
Neal Koblitz Constructing Elliptic Curve
Cryptosystems in Characteristic 2 . . . 156
Thomas Beth and
Yvo Desmedt Identification Tokens --- or: Solving
the Chess Grandmaster Problem . . . . . 169
Yvo Desmedt and
Moti Yung Arbitrated Unconditionally Secure
Authentication Can Be Unconditionally
Protected against Arbiter's Attacks
(Extended Abstract) . . . . . . . . . . 177
Joan Boyar and
David Chaum and
Ivan Bjerre Damgård and
Torben Pryds Pedersen Convertible Undeniable Signatures . . . 189
David Chaum and
Sandra Roijakkers Unconditionally Secure Digital
Signatures . . . . . . . . . . . . . . . 206
Gustavus J. Simmons Geometric Shared Secret and/or Shared
Control Schemes (invited talk) . . . . . 216
Ernest F. Brickell and
Douglas R. Stinson Some Improved Bounds on the Information
Rate of Perfect Secret Sharing Schemes
(Extended Abstract) . . . . . . . . . . 242
Silvio Micali and
Tal Rabin Collective Coin Tossing Without
Assumptions Nor Broadcasting . . . . . . 253
Yacov Yacobi A Key Distribution ``Paradox'' . . . . . 268
Walter Fumy and
Michael Munzert A Modular Approach to Key Distribution 274
Yuliang Zheng and
Tsutomu Matsumoto and
Hideki Imai Structural Properties of One-Way Hash
Functions . . . . . . . . . . . . . . . 285--302
Ronald L. Rivest The MD4 Message Digest Algorithm . . . . 303--311
Joe Kilian Achieving Zero-Knowledge Robustly . . . 313
Donald Beaver and
Joan Feigenbaum and
Victor Shoup Hiding Instances in Zero-Knowledge Proof
Systems (Extended Abstract) . . . . . . 326
Kaoru Kurosawa and
Shigeo Tsujii Multi-Language Zero-Knowledge
Interactive Proof Systems . . . . . . . 339
Dror Lapidot and
Adi Shamir Publicly Verifiable Non-Interactive
Zero-Knowledge Proofs . . . . . . . . . 353
A. De Santis and
M. Yung Cryptographic Applications of the
Non-Interactive Metaproof and
Many-Prover Systems . . . . . . . . . . 366
Alfredo De Santis and
Moti Yung Cryptographic Applications of the
Non-interactive Metaproof and
Many-Prover Systems (Preliminary
Version) . . . . . . . . . . . . . . . . 366
Joe Kilian Interactive Proofs with Provable
Security Against Honest Verifiers . . . 378
A. W. Schrift and
Adi Shamir On the Universality of the Next Bit Test 394
Ueli M. Maurer A Universal Statistical Test for Random
Bit Generators . . . . . . . . . . . . . 409
James L. McInnes and
Benny Pinkas On the Impossibility of Private Key
Cryptography with Weakly Random Keys . . 421
Stuart Haber and
W. Scott Stornetta How to Time-Stamp a Digital Document . . 437
Tatsuaki Okamoto and
Kazuo Ohta How to Utilize the Randomness of
Zero-Knowledge Proofs (Extended
Abstract) . . . . . . . . . . . . . . . 456
Ralph C. Merkle Fast Software Encryption Functions . . . 476
Dominique de Waleffe and
Jean-Jacques Quisquater CORSAIR: A Smart Card for Public Key
Cryptosystems . . . . . . . . . . . . . 502
Dominique de Waleffe and
Jean-Jacques Quisquater CORSAIR: A Smart Card for Public Key
Cryptosystems . . . . . . . . . . . . . 502
Kireeti Kompella and
Leonard M. Adleman Fast Checkers for Cryptography . . . . . 515
Richard Cleve Complexity Theoretic Issues Concerning
Block Ciphers Related to D.E.S. . . . . 530
Thomas W. Cusick and
Michael C. Wood The REDOC II Cryptosystem . . . . . . . 545
Kwangjo Kim and
Tsutomu Matsumoto and
Hideki Imai A Recursive Construction Method of
S-boxes Satisfying Strict Avalanche
Criterion . . . . . . . . . . . . . . . 564
Paul C. van Oorschot A Comparison of Practical Public-Key
Cryptosystems Based on Integer
Factorization and Discrete Logarithms 576
Paul C. van Oorschot A Comparison of Practical Public Key
Cryptosystems Based on Integer
Factorization and Discrete Logarithms 576
Kenji Koyama and
Routo Terada Nonlinear Parity Circuits and their
Cryptographic Applications . . . . . . . 582
Othmar Staffelbach and
Willi Meier Cryptographic Significance of the Carry
for Ciphers Based on Integer Addition 601
B. A. LaMacchia and
Andrew M. Odlyzko Computation of Discrete Logarithms in
Prime Fields (Extended Abstract) . . . . 616--618
Shimon Even Systolic Modular Multiplication . . . . 619
Ronald L. Rivest Finding Four Million Large Random Primes 625
Shoji Miyaguchi The FEAL Cipher Family . . . . . . . . . 627
Yacov Yacobi Discrete-log With Compressible Exponents 639
Anonymous Author Index . . . . . . . . . . . . . . 644
M. Kojima and
N. Megiddo and
T. Noma and
A. Yoshise A Unified Approach to Interior Point
Algorithms for Linear Complementarity
Problems . . . . . . . . . . . . . . . . 1
P. Cellini and
P. Gianni and
C. Traverso Algorithms for the Shape of
Semialgebraic Sets. A New Approach . . . 1
H. Janwa On the Parameters of Algebraic Geometric
Codes . . . . . . . . . . . . . . . . . 19
E. Kaltofen and
B. D. Saunders On Wiedemann's Method of Solving Sparse
Linear Systems . . . . . . . . . . . . . 29
S. N. Litsyn Fast Algorithms for Decoding Orthogonal
and Related Codes . . . . . . . . . . . 39
W. V. Vasconcelos Jacobian Matrices and Constructions in
Algebra . . . . . . . . . . . . . . . . 48
T. Becker Homogenity, Pseudo-Homogenity, and
Gröbner Basis Computations . . . . . . . 65
T. Beth and
F. Schaefer Arithmetic on Non-Supersingular Elliptic
Curves . . . . . . . . . . . . . . . . . 74
G. Butler Implementing Some Algorithms of Kantor 82
J. F. Canny Computing Roadmaps of General
Semi-Algebraic Sets . . . . . . . . . . 94
J. F. Canny An Improved Sign Determination Algorithm 108
H. Chung The $2$-nd Generalized Hamming Weight of
Double-Error Correcting Binary BCH Codes
and Their Dual Codes . . . . . . . . . . 118
P. Conti and
C. Traverso Buchberger Algorithm and Integer
Programming . . . . . . . . . . . . . . 130
M. Diab New Systolic Architectures for Cyclic
Code Encoding . . . . . . . . . . . . . 140
M. J. Dinneen and
M. R. Fellows and
V. Faber Algebraic Constructions of Efficient
Broadcast Networks . . . . . . . . . . . 152
C. van Eijl and
G. Cohen and
G. Zemor Error-Correction for WIMs and WUMs . . . 159
G. Gallo and
B. Mishra and
F. Ollivier Some Constructions in Rings of
Differential Polynomials . . . . . . . . 171
L. P. Holmquist and
L. L. Kinney Concurrent Error Detection in Sequential
Circuits Using Convolutional Codes . . . 183
T. Krick and
A. Logar An Algorithm for the Computation of the
Radical of an Ideal in the Ring of
Polynomials . . . . . . . . . . . . . . 195
W. Kuechlin and
D. Lutz and
N. Nevin Integer Multiplication in PARSAC-2 on
Stock Microprocessors . . . . . . . . . 206
G. Lachaud and
J. Stern Polynomial-Time Construction of
Spherical Codes . . . . . . . . . . . . 218
L. Langemyr Algorithms for a Multiple Algebraic
Extension II . . . . . . . . . . . . . . 224
P. Langevin On the Orphans and Covering Radius of
the Reed--Muller Codes . . . . . . . . . 234
Y. Li and
X. Wang A Joint Authentication and Encryption
Scheme Based on Algebraic Coding Theory 241
A. C. Lobstein and
P. Sole Arithmetic Codes --- Survey, Recent and
New Results . . . . . . . . . . . . . . 246
R. Morelos-Zaragoza and
S. Lin Some Results on Linear
Unequal-Error-Protection Codes Specified
by their Generator Matrix . . . . . . . 259
G. Moreno Socias An Ackermannian Polynomial Ideal . . . . 269
T. Mostowski and
E. Rannou Complexity of the Computation of the
Canonical Whitney Stratification of an
Algebraic Set in $ C^n $ . . . . . . . . 281
F. Otto Some Undecidability Results for Weakly
Confluent Monadic String-Rewriting
Systems . . . . . . . . . . . . . . . . 292
P. Pedersen Calculating Multidimensional Symmetric
Functions Using Jacobi's Formula . . . . 304
P. Pedersen Multivariate Sturm Theory . . . . . . . 318
M. Perret Binary Spherical Geometric Codes . . . . 333
A. Poli and
M. Belkasmi An Algebraic Construction of Generalized
Beenker's Codes . . . . . . . . . . . . 340
J. Rifa and
J. Borrell Improving the Time Complexity of the
Computation of Irreducible and Primitive
Polynomials in Finite Fields . . . . . . 352
J. Rifa and
J. Pujol Completely Transitive Codes and Distance
Transitive Graphs . . . . . . . . . . . 360
J.-J. Risler Placement of Curved Polygons . . . . . . 368
F. Rodier On the Weights of the Elements of the
Duals of Binary BCH Codes . . . . . . . 384
F. Rossi and
W. Spangher Computation of the Openness of Some Loci
of Modules . . . . . . . . . . . . . . . 390
Y. Saitoh and
H. Imai Random and Byte Error Correcting Codes
for Asymmetric or Unidirectional Error
Control . . . . . . . . . . . . . . . . 403
S. Sakata Finding a Minimal Polynomial Vector Set
of a Vector of nD Arrays . . . . . . . . 414
P. Sole Covering Codes and Combinatorial
Optimization . . . . . . . . . . . . . . 426
O. N. Ucan and
U. Aygolu and
E. Panayirci Decoding of Quadrature Partial
Response-Trellis Coded Signals (QPR-TCM)
in the Presence of Intersymbol
Interference and Noise . . . . . . . . . 434
F. Ulmer On Algebraic Solutions of Linear
Differential Equations with Primitive
Unimodular Galois Group . . . . . . . . 446
F. S. Vainstein Error Detection and Correction in
Numerical Computations by Algebraic
Methods . . . . . . . . . . . . . . . . 456
K. Zeng and
D.-Y. Wei and
T. R. N. Rao $d$-Functions in $ {V}_k ({F}_2) $ and
Self-Decimation of $m$-Sequences . . . . 465
L. Zhang and
B. Vuketic Multilevel Modulation Codes for Rayleigh
Fading Channels . . . . . . . . . . . . 477
M. Filgueiras and
A. P. Tomas Solving Linear Constraints on Finite
Domains Through Parsing . . . . . . . . 1
F. Menezes and
P. Barahona Constraint Solving in Finite Domains
under User Control . . . . . . . . . . . 17
A. P. Tomas and
M. Filgueiras A New Method for Solving Linear
Constraints on the Natural Numbers . . . 30
K. Lano A Constraint-Based Fuzzy Inference
System . . . . . . . . . . . . . . . . . 45
M. Mamede and
L. Monteiro A Constraint-Based Language for Querying
Taxonomic Systems . . . . . . . . . . . 60
J. A. Mendes and
P. R. Henriques Heuristic Parsing and Search Space
Pruning . . . . . . . . . . . . . . . . 76
P. C. Nelson and
A. A. Toptsis Wave-shaping in Multiprocessor
Bidirectional Heuristic State Space
Search . . . . . . . . . . . . . . . . . 92
L. Moniz Pereira and
J. J. Alferes and
J. N. Aparicio The Extended Stable Models of
Contradiction Removal Semantics . . . . 105
D. Kumar and
S. C. Shapiro Modelling a Rational Cognitive Agent in
SNePS . . . . . . . . . . . . . . . . . 120
G. David and
A. Porto Semantics of Property Inheritance in a
Hierarchic System with Explicit Negation 135
A. Cardoso and
E. Costa Time in Confluences: Dealing with Delays
for Consistency-Checking . . . . . . . . 151
E. Rutten A Temporal Representation for
Imperatively Structured Plans of Actions 165
C. Ribeiro and
A. Porto Maximal Intervals: An Approach to
Temporal Reasoning . . . . . . . . . . . 180
M. Decker and
G. Moerkotte and
H. Muller and
J. Posegga Consistency Driven Planning . . . . . . 195
C. Ramos and
E. Oliveira An Efficient Approach to Planning in
Assembly Tasks . . . . . . . . . . . . . 210
G. Friedrich and
G. Gottlob and
W. Nejdl Towards a Theory of the Repair Process 222
M. Calejo and
L. Moniz Pereira Declarative Source Debugging . . . . . . 237
K. P. Kratzer A Neural Approach to Data Compression
and Classification . . . . . . . . . . . 250
R. Vorc'h Generalization for a Propositional
Calculus: A Constraints-Based Approach 264
L. Winkelbauer and
C. Stary Adaptive Learning Using a Qualitative
Feedback Loop . . . . . . . . . . . . . 278
A. W. Biermann and
R. W. Smith An architecture for pragmatic voice
interactive systems . . . . . . . . . . 1
J. Doyle and
Y. Shoham and
M. P. Wellman A logic of relative desire . . . . . . . 16
G. Wiederhold The roles of artificial intelligence in
information systems . . . . . . . . . . 38
C. F. Eick Integrating variables and operations
into rule-based forward chaining systems 52
D. Mutchler The multi-player version of minimax
displays game-tree pathology . . . . . . 62
L. Portinale Generalization handling in a dynamic
case memory . . . . . . . . . . . . . . 72
H. An and
L. J. Henschen Knowledge based semantic query
optimization . . . . . . . . . . . . . . 82
C. Baral and
S. Kraus and
J. Minker and
V. S. Subrahmanian Combining knowledge bases consisting of
first order theories . . . . . . . . . . 92
S. K. Bhatia and
J. S. Deogun and
V. V. Raghavan User profiles for information retrieval 102
I-M. A. Chen and
R.-C. Lee An approach to deriving object
hierarchies from database schema and
contents . . . . . . . . . . . . . . . . 112
B. C. Desai and
L. Zhang Multilevel interface to a distributed
database system . . . . . . . . . . . . 122
J. Han and
Q. Wang Efficient evaluation of linear
recursions with function symbols in
deductive databases . . . . . . . . . . 132
J. Y-j. Hsu Synthesizing efficient agents from
partial programs . . . . . . . . . . . . 142
K. A. Kaufman and
R. S. Michalski and
L. Kerschberg Knowledge extraction from databases:
design principles of the INLEN system 152
R. Ng and
V. S. Subrahmanian Stable model semantics for probabilistic
deductive databases . . . . . . . . . . 162
S. K. M. Wong and
P. Lingras and
Y. Y. Yao Towards implementing valuation based
systems with relational databases . . . 172
B.-T. B. Chu On the representation of continuous
causal relationships . . . . . . . . . . 183
J. Malec Process transition networks: a formal
graphical knowledge representation tool 193
R. A. Munoz and
C.-C. Yang Using normal deduction graphs in default
reasoning . . . . . . . . . . . . . . . 203
Z. W. Ras and
J. Xiao A model of information sharing for
fault-tolerant flexible manufacturing
systems . . . . . . . . . . . . . . . . 213
B. Richards and
Y. Jiang and
H. Choi On interval-based temporal planning ---
an IQ strategy . . . . . . . . . . . . . 226
M. Sobolewski Percept conceptualizations and their
knowledge representation schemes . . . . 236
P. Terenziani Combining time points and time intervals
in a hybrid knowledge representation
formalism . . . . . . . . . . . . . . . 246
K. Thirunarayan An analysis of property-flow view vs.
individual-flow view of inheritance . . 256
E. B. Wendlandt and
J. R. Driscoll Semantic extensions to text retrieval 266
M. Winslett and
T. S.-C. Chou Updates with equality: beyond the
Herbrand universe assumption . . . . . . 276
J. Bala and
K. DeJong and
P. Pachowicz Using genetic algorithms to improve the
performance of classification rules
produced by symbolic inductive method 286
M. Botta and
A. Giordana Learning quantitative features in a
symbolic environment . . . . . . . . . . 296
S. Coates-Stephens Automatic acquisition of proper noun
meanings . . . . . . . . . . . . . . . . 306
L. Console and
A. Giordana and
L. Saitta Investigating the relationships between
abduction and inverse resolution in
propositional calculus . . . . . . . . . 316
S. Delisle and
S. Matwin and
J. Wang and
L. Zupan Explanation-based learning helps acquire
knowledge from natural language texts 326
C. W. Glover and
N. S. V. Rao and
E. M. Oblow Hybrid pattern recognition system
capable of self-modification . . . . . . 338
A. Goker and
T. L. McCluskey Towards an adaptive information
retrieval system . . . . . . . . . . . . 348
D. F. Gordon Improving the comprehensibility,
accuracy, and generality of reactive
plans . . . . . . . . . . . . . . . . . 358
J. W. Grzymala-Busse On the unknown attribute values in
learning from examples . . . . . . . . . 368
C. Z. Janikow A new system for inductive learning in
attribute-based spaces . . . . . . . . . 378
M. Michalewicz and
Z. Michalewicz Generation of classification rules . . . 389
S. Salzberg Distance metrics for instance-based
learning . . . . . . . . . . . . . . . . 399
W. M. Spears and
V. Anand A study of crossover operators in
genetic programming . . . . . . . . . . 409
G. Tecuci and
R. S. Michalski Input understanding as a basis for
multistrategy task-adaptive learning . . 419
R. Zembowicz and
J. M. Zytkow Automated discovery of empirical
equations from data . . . . . . . . . . 429
J. M. Zytkow and
P. J. Fischer Constructing models of hidden structure 441
Seiki Akama Amalgamated logic programming and
non-monotonic reasoning . . . . . . . . 450
C. Baral and
J. Lobo and
J. Minker WF$^3$: a semantics for negation in
normal disjunctive logic programs . . . 459
J. Calmet and
I. A. Tjandra Representation of mathematical knowledge 469
P. Chatalic and
C. Froidevaux Graded logics: a framework for uncertain
and defeasible knowledge . . . . . . . . 479
J. Chen and
S. Kundu The strong semantics for logic programs 490
J. M. Conrad and
D. Bahler and
J. Bowen Static parallel arc consistency in
constraint satisfaction . . . . . . . . 500
P. A. Flach Towards a theory of inductive logic
programming . . . . . . . . . . . . . . 510
Y. J. Jiang Another view of autoepistemic logic and
truth maintenance system . . . . . . . . 520
K. Kuo Dynamic autoepistemic logic . . . . . . 530
S. Lorenz Nonmonotonic temporal reasoning:
persistence, justified causation and
event minimization . . . . . . . . . . . 540
P. Marquis Novelty revisited . . . . . . . . . . . 550
M. J. Miller and
D. Perlis Typicality constants and range defaults:
some pros and cons of a cognitive model
of default reasoning . . . . . . . . . . 560
N. V. Murray and
E. Rosenthal Resolution and path dissolution in
multiple-valued logics . . . . . . . . . 570
X. Nie How well are non-Horn clauses handled? 580
M. Nirkhe and
S. Kraus and
D. Perlis Fully deadline-coupled planning: one
step at a time . . . . . . . . . . . . . 589
J. A. Plaza Completeness for propositional logic
programs with negation . . . . . . . . . 600
A. Rajasekar Disjunctive logic programs and
constraint processing . . . . . . . . . 610
Z. Stachniak Note on resolution circuits . . . . . . 620
R. H. Thomason A semantic analysis of monotonic
inheritance with roles and relations . . 630
Gerhard Brewka and
David Makinson and
Karl Schlechta Cumulative Inference Relations for JTMS
and Logic Programming . . . . . . . . . 1
Jurgen Dix Cumulativity and Rationality in
Semantics of Normal Logic Programs . . . 13
Heinrich Herre Nonmonotonic Reasoning and Logic
Programs . . . . . . . . . . . . . . . . 38
Michael Freund Supracompact Inference Operations . . . 59
Gerhard Jager Notions of Nonmonotonic Derivability . . 74
Wiktor Marek and
Grigori F. Schwarz and
Miroslaw Truszczynski Ranges of Strong Modal Nonmonotonic
Logics . . . . . . . . . . . . . . . . . 85
Helmut Thiele On Generation of Cumulative Inference
Operators by Default Deduction Rules . . 100
Emil Weydert Qualitative Magnitude Reasoning . . . . 138
Klaus P. Jantke Monotonic and Nonmonotonic Inductive
Inference of Functions and Patterns . . 161
Steffen Lange A Note on Polynomial-Time Inference of
$k$-Variable Pattern Languages . . . . . 178
Rolf Wiehagen A Thesis in Inductive Inference . . . . 184
Thomas Zeugmann Inductive Inference of Optimal Programs:
A Survey and Open Problems . . . . . . . 208
Jurgen Kalinski Autoepistemic Expansions with Incomplete
Belief Introspection . . . . . . . . . . 223
Michael Morreau and
Hans Rott Is it Impossible to Keep up to Date? . . 233
W. Hesse Two Metamodels for Application System
Development --- Conventional vs.
Object-Oriented Approach . . . . . . . . 3
B. Krieg-Bruckner Transformational Meta Program
Development . . . . . . . . . . . . . . 19
H. A. Partsch and
N. Volker Another Case Study on Reusability of
Transformational Developments Pattern
Matching According to Knuth, Morris, and
Pratt . . . . . . . . . . . . . . . . . 35
R. Hennicker and
M. Wirsing A Formal Method for the Systematic Reuse
of Specification Components . . . . . . 49
M. Broy Deductive Program Development:
Evaluation in Reverse Polish Notation as
an Example . . . . . . . . . . . . . . . 79
P. Pepper Literate Program Derivation: A Case
Study . . . . . . . . . . . . . . . . . 101
R. Steinbruggen Programs Viewed as SKOLEM Functions . . 125
U. Berger and
W. Meixner and
B. Moller Calculating a Garbage Collector . . . . 137
R. Berghammer and
H. Ehler On the Use of Elements of Functional
Programming in Program Development by
Transformations . . . . . . . . . . . . 193
C. Delgado Kloos and
W. Dosch Transformational Development of Circuit
Descriptions for Binary Adders . . . . . 217
Henk Alblas Introduction to Attribute Grammars . . . 1
Uwe Kastens Attribute Grammars as a Specification
Method . . . . . . . . . . . . . . . . . 16
Henk Alblas Attribute Evaluation Methods . . . . . . 48
Uwe Kastens Implementation of Visit-Oriented
Attribute Evaluators . . . . . . . . . . 114
Rieks op den Akker and
Erik Sluiman Storage Allocation for Attribute
Evaluators Using Stacks and Queues . . . 140
Ulrich Moncke and
Reinhard Wilhelm Grammar Flow Analysis . . . . . . . . . 151
Rieks op den Akker and
Borivoj Melichar and
Jorma Tarhio Attribute Evaluation and Parsing . . . . 187
Henk Alblas Incremental Attribute Evaluation . . . . 215
Martin Jourdan A Survey of Parallel Attribute
Evaluation Methods . . . . . . . . . . . 234
Doaitse Swierstra and
Harald Vogt Higher Order Attribute Grammars . . . . 256
Kai Koskimies Object-Orientation in Attribute Grammars 297
Jan Maluszynski Attribute Grammars and Logic Programs: A
Comparison of Concepts . . . . . . . . . 330
Kees Koster Affix Grammars for Programming Languages 358
Gorel Hedin Incremental Static-Semantic Analysis for
Object-Oriented Languages Using Door
Attribute Grammars . . . . . . . . . . . 374
Uwe Kastens Attribute Grammars in a Compiler
Construction Environment . . . . . . . . 380
Gunter Riedewald Prototyping by Using an Attribute
Grammar as a Logic Program . . . . . . . 401
Peter Forbrig Using the Generative Aspect of Attribute
Grammars in a Knowledge Based Way . . . 438
Tibor Gyimothy Natural Language Interface Construction
Using Attribute Grammars . . . . . . . . 460
Kees Koster Affix Grammars for Natural Languages . . 469
Martin Jourdan and
Didier Parigot Internals and Externals of the FNC-2
Attribute Grammar System . . . . . . . . 485
Peter Lipps and
Ulrich Moncke and
Reinhard Wilhelm An Overview of the OPTRAN System . . . . 505
Reinhard Wilhelm Attribute Reevaluation in OPTRAN . . . . 507
Ralf Lammel The Translator Writing System RUEGEN ---
KS . . . . . . . . . . . . . . . . . . . 508
Claus-Rainer Rollinger and
Otthein Herzog Introducing LILOG . . . . . . . . . . . 3
Wilfried Brauer and
Peter Lockemann and
Helmut Schnelle Text Understanding --- The Challenges to
Come . . . . . . . . . . . . . . . . . . 14
Jochen Dorre and
Roland Seiffert A Formalism for Natural Language ---
STUF . . . . . . . . . . . . . . . . . . 33
Jochen Dorre The Language of STUF . . . . . . . . . . 39
Roland Seiffert Chart-Parsing of STUF Grammars . . . . . 51
Jochen Dorre and
Ingo Raasch The STUF Workbench . . . . . . . . . . . 55
Roland Seiffert Unification-ID/LP Grammars:
Formalization and Parsing . . . . . . . 63
Gregor Erbach A Flexible Parser for a Linguistic
Development Environment . . . . . . . . 74
Esther Konig GAP-Handling Mechanisms in Categorial
Grammars . . . . . . . . . . . . . . . . 88
Siegfried Kanngießer Outlines of the LEU/2 Lexicology . . . . 105
Anne Schiller and
Petra Steffens Morphological Processing in the
Two-Level Paradigm . . . . . . . . . . . 112
Helmar Gust Representing Word Meanings . . . . . . . 127
Mechthild Rickheit Sortal Information in Lexical Concepts 143
Petra Ludewig Incremental Vocabulary Extensions in
Text Understanding Systems . . . . . . . 153
Werner Emde Managing Lexical Knowledge in LEU/2 . . 167
Tibor Kiss The Grammars of LILOG . . . . . . . . . 183
Birgit Wesche An Alternative Phrase Structure Account
of Symmetric Coordination . . . . . . . 200
Tibor Kiss and
Birgit Wesche Verb Order and Head Movement . . . . . . 216
Peter Bosch The Bermuda Triangle: Natural Language
Semantics Between Linguistics, Knowledge
Representation, and Knowledge Processing 243
Rob A. van der Sandt and
Bart Geurts Presupposition, Anaphora, and Lexical
Content . . . . . . . . . . . . . . . . 259
Rolf Mayer Anaphora and Domain Restriction . . . . 297
Kurt Eberle On Representing the Temporal Structure
of Texts . . . . . . . . . . . . . . . . 313
Godehard Link and
Hinrich Schutze The Treatment of Plurality in Lsub LILOG 342
Udo Pletat The Knowledge Representation Language
Lsub LILOG . . . . . . . . . . . . . . . 357
Ipke Wachsmuth and
Barbara Gangler Knowledge Packets and Knowledge Packet
Structures . . . . . . . . . . . . . . . 380
Peter H. Schmitt Deductive Aspects of Three-Valued Logic 394
Toni Bollinger and
Sven Lorenz and
Udo Pletat The LILOG Inference Engine . . . . . . . 402
Karl Hans Blasius Knowledge Based Control of the LILOG
Inference Engine: Kinds of Metaknowledge 428
Bernhard Nebel and
Gert Smolka Attributive Description Formalisms
\ldots and the Rest of the World . . . . 439
Gudrun Klose and
Kai von Luck The Background Knowledge of the LILOG
System . . . . . . . . . . . . . . . . . 455
Ewald Lang The LILOG Ontology from a Linguistic
Point of View . . . . . . . . . . . . . 464
Manfred Borkel and
Peter Gerstl A Knowledge Engineering Environment for
LILOG . . . . . . . . . . . . . . . . . 482
Jurgen Angele and
Dieter Fensel and
Dieter Landes and
Susanne Neubert and
Rudi Studer Knowledge Engineering in the Context of
Related Fields of Research . . . . . . . 490
Stefan Benzschawel and
Erich Gehlen and
Michael Ley and
Thomas Ludwig and
Albert Maier and
Bernd Walter LILOG-DB: Database Support for Knowledge
Based Systems . . . . . . . . . . . . . 501
Christopher Habel Processing of Spatial Expressions in
LILOG . . . . . . . . . . . . . . . . . 598
Simone Pribbenow Phenomena of Localization . . . . . . . 609
Claudia Maienborn Verbs of Motion and Position: On the
Optionality of the Local Argument . . . 621
Kai-Uwe Carstensen and
Geoff Simmons Why a Hill Can't be a Valley:
Representing Gestalt and Position
Properties of Objects with Object
Schemata . . . . . . . . . . . . . . . . 632
Mohammed N. Khenkhar Object-Oriented Representation of
Depictions on the Basis of Cell Matrices 645
Hans-Joachim Novak Integrating a Generation Component into
a Natural Language Understanding System 659
Zuzana Dobes and
Hans-Joachim Novak From Knowledge Structures to Text
Structures . . . . . . . . . . . . . . . 670
Birgit Wendholt The Formulator . . . . . . . . . . . . . 685
Kai von Luck and
Thomas Pirlein Constructing a Context for LEU/2 . . . . 703
Jan Wilms The Text Understanding System LEU/2 . . 711
Andreas Arning The Trace of Building a Large AI System 719
Eli Biham and
Adi Shamir Differential Cryptanalysis of Feal and
$N$-Hash . . . . . . . . . . . . . . . . 1
Xuejia Lai and
James L. Massey and
Sean Murphy Markov Ciphers and Differential
Cryptanalysis . . . . . . . . . . . . . 17
Paul Camion and
Jacques Patarin The Knapsack Hash Function Proposed at
Crypto '89 Can be Broken . . . . . . . . 39--53
Matthijs J. Coster and
B. A. LaMacchia and
Andrew M. Odlyzko and
Claus P. Schnorr An Improved Low-Density Subset Sum
Algorithm . . . . . . . . . . . . . . . 54
Valery I. Korzhik and
Andrey I. Turkin Cryptanalysis of McEliece's Public-Key
Cryptosystem . . . . . . . . . . . . . . 68
Peter de Rooij On the Security of the Schnorr Scheme
Using Preprocessing . . . . . . . . . . 71
Mike V. D. Burmester and
Yvo Desmedt Broadcast Interactive Proofs . . . . . . 81
Tatsuaki Okamoto and
David Chaum and
Kazuo Ohta Direct Zero Knowledge Proofs of
Computational Power in Five Rounds . . . 96
Claude Crépeau and
Miklós Sántha On the Reversibility of Oblivious
Transfer . . . . . . . . . . . . . . . . 106
Sibylle Mund Ziv--Lempel Complexity for Periodic
Sequences and its Cryptographic
Application . . . . . . . . . . . . . . 114
Toshiki Habutsu and
Yoshifumi Nishio and
Iwao Sasase and
Shinsaku Mori A Secret Key Cryptosystem by Iterating a
Chaotic Map . . . . . . . . . . . . . . 127
Bart Preneel and
René Govaerts and
Joos Vandewalle Boolean Functions Satisfying Higher
Order Propagation Criteria . . . . . . . 141
Cees J. A. Jansen The Maximum Order Complexity of Sequence
Ensembles . . . . . . . . . . . . . . . 153
Jovan Dj. Golic The Number of Output Sequences of a
Binary Sequence Generator . . . . . . . 160
Zong-Duo D. Dai and
Jun-Hui H. Yang Linear Complexity of Periodically
Repeated Random Sequences . . . . . . . 168
Vladimir Chepyzhov and
Bernard Smeets On a Fast Correlation Attack on Certain
Stream Ciphers . . . . . . . . . . . . . 176
Willi Meier and
Othmar Staffelbach Analysis of Pseudo Random Sequences
Generated by Cellular Automata . . . . . 186
William G. Chambers and
Zong-Duo D. Dai On Binary Sequences from Recursions
``modulo $ 2^e $'' Made Non-Linear by
the Bit-by-Bit ``XOR'' Function . . . . 200
Yvo Desmedt and
Moti Yung Weaknesses of Undeniable Signature
Schemes (Extended Abstract) . . . . . . 205
Torben Pryds Pedersen Distributed Provers with Applications to
Undeniable Signatures . . . . . . . . . 221
Atsushi Fujioka and
Tatsuaki Okamoto and
Kazuo Ohta Interactive Bi-Proof Systems and
Undeniable Signature Schemes . . . . . . 243
David Chaum and
Eug\`ene van Heyst Group Signatures . . . . . . . . . . . . 257
Colin Boyd Enhancing Secrecy by Data Compression:
Theoretical and Practical Aspects . . . 266
Claus P. Schnorr Factoring Integers and Computing
Discrete Logarithms via Diophantine
Approximation . . . . . . . . . . . . . 281
Klaus Huber Some Considerations Concerning the
Selection of RSA Moduli . . . . . . . . 294
Michael Portz On the Use of Interconnection Networks
in Cryptography . . . . . . . . . . . . 302
Thomas Beth and
F. Schaefer Non Supersingular Elliptic Curves for
Public Key Cryptosystems . . . . . . . . 316
François Morain Building Cyclic Elliptic Curves Modulo
Large Primes . . . . . . . . . . . . . . 328
Hiroki Shizuya and
Toshiya Itoh and
Kouichi Sakurai On the Complexity of Hyperelliptic
Discrete Logarithm Problem . . . . . . . 337
M. H. Dawson and
Stafford E. Tavares An Expanded Set of S-Box Design Criteria
Based on Information Theory and its
Relation to Differential-Like Attacks 352
Luke O'Connor Enumerating Nondegenerate Permutations 368
Kaisa Nyberg Perfect Nonlinear S-Boxes . . . . . . . 378
Rainer A. Rueppel A Formal Approach to Security
Architectures . . . . . . . . . . . . . 387
Patrick Horster and
Hans-Joachim Knobloch Discrete Logarithm Based Protocols . . . 399
Tsutomu Matsumoto and
Hideki Imai Human Identification Through Insecure
Channel . . . . . . . . . . . . . . . . 409
B. Goldburg and
E. Dawson and
S. Sridharan The Automated Cryptanalysis of Analog
Speech Scramblers . . . . . . . . . . . 422
Babak Sadeghiyan and
Józef P. Pieprzyk A Construction for One Way Hash
Functions and Pseudorandom Bit
Generators . . . . . . . . . . . . . . . 431--445
Atsushi Fujioka and
Tatsuaki Okamoto and
Shoji Miyaguchi ESIGN: An Efficient Digital Signature
Implementation for Smart Cards . . . . . 446
Ueli M. Maurer New Approaches to the Design of
Self-Synchronizing Stream Ciphers . . . 458
Józef P. Pieprzyk and
Reihaneh Safavi-Naini Randomized Authentication Systems . . . 472
E. M. Gabidulin and
A. V. Paramonov and
O. V. Tretjakov Ideals over a Non-Commutative Ring and
Their Application in Cryptology . . . . 482
Marc Girault Self-Certified Public Keys . . . . . . . 490
Ueli M. Maurer and
Yacov Yacobi Non-interactive Public-Key Cryptography 498
Gilles Zémor Hash Functions and Graphs with Large
Girths . . . . . . . . . . . . . . . . . 508--511
Winfried B. Müller and
Alan Oswald Dickson Pseudoprimes and Primality
Testing . . . . . . . . . . . . . . . . 512
J. Keith Gibson Equivalent Goppa Codes and Trapdoors to
McEliece's Public Key Cryptosystem . . . 517
Torben Pryds Pedersen A Threshold Cryptosystem without a
Trusted Party (Extended Abstract) . . . 522
Miodrag J. Mihaljevic and
Jovan Dj. Golic A Comparison of Cryptanalytic Principles
Based on Iterative Error-Correction . . 527
Eli Biham Cryptanalysis of the Chaotic-Map
Cryptosystem Suggested at EUROCRYPT '91 532
Shimshon Berkovits How to Broadcast a Secret . . . . . . . 535
Józef P. Pieprzyk Probabilistic Analysis of Elementary
Randomizers . . . . . . . . . . . . . . 542
Bart Preneel and
David Chaum and
Walter Fumy and
Cees J. A. Jansen and
Peter Landrock and
G. Roelofsen Race Integrity Primitives Evaluation
(RIPE): A Status Report . . . . . . . . 547
Lennart Brynielsson The Information Leakage Through a
Randomly Generated Function . . . . . . 552
David Chaum Some Weaknesses of ``Weaknesses of
Undeniable Signatures'' . . . . . . . . 554
D. M. Gabbay Abduction in Labelled Deductive Systems
--- A Conceptual Abstract . . . . . . . 3
P. Gardenfors Nonmonotonic Inference, Expectations,
and Neural Networks . . . . . . . . . . 12
Anonymous Introduction . . . . . . . . . . . . . . 31
S. Amarger and
D. Dubois and
H. Prade Imprecise Quantifiers and Conditional
Probabilities . . . . . . . . . . . . . 33
P. Besnard Default Logics . . . . . . . . . . . . . 38
J. Cano and
M. Delgado and
S. Moral Propagation of Uncertainty in Dependence
Graphs . . . . . . . . . . . . . . . . . 42
M. Clarke and
N. Wilson Efficient Algorithms for Belief
Functions Based on the Relationship
Between Belief and Probability . . . . . 48
D. Dubois and
J. Lang and
H. Prade A Brief Overview of Possibilistic Logic 53
L. Farinas del Cerro and
A. Herzig A Modal Analysis of Possibility Theory 58
J. Fox and
P. Krause and
M. Dohnal An Extended Logic Language for
Representing Belief . . . . . . . . . . 63
Ch. Froidevaux and
P. Chatalic and
J. Mengin Graded Default Logics . . . . . . . . . 70
L. Godo and
R. Lopez de Mantaras Linguistically Expressed Uncertainty:
Its Elicitation and Use in Modular
Expert Systems . . . . . . . . . . . . . 76
R. Kruse and
J. Gebhardt and
F. Klawonn Reasoning with Mass Distributions and
the Context Model . . . . . . . . . . . 81
S. Parsons Advance Prototyping . . . . . . . . . . 86
P. Smets and
Y-T Hsia and
A. Saffiotti and
R. Kennes and
H. Xu and
E. Umkehrer The Transferable Belief Model . . . . . 91--98
S. Acid and
L. M. de Campos and
A. Gonzalez and
R. Molina Learning with CASTLE . . . . . . . . . . 99
J. F. Baldwin A New Approach to Inference Under
Uncertainty for Knowledge Based Systems 107
E. Binaghi Learning of Uncertain Classification
Rules in Medical Diagnosis . . . . . . . 115
G. Brewka Assertional Default Theories . . . . . . 120
L. Cardona and
J. Kohlas and
P. A. Monney The Reliability of Reasoning with
Unreliable Rules and Propositions . . . 125
A. Chateauneuf and
R. Kast and
A. Lapied Uncertainty in the Valuation of Risky
Assets . . . . . . . . . . . . . . . . . 130
G. Coletti and
A. Gilio and
R. Scozzafava Assessment of Qualitative Judgements for
Conditional Events in Expert Systems . . 135
F. S. Correa da Silva and
D. Robertson and
P. Chung Automated Reasoning About an Uncertain
Domain . . . . . . . . . . . . . . . . . 141
J. Cussens and
A. Hunter Using Defeasible Logic for a Window on a
Probabilistic Database: Some Preliminary
Notes . . . . . . . . . . . . . . . . . 146
E. Diday From Data Analysis to Uncertainty
Knowledge Analysis . . . . . . . . . . . 153
A. Di Nola and
W. Pedrycz and
S. Sessa Difference Fuzzy Relation Equations:
Studies in Dynamical Systems . . . . . . 161
D. Driankov and
H. Hellendoorn Towards a Logic for a Fuzzy Logic
Controller . . . . . . . . . . . . . . . 166
O. Etzion Handling Active Databases with Partial
Inconsistencies . . . . . . . . . . . . 171
L. Gacogne An Extension of the Possibility Theory
in View of the Formalization of
Approximate Reasoning . . . . . . . . . 176
S. D. Goodwin and
E. Neufeld and
A. Trudel Probabilistic Regions of Persistence . . 182
E. Gregoire Formalizing Pertinence Links in
Inheritance Reasoning: Preliminary
Report . . . . . . . . . . . . . . . . . 190
J. Heinsohn A Hybrid Approach for Modeling
Uncertainty in Terminological Logics . . 198
H. Hellendoorn and
M. Reinfrank Fuzzy Control Research at Siemens
Corporate R and D . . . . . . . . . . . 206
U. Junker and
G. Brewka Handling Partially Ordered Defaults in
TMS . . . . . . . . . . . . . . . . . . 211
F. Levy Computing Extensions of Default Theories 219
G. Lohmann An Evidential Reasoning Approach to the
Classification of Satellite Images . . . 227
Z. Luo and
A. Gammerman PRESS --- A Probabilistic Reasoning
Expert System Shell . . . . . . . . . . 232
Y. Ma and
D. C. Wilkins Induction of Uncertain Rules and the
Sociopathicity Property in
Dempster-Shafer Theory . . . . . . . . . 238
C. MacNish Hierarchical Default Logic . . . . . . . 246
A. Nakamura A Logic of Imprecise Monadic Predicates
and its Relation to the S5-Modal Fuzzy
Logic . . . . . . . . . . . . . . . . . 254
U. G. Oppel Every Complex System can be Determined
by a Causal Probabilistic Network
Without Cycles and Every Such Network
Determines a Markov Field . . . . . . . 262
G. Paass Probabilistic Default Reasoning
Involving Continuous Variables . . . . . 267
O. Papini Revision in Propositional Calculus . . . 272
T. Pontet A Constraint-based Approach to Uncertain
and Imprecise Reasoning. Application to
Expert Systems . . . . . . . . . . . . . 277
P. Quinio and
T. Matsuyama Random Closed Sets: A Unified Approach
to the Representation of Imprecision and
Uncertainty . . . . . . . . . . . . . . 282
A. Rauzy Knowledge Extraction in Trivalued
Propositional Logic . . . . . . . . . . 287
P. C. Rhodes and
G. R. Garside Using Maximum Entropy to Identify Unsafe
Assumptions in Probabilistic Expert
Systems . . . . . . . . . . . . . . . . 292
E. H. Ruspini On Truth and Utility . . . . . . . . . . 297
T. Schaub On Commitment and Cumulativity in
Default Logics . . . . . . . . . . . . . 305
C. B. Schwind and
V. Risch A Tableau-Based Characterisation for
Default Logic . . . . . . . . . . . . . 310
P. Snow Restraining the Proliferation of Worlds
in Probabilistic Logic Entailments . . . 318
M. Spies Managing Uncertainty in Environmental
Analysis: An Application to Measurement
Data Interpretation . . . . . . . . . . 323
L. E. Sucar and
D. F. Gillies Handling Uncertainty in Knowledge-Based
Computer Vision . . . . . . . . . . . . 328
H. Thone and
U. Guntzer and
W. Kiebling Probabilistic Reasoning with Facts and
Rules in Deductive Databases . . . . . . 333
R. M. Vandenberghe and
R. M. de Caluwe An Entity-Relationship Approach to the
Modelling of Vagueness in Databases . . 338
F. Voorbraak A Preferential Model Semantics for
Default Logic . . . . . . . . . . . . . 344
E. Weydert Elementary Hyperentailment ---
Nonmonotonic Reasoning About Defaults 352
W. Wahlster and
E. Andre and
W. Graf and
T. Rist Knowledge-based media coordination in
intelligent user interfaces . . . . . . 2
G. Amati Some notes on cumulative reasoning . . . 18
P. A. Bonatti A family of three-valued autoepistemic
logics . . . . . . . . . . . . . . . . . 28
M. Simi Viewpoints subsume beliefs, truths and
situations . . . . . . . . . . . . . . . 38
D. Basin and
F. Giunchigia and
P. Traverso Automating meta-theory creation and
system extension . . . . . . . . . . . . 48
B. Fronhofer Implementing exceptions in inheritance
by concept transforming actions . . . . 58
M. Cadoli and
M. Schaerf Approximate entailment . . . . . . . . . 68
L. Giordano and
M. Martelli and
M. L. Sapino Negation as failure and constraints
through abduction and defaults . . . . . 78
F. M. Donni and
M. Lenzerini and
D. Nardi and
A. Schaerf A hybrid system with datalog and concept
languages . . . . . . . . . . . . . . . 88
J. Ellman and
G. Mezzanatto Optimal search for conjunctive goals
using constraints . . . . . . . . . . . 98
R. M. Jansen-Winkeln and
A. Ndiaye and
N. Reithinger FSS-WASTL: interactive knowledge
acquisition for a semantic lexicon . . . 108
J.-M. Slack Hybrid encoding: constraints on
addressing structure . . . . . . . . . . 117
A. Bonarini and
E. Cappelletti and
A. Corrao Uncertainty and cyclic dependencies: a
proposal and a network implementation 127
A. Brogi and
E. Lamma and
P. Mancarelli and
P. Mello Abductive reasoning in a multi-theory
framework . . . . . . . . . . . . . . . 137
R. Evertsz and
E. Motta The abstract interpretation of hybrid
rule/frame-based systems . . . . . . . . 147
C. Bagnasco and
P. Petrin and
L. Spampinato Taxonomic reasoning in configuration
tasks . . . . . . . . . . . . . . . . . 157
G. Brajnik and
L. Chittaro and
G. Guida and
C. Tasso and
E. Toppano Representation and use of teleological
knowledge in the multi-modeling approach 167
L. Console and
D. Theseider-Dupre and
P. Torasso Towards the integration of different
knowledge sources in model-based
diagnosis . . . . . . . . . . . . . . . 177
S. Cermignani and
G. Tornielli Integrating statistics, numerical
analysis and dependency-recording in
model-based diagnosis . . . . . . . . . 187
C. Carpineto Version-space induction with multiple
concept languages . . . . . . . . . . . 198
G. Cerbone and
T. G. Dietterich Knowledge compilation to speed up
numerical optimization . . . . . . . . . 208
M. Dorigo New perspectives about default
hierarchies formation in learning
classifier systems . . . . . . . . . . . 218
M. Botta and
F. Brancadori and
S. Ravotto and
S. Sperotto and
L. Saitta Use of causal model to learn diagnostic
knowledge in a real domain . . . . . . . 228
A. Giordana and
L. Saitta and
D. Roverso and
R. Finelli and
M. Paderni Extending inverse resolution to build up
abstractions . . . . . . . . . . . . . . 238
R. Basili and
M. T. Pazienza and
P. Velardi Using word association for syntactic
disambiguation . . . . . . . . . . . . . 250
D. Fum and
C. Tasso and
L. Tiepolo and
A. Tramontini A computational model of tense selection
and its experimentation within an
intelligent tutor . . . . . . . . . . . 261
M. Piastra and
R. Bolognesi An efficient context-free parsing
algorithm with semantic actions . . . . 271
C. Strapparava From scopings to interpretation: the
semantic interpretation within the
AIFresco system . . . . . . . . . . . . 281
V. Lombardo Parsing dependency grammars . . . . . . 291
E. Ardizzone and
A. Chella and
R. Pirrone and
F. Sorbello A system based on neural architectures
for the reconstruction of $3$-D shapes
from images . . . . . . . . . . . . . . 302
F. Burbello and
S. B. Pollard and
J. Porrill and
J. E. W. Mayhew Retrieval of high-level data structures
from stereo vision data . . . . . . . . 312
G. Adorni and
A. Broggi and
G. Conte and
V. D'Andrea and
C. Sansoe High-level and low-level computer
vision: towards an integrated approach 322
E. Ardizzone and
F. Callari and
A. Chella and
F. Frixione An associative link from geometric to
symbolic representations in artificial
vision . . . . . . . . . . . . . . . . . 332
G. Vercelli and
R. Zaccaria and
P. Morasso A theory of sensor-based robot
navigation using local information . . . 342
M. Klein and
S. C.-Y. Lu Insights into cooperative group design:
experience with the LAN designer system 354
F. Abbruzzese and
E. Minicozzi Direct interaction among active data
structures: a tool for building AI
systems . . . . . . . . . . . . . . . . 365
A. Artale and
F. Cesarini and
G. Soda Introducing knowledge representation
techniques in database models . . . . . 375
M. Gioiello and
G. Vassallo and
A. Chella and
F. Sorbello Self-organizing maps: a new digital
architecture . . . . . . . . . . . . . . 385
A. Bertin and
F. Buciol and
G. Dondossola and
C. Lanza Electrical equipment maintenance
training and its application in
industrial environment . . . . . . . . . 399
M. Kantardzic and
V. Okanovic and
S. Rizvic and
A. Filipovic and
H. Glavic Temporal and spatial data and default
assumptions in DIPSY-E system . . . . . 410
R. Milanese and
J.-M. Bost and
T. Pun Visual indexing with an attentive system 415
P. de Pinto and
M. Sette On neural network programming . . . . . 420
M. Abbati and
S. Odoardi A logic for the representation of
spatial knowledge . . . . . . . . . . . 425
B. Fringuelli and
S. Marcugini and
A. Milani and
S. Rivora Truth maintenance in approximate
reasoning . . . . . . . . . . . . . . . 430
A. McIntyre A strategy for design and development of
complex knowledge-systems . . . . . . . 435
G. Attardi and
M. Gaspari and
P. Iglio Efficient compilation of first order
predicates . . . . . . . . . . . . . . . 440
G. Brajnik and
C. Tasso and
A. Vaccher A flexible tool for assumption-based
user modeling . . . . . . . . . . . . . 445
P. Frasconi and
M. Gori and
M. Maggini and
G. Soda KL: a neural model for capturing
structure in speech . . . . . . . . . . 450
G. Lavelli and
B. Magnini Lexical discrimination within a
multilevel semantics approach . . . . . 455
S. Costantini and
G. A. Lanzarone Metalevel representation of analogical
inference . . . . . . . . . . . . . . . 460
L. Ardissono and
P. Terenziani Semantic interpretation of copulative
sentences . . . . . . . . . . . . . . . 465
S. Badaloni and
A. Zanardo Typicality for plausible reasoning . . . 470
V. Roberto A distributed image-understanding system 475
Stuart I. Feldman Software Configuration Management: Past
Uses and Future Challenges . . . . . . . 1
Joelle Coutaz Architectural Design for User Interfaces 7
Christer Fernstrom The Eureka Software Factory: Concepts
and Accomplishments . . . . . . . . . . 23
J. Dick and
J. Loubersac Integrating Structured and Formal
Methods: A Visual Approach to VDM . . . 37
T. Cattel Rational Design of Distributed
Applications . . . . . . . . . . . . . . 60
P. Dauchy and
B. Marre Test Data Selection From Algebraic
Specifications: Application to an
Automatic Subway Module . . . . . . . . 80
F. J. van der Linden Specification in COLD-1 of a CAD-Package
for Drawing Shadow Masks . . . . . . . . 101
C. Ghezzi and
R. A. Kemmerer ASTRAL: An Assertion Language for
Specifying Real-Time Systems . . . . . . 122
D. Creusot and
P. Lemoine and
O. Roux and
Y. Trinquet and
A. Kung and
O. Marbach and
C. Serrano-Morales Execution Environment for ELECTRE
Applications . . . . . . . . . . . . . . 147
H. Kopetz and
R. Zainlinger and
G. Fohler and
H. Kantz and
P. Puschner and
W. Schutz An Engineering Approach Towards Hard
Real-Time System Design . . . . . . . . 166
S. Honiden and
N. Uchihira and
K. Itoh An Application of Artificial
Intelligence to Prototyping Process in
Performance Design for Real-Time Systems 189
J. Amador and
B. de Vicente and
A. Alonso Dynamically Replaceable Software: A
Design Method . . . . . . . . . . . . . 210
V. Berzins Software Merge: Models and Methods for
Combining Changes to Programs . . . . . 229
B. A. Sijtsma and
J. W. Mager A Theory for Software Design Extraction 251
A. Coen-Porisini and
F. De Paoli SESADA: An Environment Supporting
Software Specialization . . . . . . . . 266
R. W. Selby and
R. K. Madsen Metric-Driven Classification Analysis 290
J. Voas A Dynamic Failure Model For Predicting
the Impact that a Program Location Has
on the Program . . . . . . . . . . . . . 308
I. Rozman and
J. Gyorkos and
T. Dogsa Relation Between Source Code Metrics and
Structure Analysis Metrics . . . . . . . 332
M. Shepperd and
D. Ince Algebraic Validation of Software Metrics 343
F. Parisi Presicce and
A. Pierantonio An Algebraic View of Inheritance and
Subtyping in Object Oriented Programming 364
N. S. Barghouti and
G. E. Kaiser Scaling Up Rule-Based Software
Development Environments . . . . . . . . 380
G. Snelting and
F. J. Grosch and
U. Schroeder Inference-Based Support for Programming
in the Large . . . . . . . . . . . . . . 396
T. Collins and
K. Ewert and
C. Gerety and
J. Gustafson and
I. Thomas TICKLE: Object-Oriented Description and
Composition Services for Software
Engineering Environments . . . . . . . . 409
C. Tattersall Integrated Project Support Environments,
Text Generation and Technical Writing 424
D. Schefstrom The Arcs Experience . . . . . . . . . . 443
A. Fuggetta Panel Presentation . . . . . . . . . . . 465
V. Frasca The Production of Software in the
FINSIEL Group . . . . . . . . . . . . . 468
C. Jackson The Impact of Software Engineering
Researches on Industrial Practice --- A
Personal View . . . . . . . . . . . . . 472
R. Troy Impact of Methods on Productivity and
Quality . . . . . . . . . . . . . . . . 480
M. S. Feather Requirements Engineering: Getting Right
from Wrong . . . . . . . . . . . . . . . 485
A. Finkelstein A (Neat) Alphabet of Requirements
Engineering Issues . . . . . . . . . . . 489
Sol Greenspan The Scruffy Side of Requirements
Engineering . . . . . . . . . . . . . . 492
C. Potts Expediency and Appropriate Technology:
An Agenda for Requirements Engineering
Research in the 1990s . . . . . . . . . 495
P. Hruschka CASE Support for the Software Process 497
J. Kramer CASE Support for the Software Process: a
Research Viewpoint . . . . . . . . . . . 499
D. Robinson CASE Support for Large Systems . . . . . 504
W. E. Fischer CASE Seen From Both Sides of the Fence 509
B. Lang CASE Support for the Software Process:
Advances and Problems . . . . . . . . . 512
Michael Jackson Description Is Our Business . . . . . . 1
Robin Milner Concurrent Processes as Objects . . . . 9
John V. Guttag The Larch Approach to Specification . . 10
David A. Penny and
Richard C. Holt and
Michael W. Godfrey Formal Specification in Metamorphic
Programming . . . . . . . . . . . . . . 11
David Garlan and
David Notkin Formalizing Design Spaces: Implicit
Invocation Mechanisms . . . . . . . . . 31
Flemming Damm and
Bo Stig Hansen and
Hans Bruun On Type Checking in VDM and Related
Consistency Issues . . . . . . . . . . . 45
T. Clement Combining Transformation and
Posit-and-Prove in a VDM Development . . 63
Nico Plat and
Jan van Katwijk and
Kees Pronk A Case for Structured Analysis/Formal
Design . . . . . . . . . . . . . . . . . 81
Reinder J. Bril A Model-oriented Method for Algebraic
Specifications Using COLD-1 as Notation 106
David M. Goldschlag A Mechanical Formalization of Several
Fairness Notions . . . . . . . . . . . . 125
Stephan Rossig and
Michael Schenke Specification and Stepwise Development
of Communicating Systems . . . . . . . . 149
Marc Benveniste Writing Operational Semantics in Z: A
Structural Approach . . . . . . . . . . 164
Veronika Doma and
Robin Nicholl EZ: A System for Automatic Prototyping
of Z Specifications . . . . . . . . . . 189
K. M. van Hee and
L. J. Somers and
M. Voorhoeve Z and High Level Petri Nets . . . . . . 204
Hans Bruun and
Bo Stig Hansen and
Flemming Damm An Approach to the Static Semantics of
VDM-SL . . . . . . . . . . . . . . . . . 220
Michael J. Butler Behavioural Extension for CSP . . . . . 254
Marek A. Bednarczyk and
Andrzej M. Borzyszkowski Cpo's do not form a Cpo, and yet
Recursion Works . . . . . . . . . . . . 268
C. A. Middelburg and
G. R. Renardel de Lavalette LPF and MPLomega --- A Logical
Comparison of VDM SL and COLD-K . . . . 279
Thierry Cattel Tactical Tools for Distributing VDM
Specifications . . . . . . . . . . . . . 309
Ketil Stolen An Attempt to Reason About Shared-State
Concurrency in the Style of VDM . . . . 324
Morten Elvang-Goransson Reasoning About VDM Specifications . . . 343
R. D. Arthan Formal Specification of a Proof Tool . . 356
J. C. Bicarregui and
B. Ritchie Reasoning About VDM Developments Using
The VDM Support Tool in Mural . . . . . 371
Dan Craigen and
Sentot Kromodimoeljo and
Irwin Meisels and
Bill Pase and
Mark Saaltink EVES: An Overview . . . . . . . . . . . 389
Matthias Weber Deriving Transitivity of VDM-Reification
in DEVA . . . . . . . . . . . . . . . . 406
H. B. M. Jonkers Upgrading the Pre-and Postcondition
Technique . . . . . . . . . . . . . . . 428
Paul Smith and
Richard Keighley The Formal Development of a Secure
Transaction Mechanism . . . . . . . . . 457
Gerard R. Renardel de Lavalette Formal Development of a Serial Copy
Management System . . . . . . . . . . . 477
Klaus-Dieter Schewe and
Joachim W. Schmidt and
Ingrid Wetzel Specification and Refinement in an
Integrated Database Application
Environment . . . . . . . . . . . . . . 496
Pamela Zave and
Michael Jackson Techniques for Partial Specification and
Specification of Switching Systems . . . 511
G. I. Parkin and
G. O'Neill Specification of the MAA Standard in VDM 526
Jeannette M. Wing and
Amy Moormann Zaremski Unintrusive Ways to Integrate Formal
Specifications in Practice . . . . . . . 545
Stephen Bear An Overview of HP-SL . . . . . . . . . . 571
Iain Houston and
Steve King CICS Project Report: Experiences and
Results from the Use of Z in IBM . . . . 588
D. Kinnaes and
K. De Vlaminck A Debugger for a Meta-IV-like
Meta-language . . . . . . . . . . . . . 597
Peter Gorm Larsen and
Paul Bogh Lassen An Executable Subset of Meta-IV with
Loose Specification . . . . . . . . . . 604
Lynn S. Marshall and
Linda Simon Using VDM within an Object-Oriented
Framework . . . . . . . . . . . . . . . 619
A. Puccetti The Integrated Software Development and
Verification System Ates . . . . . . . . 629
D. L. Chalmers and
B. Dandanell and
J. Gortz and
J. S. Pedersen and
E. Zierau Using RAISE --- First Impressions from
the LaCoS Applications . . . . . . . . . 645
P. McParland and
P. Kilpatrick A Specification of a Complex Programming
Language Statement . . . . . . . . . . . 658
Berthold Hoffman and
Bernd Krieg-Bruckner The PROSPECTRA System . . . . . . . . . 668
Jeremy Dick and
Jerome Loubersac The Visual Presentation of VDM
Specifications . . . . . . . . . . . . . 670
Richard Moore and
Peter Froome mural and SpecBox . . . . . . . . . . . 673
Uwe Schmidt and
Hans-Martin Horcher The VDM Domain Compiler: A VDM Class
Library Generator . . . . . . . . . . . 675
Nico Plat and
Kees Pronk and
Marcel Verhoef The Delft VDM-SL Front End . . . . . . . 677
H. Heping and
H. Zedan Prototyping with Temporal VDM: A Status
Report . . . . . . . . . . . . . . . . . 681
K. M. van Hee and
L. J. Somers and
M. Voorhoeve The ExSpect tool . . . . . . . . . . . . 683
David Jordan Cadiz --- Computer Aided Design in Z . . 685
Chris Dollin The HP-ST Toolset . . . . . . . . . . . 687
CRI RAISE Tools Group The RAISE Toolset . . . . . . . . . . . 689
Iain Houston The IBM Z Tool . . . . . . . . . . . . . 691
Flemming M. Damm and
Hans Bruun and
Bo Stig Hansen The VDM-SL Editor and Consistency
Checker . . . . . . . . . . . . . . . . 693
Matthew Lee and
Ib. H. Sorensen B-Tool . . . . . . . . . . . . . . . . . 695
Christoph Blaue A VDM Subset Compiler . . . . . . . . . 697
Anonymous Preface . . . . . . . . . . . . . . . . v
Anonymous Table of contents . . . . . . . . . . . ix
John V. Guttag and
James J. Horning A Tutorial on Larch and LCL, A Larch/C
Interface Language . . . . . . . . . . . 1
J. C. P. Woodcock A Tutorial on the Refinement Calculus 79
Micheal Mac an Airchinnigh Tutorial Lecture Notes on the Irish
School of the VDM . . . . . . . . . . . 141
Chris George The RAISE Specification Language: A
Tutorial . . . . . . . . . . . . . . . . 238
Ole-Johan Dahl and
Olaf Owe Formal Development with ABEL . . . . . . 320
Bernd Krieg-Bruckner and
Einar W. Karlsen and
Junbo Liu and
Owen Traynor The PROSPECTRA Methodology and System:
Uniform Transformational (Meta-)
Development . . . . . . . . . . . . . . 363
J. R. Abrial The B Method for Large Software.
Specification, Design and Coding
(Abstract) . . . . . . . . . . . . . . . 398
Don I. Good and
William D. Young Mathematical Methods for Digital Systems
Development . . . . . . . . . . . . . . 406
Anonymous Contents . . . . . . . . . . . . . . . . ix
Anonymous Preface . . . . . . . . . . . . . . . . v
Franz Aurenhammer and
Gerd Stockl and
Emo Welzl The Post Office Problem for Fuzzy Point
Sets . . . . . . . . . . . . . . . . . . 1
Bruno Becker and
Paolo Giulio Franciosa and
Stephan Gschwind and
Thomas Ohler and
Gerald Thiemt and
Peter Widmayer An Optimal Algorithm for Approximating a
Set of Rectangles by Two Minimum Area
Rectangles . . . . . . . . . . . . . . . 13
Hanspeter Bieri and
Peter-Michael Schmidt An On-Line Algorithm for Constructing
Sweep Planes in Regular Position . . . . 27
Salvador Dominguez and
Oliver Gunther Performance Analysis of Three Curve
Presentation Schemes . . . . . . . . . . 37
Martin J. Durst Preclassification and Delayed
Classification of Boundary Entities in
Arbitrary Dimensions . . . . . . . . . . 57
Peter Engel On the Morphology of Polytopes in $ R^d
$ . . . . . . . . . . . . . . . . . . . 71
Fang Shiaofen and
Beat Bruderlin Robustness in Geometric Modeling ---
Tolerance-Based Methods . . . . . . . . 85
Edmund Ihler and
Gabriele Reich and
Peter Widmayer On Shortest Networks for Classes of
Points in the Plane . . . . . . . . . . 103
Xiao-Yi Jiang and
Horst Bunke Determination of the Symmetries of
Polyhedra and an Application to Object
Recognition . . . . . . . . . . . . . . 113
Rolf Klein Moving Along a Street . . . . . . . . . 123
Paul-Andre Monney Planar Geometric Reasoning with the
Theory of Hints . . . . . . . . . . . . 141
Heinrich Muller and
Matthias Otte Solving Algebraic Systems in
Bernstein-Bezier Representation . . . . 161
Jurg Nievergelt and
Peter Schorn and
Michele De Lorenzi and
Christoph Ammann and
Adrian Brungger XYZ: A Project in Experimental Geometric
Computation . . . . . . . . . . . . . . 171
Peter Schorn Implementing the XYZ GeoBench: A
Programming Environment for Geometric
Algorithms . . . . . . . . . . . . . . . 187
Bengt J. Nilsson and
Sven Schuierer Computing the Rectilinear Link Diameter
of a Polygon . . . . . . . . . . . . . . 203
Hartmut Noltemeier Layout of Flexible Manufacturing Systems
--- Selected Problems . . . . . . . . . 217
Thomas Roos and
Hartmut Noltemeier Dynamic Voronoi Diagrams in Motion
Planning . . . . . . . . . . . . . . . . 227
Haijo Schipper Generating Triangulations of 2-Manifolds 237
Ralf Schneider and
Hans-Peter Kriegel The TR${}^*$-tree: A New Representation
of Polygonal Objects Supporting Spatial
Queries and Operations . . . . . . . . . 249
Thomas Schreiber A Voronoi Diagram Based Adaptive
$K$-Means-Type Clustering Algorithm for
Multidimensional Weighted Data . . . . . 265
Sven Schuierer and
Gregory J. E. Rawlins and
Derick Wood A Generalization of Staircase Visibility 277
Klaus Simon A New Simple Linear Algorithm to
Recognize Interval Graphs . . . . . . . 289
Sabine Stifter Predictions About Collision Free Paths
from Intersection Tests . . . . . . . . 309
G. Grahne The Problem of Incomplete Information in
Relational Databases . . . . . . . . . . 1
G. Barth What Is All the Fuss About Neural
Networks? . . . . . . . . . . . . . . . 1
W. Brauer The New Paradigm of Informatics . . . . 15
P. A. Carlson Virtual Text and New Habits of Mind . . 25
A. B. Cremers and
Th. N. Hibbard Axioms for Concurrent Processes . . . . 54
K. Culik and
S. Dube New Methods for Image Generation and
Compression . . . . . . . . . . . . . . 69
G. Domik The Role of Visualization in
Understanding Data . . . . . . . . . . . 91
H. Edelsbrunner and
R. Seidel and
M. Sharir On the Zone Theorem for Hyperplane
Arrangements . . . . . . . . . . . . . . 108
V. Estivill-Castro and
D. Wood Sorting, Measures of Disorder, and
Worst-case Performance . . . . . . . . . 124
D. W. Fellner Object-Oriented Programming --- Does it
Help in Computer Graphics? . . . . . . . 132
S. E. Hambrusch and
H.-Y. Tu New Algorithms and Approaches for
$1$-Dimensional Layout Compaction . . . 152
H.-P. Kriegel Query Processing in Spatial Database
Systems . . . . . . . . . . . . . . . . 172
B. M. E. Moret and
H. D. Shapiro How to Find a Minimum Spanning Tree in
Practice . . . . . . . . . . . . . . . . 192
G. Muller Current Trends in Distributed Systems 204
D. H. Norrie and
A. D. Kwok Object-Oriented Distributed Artificial
Intelligence . . . . . . . . . . . . . . 225
T. Ottmann Trees --- a Personal View . . . . . . . 243
J. Preece Supporting User Testing in
Human-Computer Interaction Design . . . 256
G. Rozenberg Labeled 2-Structures . . . . . . . . . . 268
A. Salomaa Verifying and Recasting Secret Ballots
in Computer Networks . . . . . . . . . . 283
J. Schaer and
M. G. Stone Face Traverses and a Volume Algorithm
for Polyhedra . . . . . . . . . . . . . 290
A. Schwald Ada --- On the Acceptance Problems of a
Planned Innovation . . . . . . . . . . . 298
H.-W. Six and
J. Voss User Interface Development: Problems and
Experiences . . . . . . . . . . . . . . 306
I. Tomek and
H. Maurer Hypermedia --- from the Past to the
Future . . . . . . . . . . . . . . . . . 320
L. M. Wegner Let the Fingers Do the Walking: Object
Manipulation in an $ N F^2 $ Database
Editor . . . . . . . . . . . . . . . . . 337
E. Welzl Smallest Enclosing Disks (Balls and
Ellipsoids) . . . . . . . . . . . . . . 359
M. R. Williams The First Computer . . . . . . . . . . . 371
I. H. Witten and
D. L. Maulsby Evaluating Programs Formed by Example:
an Informational Heuristic . . . . . . . 388
C. H. Papadimitriou Decision-Making with Incomplete
Information . . . . . . . . . . . . . . 1
D. T. Lee and
Majid Sarrafzadeh Maximum Independent Set of a Permutation
Graph in k Tracks . . . . . . . . . . . 2
Yaw-Ling Lin and
Steven S. Skiena Algorithms for Square Roots of Graphs 12
Satoshi Fujita and
Masafumi Yamashita and
Tadashi Ae Distributed $k$-Mutual Exclusion Problem
and $k$-Coteries . . . . . . . . . . . . 22
Arvind Raghunathan and
Huzur Saran Is the Shuffle-Exchange Better Than the
Butterfly? . . . . . . . . . . . . . . . 32
A. C. Yao Weighted Random Assignments with
Application to Hashing . . . . . . . . . 42--42
Shin-Ichi Nakano and
Takao Nishizeki Scheduling File Transfers under Port and
Channel Constraints . . . . . . . . . . 43
Hsu Wen-Lian and
Ma Tze-Heng Substitution Decomposition on Chordal
Graphs and Applications . . . . . . . . 52
Atsushi Takahashi and
Ueno Shuichi and
Kajitani Yoji Mixed-Searching and Proper-Path-Width 61
Frank Wagner and
Barbara Wolfers Short Wire Routing in Convex Grids . . . 72
Dorothea Wagner A New Approach to Knock-Knee Channel
Routing . . . . . . . . . . . . . . . . 83
Tetsuo Asano and
Takeshi Tokuyama Circuit Partitioning Algorithms: Graph
Model versus Geometry Model . . . . . . 94
Endre Boros and
Peter L. Hammer and
Toshihide Ibaraki and
Kazuhiko Kawakami Identifying 2-Monotonic Positive Boolean
Functions in Polynomial Time . . . . . . 104
T. H. Hu and
C. Y. Tang and
R. C. T. Lee An Average Case Analysis of Monien and
Speckenmeyer's Mechanical Theorem
Proving Algorithm . . . . . . . . . . . 116
Chan Kwong-Fai and
Wah Lam Tak An On-Line Algorithm for Navigating in
Unknown Terrain . . . . . . . . . . . . 127
Ravi Janardan On Maintaining the Width and Diameter of
a Planar Point-Set Online . . . . . . . 137
Herbert Edelsbrunner Optimal Triangulations by
Retriangulating . . . . . . . . . . . . 150
Leonidas J. Guibas and
John E. Hershberger and
Joseph S. B. Mitchell and
Jack Scott Snoeyink Approximating Polygons and Subdivisions
with Minimum Link Paths . . . . . . . . 151
Tan Xue-Hou and
Tomio Hirata and
Yasuyoshi Inagaki An Incremental Algorithm for
Constructing Shortest Watchman Routes 163
H. S. Lee and
R. C. Chang On Hitting Grid Points in a Convex
Polygon with Straight Lines . . . . . . 176
A. Benkouar and
Y. G. Manoussakis and
V. Th. Paschos and
R. Saad On the Complexity of Some Hamiltonian
and Eulerian Problems in Edge-Colored
Complete Graphs . . . . . . . . . . . . 190
Takao Asano Dynamic Programming on Intervals . . . . 199
Wojciech Szpankowski Combinatorial Optimization Through Order
Statistics . . . . . . . . . . . . . . . 208
Leonidas J. Guibas Combinatorics and Algorithms of
Geometric Arrangements . . . . . . . . . 218
Susumu Hasegawa and
Hiroshi Imai and
Koji Hakata An Analysis of Randomized Shear Sort on
the Mesh Computer . . . . . . . . . . . 219
Wu I-Chen Efficient Parallel Divide-and-Conquer
for a Class of Interconnection
Topologies . . . . . . . . . . . . . . . 229
M. Y. Chan and
F. Y. L. Chin and
C. K. Poon Optimal Specified Root Embedding of Full
Binary Trees in Faulty Hypercubes . . . 241
Rudolf Fleischer A Tight Lower Bound for the Worst Case
of Bottom-Up Heapsort . . . . . . . . . 251
Alistair Moffat and
Ola Petersson Historical Searching and Sorting . . . . 263
Arne Andersson and
Tony W. Lai Comparison-Efficient and Write-Optimal
Searching and Sorting . . . . . . . . . 273
F. Yao Nearest Neighbors Revisited . . . . . . 283
Vladimir Estivill-Castro and
Murray Sherk Competitiveness and Response Time in
On-Line Algorithms . . . . . . . . . . . 284
Ho Jan-Ming A Linear Time Optimal Via Assignment
Algorithm for Three-Dimensional Channel
Routing . . . . . . . . . . . . . . . . 294
Luc Longpre and
Sarah Mocas Symmetry of Information and One-Way
Functions . . . . . . . . . . . . . . . 308
Hsu Lih-Hsing and
J. Y. Hwang and
T. Y. Ho and
C. H. Tsai A Linear Time Algorithm to Recognize the
Double Euler Trail for Series-Parallel
Networks . . . . . . . . . . . . . . . . 316
Hsu Tsan-Sheng and
Vijaya Ramachandran On Finding a Smallest Augmentation to
Biconnect a Graph . . . . . . . . . . . 326
Michael Kaufmann and
Gerhard Klar A Faster Algorithm for Edge-Disjoint
Paths in Planar Graphs . . . . . . . . . 336
Hans-Peter Lenhof and
Michiel Smid An Optimal Construction Method for
Generalized Convex Layers . . . . . . . 349
Michiel Smid Rectangular Point Location and the
Dynamic Closest Pair Problem . . . . . . 364
Chan Ip-Wang and
Donald K. Friesen Parallel Algorithms for Some Dominance
Problems Based on a CREW PRAM . . . . . 375
Krzysztof Diks and
Oscar Garrido and
Andrzej Lingas Parallel Algorithms for Finding Maximal
$k$-Dependent Sets and Maximal
$f$-Matchings . . . . . . . . . . . . . 385
J. Hooman Specification and Compositional
Verification of Real-Time Systems . . . 1
G. Butler Fundamental Algorithms for Permutation
Groups . . . . . . . . . . . . . . . . . xii + 238
Manuel Blum Program Checking . . . . . . . . . . . . 1
Andreas Blass and
Yuri Gurevich Randomizing Reductions of Search
Problems . . . . . . . . . . . . . . . . 10
David Sands Time Analysis, Cost Equivalence, and
Program Refinement . . . . . . . . . . . 25
Subrata Mitra and
G. Sivakumar AC-Equation Solving . . . . . . . . . . 40
Qing-Ping Tan and
Huo-Wang Chen On the Operational Interpretation of
Complex Types . . . . . . . . . . . . . 57
Kamal Lodaya and
R. Ramanujam Tense Logics for Local Reasoning in
Distributed Systems . . . . . . . . . . 71
Luca Aceto and
Uffe Engberg Failures Semantics for a Simple Process
Language with Refinement . . . . . . . . 89
Hardi Hungar Correctness of Programs over Poor
Signatures . . . . . . . . . . . . . . . 109
John Case and
Sanjay Jain and
Arun Sharma Complexity Issues for Vacillatory
Function Identification . . . . . . . . 121
Bertrand Le Saec and
Jean-Eric Pin and
Pascal Weil A Purely Algebraic Proof of McNaughton's
Theorem on Infinite Words . . . . . . . 141
Jiang Tao and
Edward McDowell and
B. Ravikumar The Structure and Complexity of Minimal
NFAs over a Unary Alphabet . . . . . . . 152
Meena Mahajan and
Kamala Krithivasan Relativised Cellular Automata and
Complexity Classes . . . . . . . . . . . 172
Sam Kim and
Robert McNaughton Computing the Order of a Locally
Testable Automaton . . . . . . . . . . . 186
Judy Goldsmith and
Lane A. Hemachandra and
Kenneth Kunen On the Structure and Complexity of
Infinite Sets with Minimal Perfect Hash
Functions . . . . . . . . . . . . . . . 212--223
Manindra Agrawal NP-hard Sets and Creativeness over
Constant Time Languages . . . . . . . . 224
Iain A. Stewart Complete Problems Involving Boolean
Labelled Structures and Projection
Translations . . . . . . . . . . . . . . 242
V. Vinay Is BP crplus P a Probabilistic Class? 261
J. Ian Munro and
Venkatesh Raman Fast Stable In-Place Sorting with O(n)
Data Moves . . . . . . . . . . . . . . . 266
V. Th. Paschos A Theorem on the Approximation of Set
Cover and Vertex Cover . . . . . . . . . 278
Sachin B. Patkar and
H. Narayanan A Fast Algorithm for the Principal
Partition of a Graph . . . . . . . . . . 288
Inga Niepel and
Peter Rossmanith Uniform Circuits and Exclusive Read
PRAMs . . . . . . . . . . . . . . . . . 307
Martin Furer and
Balaji Raghavachari Contracting Planar Graphs Efficiently in
Parallel . . . . . . . . . . . . . . . . 319
Danny Krizanc and
Lata Narayanan and
Rajeev Raman Fast Deterministic Selection on
Mesh-Connected Processor Arrays . . . . 336
Yishay Mansour and
James K. Park and
Baruch Schieber and
Sandeep Sen Improved Selection in Totally Monotone
Arrays . . . . . . . . . . . . . . . . . 347
Christos H. Papadimitriou and
Venkat Rangan and
Martha Sideri Designing Secure Communication Protocols
from Trust Specifications . . . . . . . 360
Subir Kumar Ghosh and
Anil Maheshwari and
Sudebkumar Prasant Pal and
Sanjeev Saluja and
C. E. Veni Madhavan Computing the Shortest Path Tree in a
Weak Visibility Polygon . . . . . . . . 369
Binay K. Bhattacharya Usefulness of Angle-Sweep over
Line-Sweep . . . . . . . . . . . . . . . 390
C. Ding and
G. Xiao and
W. Shan The Stability Theory of Stream Ciphers 1
R. Breu Algebraic Specification Techniques in
Object Oriented Programming Environments 1
M. Satyanarayanan An Agenda for Research in Large-Scale
Distributed Data Repositories . . . . . 2
J. H. Saltzer File System Indexing and Backup . . . . 13
D. W. Gifford and
J. W. O'Toole Intelligent File Systems for Object
Repositories . . . . . . . . . . . . . . 20
M. Sloman Using Domains for Specifying Management
Policy . . . . . . . . . . . . . . . . . 25
Anonymous Discussion Summary . . . . . . . . . . . 31
B. Joy Future Operating Systems: An
Environmental Scenario and Consequential
Challenges . . . . . . . . . . . . . . . 34
E. D. Lazowska Operating System Support for
High-Performance Architectures . . . . . 40
P. Schlichtiger Closely Coupled Systems . . . . . . . . 44
A. I. Karshmer and
J. N. Thomas Are Operating Systems at RISC? . . . . . 48
J. Zahorjan Operating Systems of the 90s and Beyond
(with Emphasis on Multiprocessing) . . . 53
J. K. Bennett and
J. B. Carter and
W. Zwaenepoel Munin: Distributed Shared Memory Using
Multi-Protocol Release Consistency . . . 56
Anonymous Discussion Summary . . . . . . . . . . . 61
H. Schmutz Autonomous Heterogeneous Computing ---
Some Open Problems . . . . . . . . . . . 63
B. Randell Coping with the Past . . . . . . . . . . 72
J. Nehmer The Immortality of Operating Systems,
or: Is Research in Operating Systems
still Justified? . . . . . . . . . . . . 77
Anonymous Discussion Summary . . . . . . . . . . . 84
H. Kopetz Event-Triggered Versus Time-Triggered
Real-Time Systems . . . . . . . . . . . 87
S. K. Tripathi and
V. Nirkhe Pre-Scheduling for Synchronization in
Hard Real-Time Systems . . . . . . . . . 102
G. Le Lann Notes on Future Operating Systems for
Real-Time Dependable Distributed
Computing . . . . . . . . . . . . . . . 109
Anonymous Discussion Summary . . . . . . . . . . . 116
F. Cristian Basic Concepts and Issues in
Fault-Tolerant Distributed Systems . . . 119
F. D. Schlichting Operating Systems and Fault-Tolerance 150
K. Birman Fault-Tolerance in Sixth-Generation
Operating Systems . . . . . . . . . . . 154
O. Babaoglu Fault Tolerance Support in Future
Operating Systems . . . . . . . . . . . 162
J. P. Banatre and
M. Banatre Fast Stable Storage as a Basis for
Fault-Tolerant Architectures . . . . . . 167
C. Horn and
B. Coghlan and
N. Harris and
J. Jones Stable Memory --- Another Look . . . . . 171
R. Kroger and
E. Nett System Level Support for Dependable
Distributed Applications . . . . . . . . 178
Anonymous Discussion Summary . . . . . . . . . . . 182
B. C. Neuman Protection and Security Issues for
Future Systems . . . . . . . . . . . . . 184
R. Cole Some Issues in Security Arising from
Distribution . . . . . . . . . . . . . . 202
H. G. Stiegler Security: System Development in a New
Context . . . . . . . . . . . . . . . . 207
H. Hartig and
W. Kuhnhauser and
J. Liedtke Issues in Security and Fault Tolerance 212
Anonymous Discussion Summary . . . . . . . . . . . 217
R. Needham What Next? Some Speculations . . . . . . 220
A. Z. Spector Some Thoughts on Systems Challenges for
the 1990s . . . . . . . . . . . . . . . 223
M. Gien Next Generation Operating Systems
Architecture . . . . . . . . . . . . . . 227
M. Tokoro Toward Computing Systems for the 2000s 233
F. Hofmann and
P. Schlenk and
T. Eirich Encapsulation and Interaction in Future
Operating Systems . . . . . . . . . . . 241
H. D. Wettstein The Explainable Operating System . . . . 247
M. Shapiro Soul: An Object-Oriented OS Framework
for Object Support . . . . . . . . . . . 251
S. Shrivastava and
D. McCue Operating System Support for
Object-Oriented Distributed Systems . . 256
Anonymous Discussion Summary . . . . . . . . . . . 258
M. G. Lamming Towards a Human Memory Prosthesis . . . 262
S. J. Mullender Systems for the Nineties --- Distributed
Multimedia Systems . . . . . . . . . . . 273
R. G. Herrtwich The Role of Performance, Scheduling and
Resource Reservation in Multimedia
Systems . . . . . . . . . . . . . . . . 279
P. Molzberger On Parallel Consciousness . . . . . . . 1
W. v. Lucadou Complementarity and Non-locality in
Complex Systems . . . . . . . . . . . . 21
E. Caianiello Systems and Uncertainty . . . . . . . . 56
P. Quadranti The Construction of Space and the Logics
of Quantum Mechanics . . . . . . . . . . 67
D. Gernert Cellular Automata and the Concept of
Space . . . . . . . . . . . . . . . . . 94
G. Fritsch Multipurpose and Special Purpose
Computers . . . . . . . . . . . . . . . 103
R. Knecht Implementation of Divide-and-Conquer
Algorithms on Multiprocessors . . . . . 121
R. Vollmar Some Remarks on Synchronization Problems 137
M. Makhaniok and
V. Cherniavsky and
R. Manner and
O. Stucky Effective Implementation of Distributed
Arbitration in Multiprocessor Systems 148
M. P. Pensini and
G. Mauri and
F. Gardin Flowshop and Travelling Salesman Problem 157
R. Hauser and
H. Horner and
R. Manner and
M. Makhaniok Architectural Considerations for NERV
--- a General Purpose Neural Network
Simulation System . . . . . . . . . . . 183
V. G. Dobson Associative Neural Networks in Analog
VLSI: Advantages of Decrementing
Algorithms . . . . . . . . . . . . . . . 196
H.-J. Eikmeyer Connectionist Models of Utterance
Production . . . . . . . . . . . . . . . 219
G. J. Dalenoort Self-Organization of Informational
Systems . . . . . . . . . . . . . . . . 231
B. B. Rieger Distributed Semantic Representations of
Word Meanings . . . . . . . . . . . . . 243
H. Wermus Logic of Cognitive Representations and
Their Evolution . . . . . . . . . . . . 274
H. Atmanspacher and
F. R. Krueger and
H. Scheingraber A Modal Propositional Calculus for
Quantum Facts and Dynamical Theories . . 304
F. W. Mundemann Self-Organization in Computational
Systems . . . . . . . . . . . . . . . . 315
J. D. Becker Adaptation and Extension: Learning in
Rigid Systems . . . . . . . . . . . . . 326
A. A. Katsikas and
J. S. Nicolis Chaotic Dynamics of Generating Markov
Partitions, and Linguistic Sequences
Mimicking Zipf's Law . . . . . . . . . . 335
P. Schuster Optimization and Complexity in Molecular
Biology and Physics . . . . . . . . . . 364
H. P. Schwefel Understanding Evolution as a Collective
Strategy for Groping in the Dark . . . . 388
H. Muhlenbein Parallel Genetic Algorithms, Population
Genetics, and Combinatorial Optimization 398
M. Gorges-Schleuter ASPARAGOS, A Parallel Genetic Algorithm
and Population Genetics . . . . . . . . 407
P. M. Allen and
M. J. Lesser Evolution: Travelling in an Imaginary
Landscape . . . . . . . . . . . . . . . 419
W. Banzhaf Finding the Global Minimum of a
Low-Dimensional Spin-Glass Model . . . . 442
P. Ablay Ten Theses Regarding the Design of
Controlled Evolutionary Strategies . . . 457
H. Atmanspacher Incommensurability of Liouvillean
Dynamics and Information Dynamics . . . 482
R. Lohmann Selforganization by Evolutionary
Strategies in Visual Systems . . . . . . 500
J. Hesser and
R. Manner and
O. Stucky On Steiner Trees and Genetic Algorithms 509
R. Lanzelotte and
P. Valduriez and
M. Ziane and
J.-P. Cheiney Optimization of Nonrecursive Queries in
OODBs . . . . . . . . . . . . . . . . . 1
Z. Jiao and
P. M. D. Gray Optimization of Methods in a
Navigational Query Language . . . . . . 22
D. D. Straube and
M. Tamer Ozsu Execution Plan Generation for an
Object-Oriented Data Model . . . . . . . 43
C. C. Low and
H. Lu and
B. C. Ooi and
J. Han Efficient Access Methods in Deductive
and Object-Oriented Databases . . . . . 68
T. C. Przymusinski Semantics of Disjunctive Logic Programs
and Deductive Databases . . . . . . . . 85
J. Paredaens and
P. Peelman and
L. Tanca G-Log: A Declarative Graphical Query
Language . . . . . . . . . . . . . . . . 108
F. Giannotti and
D. Pedreschi and
D. Sacca and
C. Zaniolo Nondeterminism in Deductive Databases 129
W. Chen Declarative Specification and Evaluation
of Database Updates . . . . . . . . . . 147
E. Waller Schema Updates and Consistency . . . . . 167
M. H. Scholl and
C. Laasch and
M. Tresch Updatable Views in Object-Oriented
Databases . . . . . . . . . . . . . . . 189
P. T. Wood Syntactic Characterizations of 1-Bounded
Datalog Programs . . . . . . . . . . . . 208
J. Van den Bussche Evaluation and Optimization of Complex
Object Selections . . . . . . . . . . . 226
Y. Sagiv On Testing Effective Computability of
Magic Programs . . . . . . . . . . . . . 244
J. D. Ullman A Comparison of Deductive and
Object-Oriented Database Systems . . . . 263
R. Torlone and
P. Atzeni Updating Deductive Databases with
Functional Dependencies . . . . . . . . 278
Y. Caseau Constraints in an Object-Oriented
Deductive Database . . . . . . . . . . . 292
N. Coburn and
G. E. Weddell Path Constraints for Graph-Based Data
Models: Towards a Unified Theory of
Typing Constraints, Equations, and
Functional Dependencies . . . . . . . . 312
T. Minohara and
M. Tokoro Providing Dynamic Type Abstractions and
Specifications for Persistent
Information . . . . . . . . . . . . . . 332
E. Sciore Multidimensional Versioning for
Object-Oriented Databases . . . . . . . 355
A. Ngu and
L. Wong and
S. Widjojo On Canonical and Non-Canonical
Classifications . . . . . . . . . . . . 371
M. Tsukamoto and
S. Nishio and
M. Fujio DOT: A Term Representation Using DOT
Algebra for Knowledge-bases . . . . . . 391
S. Brass and
U. W. Lipeck Semantics of Inheritance in Logical
Object Specifications . . . . . . . . . 411
R. J. Wieringa A Formalization of Objects Using
Equational Dynamic Logic . . . . . . . . 431
M. Atkinson A Vision of Persistent Systems . . . . . 453
M. Jeusfeld and
M. Jarke From Relational to Object-Oriented
Integrity Simplification . . . . . . . . 460
V. Kuchenhoff On the Efficient Computation of the
Difference Between Consecutive Database
States . . . . . . . . . . . . . . . . . 478
J.-P. Cheiney and
Y.-N. Huang Set-Oriented Propagation of Updates into
Transitively Closed Relations . . . . . 503
T. Imielinski and
S. Naqui and
K. Vadaparty Querying Design and Planning Databases 524
L. Kalinichenko and
V. Zadorozhny A Generalized Information Resource Query
Language and Basic Query Evaluation
Technique . . . . . . . . . . . . . . . 546
O. Boucelma and
J. Le Maitre An Extensible Functional Query Language
for an Object-Oriented Database System 567
C. Zaniolo Efficient Processing of Declarative
Rule-Based Languages for Databases . . . 1
M. Dorochevsky and
J. Noye and
O. Thibault Has Dedicated Hardware for Prolog a
Future? . . . . . . . . . . . . . . . . 17
C. Moss Commercial Applications of Large Prolog
Knowledge Bases . . . . . . . . . . . . 32
G. Ellis Compiling Conceptual Graphs . . . . . . 41
M. Willems Subsumption in Knowledge Graphs . . . . 56
F. Baader and
B. Hollunder A Terminological Knowledge
Representation System with Complete
Inference Algorithms . . . . . . . . . . 67
H. Jaeger An Introduction to Dynamic Concept
Systems . . . . . . . . . . . . . . . . 87
M. Lenzerini and
A. Schaerf Querying Concept-Based Knowledge Bases 107
A. Artale and
F. Cesarini and
G. Soda Subsumption Computation in an
Object-Oriented Data Model . . . . . . . 124
N. Guarino A Concise Presentation of ITL . . . . . 141
R. Backofen and
L. Euler and
G. Gorz Distributed Disjunctions for LIFE . . . 161
C. Ribeiro and
A. Porto Reasoning with Maximal Time Intervals 171
V. Kriauciukas Nonclassical Models for Logic Programs 179
E. Borger and
E. Riccobene Logical Operational Semantics of Parlog
--- Part I: And-Parallellism . . . . . . 191
Z. Markov A Tool for Building Connectionist-Like
Networks Based on Term Unification . . . 199
W.-F. Riekert Providing Declarative Access to a
Processing System for Satellite Image
Data . . . . . . . . . . . . . . . . . . 214
J. Treur Declarative Functionality Descriptions
of Interactive Reasoning Modules . . . . 221
Y. Caseau Rule-Aided Constraint Resolution in
LAURE . . . . . . . . . . . . . . . . . 237
A. V. Mantsivoda Flang: A Functional Logic Language . . . 257
P. Bonzon Processing Functional Definitions as
Declarative Knowledge: A Reduced
Bytecode Implementation of a Functional
Logic Machine . . . . . . . . . . . . . 271
A. King and
P. Soper Reducing Scheduling Overheads for
Concurrent Logic Programs . . . . . . . 279
H. Kautz and
B. Selman A General Framework for Knowledge
Compilation . . . . . . . . . . . . . . 287
Y. Cosmadopoulos and
M. Sergot and
R. W. Southwick Data-Driven Transformation of
Meta-Interpreters: A Sketch . . . . . . 301
M. Bruynooghe and
V. Dumortier and
G. Janssens Improving the Efficiency of Constraint
Logic Programming Languages by Deriving
Specialized Versions . . . . . . . . . . 309
G. Yaoqing and
W. Dingxing and
Q. Xiaolin and
H. Zhiyi and
H. Shouren Parallelizing Prolog on Shared-Memory
Multiprocessors . . . . . . . . . . . . 318
E. Lamma and
P. Mello Processing Abductive Reasoning via
Contextual Logic Programming . . . . . . 336
M. Hanus Efficient Implementation of Narrowing
and Rewriting . . . . . . . . . . . . . 344
P. Balbiani and
A. Herzig and
M. Lima Marques TIM: The Toulouse Inference Machine for
Non-Classical Logic Programming . . . . 366
H. Boley and
M. Meier and
C. Moss and
M. M. Richter and
A. A. Voronkov PANEL: Declarative and Procedural
Paradigms --- Do they Really Compete? 383
M. Aronsson and
L.-H. Eriksson The GCLA II Programming Language . . . . 399
C. Beierle and
G. Meyer and
H. Semle A Brief Description of the PROTOS-L
System . . . . . . . . . . . . . . . . . 402
S. Fricke and
M. Hein PCPL --- PROLOG Constraint Processing
Library, Version 2.0 . . . . . . . . . . 405
N. Guarino A Mini-Description of the ITL System . . 408
P. Hanschke and
A. Abecker and
D. Drollinger TAXON: A Concept Language with Concrete
Domains . . . . . . . . . . . . . . . . 411
M. Hanus The ALF System: An Efficient
Implementation of a Functional Logic
Language . . . . . . . . . . . . . . . . 414
K. Hinkelmann and
M. Harm and
T. Labisch Transforming Horn Clauses for Forward
Reasoning . . . . . . . . . . . . . . . 417
A. Mantsivoda and
V. Petukhin Implementation of the Functional Logic
Language Flang . . . . . . . . . . . . . 420
M. Meier and
J. Schimpf SEPIA 3.0 --- An Extensible Prolog
System . . . . . . . . . . . . . . . . . 422
M. Meyer and
J. Muller and
S. Schrodl FIDO: Exploring Finite Domain
Consistency Techniques in Logic
Programming . . . . . . . . . . . . . . 425
H.-J. Burckert A Resolution Principle for a Logic with
Restricted Quantifiers . . . . . . . . . 1
M. Gittins Debugging Parallel Strand Programs . . . 1
M. Dorochevsky and
K. Schuerman and
A. Veron and
J. Xu Constraint Handling, Garbage Collection
and Execution Model Issues in ElipSys 17
P. Kefalas and
T. J. Reynolds Controlling Search with Meta-Brave . . . 29
P. Szeredi Solving Optimization Problems in the
Aurora Or-parallel Prolog System . . . . 39
R. Moolenaar and
H. Van Acker and
B. Demoen $ \kappa \alpha \pi \pi \alpha $: A
Kernel Andorra Prolog Parallel
Architecture Design . . . . . . . . . . 54
I. de Castro Dutra A Flexible Scheduler in the Andorra-I
System . . . . . . . . . . . . . . . . . 70
R. Bahgat The Pandora Abstract Machine: An
Extension of JAM . . . . . . . . . . . . 83
K. Ali and
R. Karlsson and
S. Mudambi Performance of MUSE on the BBN Butterfly
TC2000 . . . . . . . . . . . . . . . . . 104
A. Beaumont Scheduling Strategies and Speculative
Work . . . . . . . . . . . . . . . . . . 120
W. Ertel Performance of Competitive
Or-parallelism . . . . . . . . . . . . . 132
G. Gupta and
M. Hermenegildo ACE: And/Or-parallel Copying-based
Execution of Logic Programs . . . . . . 146
K. O. M. De Bosschere Blackboard Communication in Prolog . . . 159
G. Succi and
G. Marino Data Parallelism in Logic Programming 173
H. Bourzoufi and
G. Goncalves and
P. Lecouffe and
B. Toursel An Efficient Binding Management In
Or-parallel Model . . . . . . . . . . . 185
A. Goswami and
M. Bell and
M. Joseph ISL: An Interval Logic for the
Specification of Real-Time Programs . . 1
Chaochen Zhou and
M. R. Hansen and
A. P. Ravn and
H. Rischel Duration Specifications for Shared
Processors . . . . . . . . . . . . . . . 21
J. Coenen and
J. Hooman A Compositional Semantics for
Fault-Tolerant Real-Time Systems . . . . 33
Mats Daniels Modelling Real-Time Behaviour with an
Interval Time Calculus . . . . . . . . . 53
Odile Millet Multicycles and RTL Logic Satisfiability 73
Abha Moitra Voluntary Preemption: a Tool in the
Design of Hard Real-Time Systems . . . . 87
K. T. Narayana Observing Task Preemption in Ada 9X . . 107
L. Breveglieri and
A. Cherubini and
S. Crespi-Reghizzi Real-Time Scheduling by Queue Automata 131
J. Davies and
D. Jackson and
S. Schneider Broadcast Communication for Real-Time
Processes . . . . . . . . . . . . . . . 149
R. de Lemos and
A. Saeed and
T. Anderson Analysis of Timeliness Requirements in
Safety-Critical Systems . . . . . . . . 171
V. Yodaiken and
K. Ramamritham Verification of a Reliable Net Protocol 193
N. Shankar Mechanical Verification of a Generalized
Protocol for Byzantine Fault Tolerant
Clock Synchronization . . . . . . . . . 217
J. Rushby Formal Specification and Verification of
a Fault-Masking and Transient-Recovery
Model for Digital Flight-Control Systems 237
B. Deylon and
O. Maler On Fault-Tolerant Symbolic Computations 259
K. D. Heidtmann Temporal Logic Applied to Reliability
Modelling of Fault-Tolerant Systems . . 271
P. Krishnan and
P. D. Mosses Specifying Asynchronous Transfer of
Control . . . . . . . . . . . . . . . . 291
W. Janssen and
J. Zwiers Protocol Design by Layered
Decomposition: A Compositional Approach 307
R. Kurki-Suonio and
K. Systa and
J. Vain Scheduling in Real-Time Models . . . . . 327
Y. Naik A Temporal Approach to Requirement
Specification of Real-Time Systems . . . 341
J. A. Plaice RLucid, a General Real-Time Dataflow
Language . . . . . . . . . . . . . . . . 363
R. Cardell-Oliver A Mechanized Theory for the Verification
of Real-Time Program Code uUing Higher
Order Logic . . . . . . . . . . . . . . 375
C. J. Fidge Specification and Verification of
Real-Time Behaviour Using Z and RTL . . 393
D. J. Scholefield and
H. S. M. Zedan TAM: A Formal Framework for the
Development of Distributed Real-Time
Systems . . . . . . . . . . . . . . . . 411
M. Richard and
O. Roux An Attempt to Confront Asynchronous
Reality to Synchronous Modelization in
the ESTEREL Language . . . . . . . . . . 429
F. de Boer and
J. Hooman The Real-Time Behaviour of
Asynchronously Communicating Processes 451
J. C. M. Baeten and
J. A. Bergstra Asynchronous Communication in Real Space
Process Algebra . . . . . . . . . . . . 473
A. Jeffrey Translating Timed Process Algebra into
Prioritized Process Algebra . . . . . . 493
Y. Ortega-Mallen Operational Semantics for Timed
Observations . . . . . . . . . . . . . . 507
D. Murphy and
D. Pitt Real-Timed Concurrent Refineable
Behaviours . . . . . . . . . . . . . . . 529
H. Toetenel and
J. van Katwijk Stepwise Development of Model-Oriented
Real-Time Specifications from
Action/Event Models . . . . . . . . . . 547
P. Coesmans and
M. J. Wieczorek Formal Specification of Fault-Tolerant
Real-Time Systems Using Minimal 3-Sorted
Modal Logic . . . . . . . . . . . . . . 571
Y. Kesten and
A. Pnueli Timed and Hybrid Statecharts and Their
Textual Representation . . . . . . . . . 591
C. Stirling Taming Infinite State Spaces . . . . . . 1
H. Huttel Silence is Golden: Branching
Bisimilarity is Decidable for
Context--Free Processes . . . . . . . . 2
H. Korver Computing Distinguishing Formulas for
Branching Bisimulation . . . . . . . . . 13
H. Andersen and
G. Winskel Compositional Checking of Satisfaction 24
R. De Nicola and
A. Fantechi and
S. Gnesi and
G. Ristori An Action Based Framework for Verifying
Logical and Behavioural Properties of
Concurrent Systems . . . . . . . . . . . 37
R. Cleaveland and
B. Steffen A Linear-Time Model-Checking Algorithm
for the Alternation-Free Modal
Mu-Calculus . . . . . . . . . . . . . . 48
A. P. Sistla and
L. D. Zuck Automatic Temporal Verification of
Buffer Systems . . . . . . . . . . . . . 59
W. Bevier and
J. Sògaard-Andersen Mechanically Checked Proofs of Kernel
Specifications . . . . . . . . . . . . . 70
S. Gjessing and
S. Krogdahl and
E. Munthe-Kaas A Top Down Approach to the Formal
Specification of SCI Cache Coherence . . 83
G. S. Avrunin and
J. C. Corbett and
U. A. Buy Integer Programming in the Analysis of
Concurrent Systems . . . . . . . . . . . 92
M. Barbeau and
G. v. Bochmann The Lotos Model of a Fault Protected
System and its Verification Using a
Petri Net Based Approach . . . . . . . . 103
A. Rasse Error Diagnosis in Finite Communicating
Systems . . . . . . . . . . . . . . . . 114
R. Vemuri and
A. Sridhar Temporal Precondition Verification of
Design Transformations . . . . . . . . . 125
H. Lin Pam: A Process Algebra Manipulator . . . 136
C. T. Jensen The Concurrency Workbench with
Priorities . . . . . . . . . . . . . . . 147
S. Mauw and
G. Veltink A Proof Assistant for PSF . . . . . . . 158
A. Finkel and
L. Petrucci Avoiding State Explosion by Composition
of Minimal Covering Graphs . . . . . . . 169
J.-C. Fernandez and
L. Mounier ``On the fly'' Verification of
Behavioural Equivalences and Preorders 181
C. Jard and
Th. Jeron Bounded-memory Algorithms for
Verification On-the-fly . . . . . . . . 192
R. Enders and
T. Filkorn and
D. Taubner Generating BDDs for Symbolic Model
Checking in CCS . . . . . . . . . . . . 203
H. Hiraishi and
K. Hamaguchi and
H. Ochi and
S. Yajima Vectorized Symbolic Model Checking of
Computation Tree Logic for Sequential
Machine Verification . . . . . . . . . . 214
T. Filkorn Functional Extension of Symbolic Model
Checking . . . . . . . . . . . . . . . . 225
W. Mao and
G. Milne An Automated Proof Technique for
Finite--State Machine Equivalence . . . 233
E. Brinksma From Data Structures to Process
Structure . . . . . . . . . . . . . . . 244
D. L. Dill and
A. J. Hu and
H. Wong-Toi Checking for Language Inclusion Using
Simulation Relations . . . . . . . . . . 255
N. de Francesco and
P. Inverardi A Semantic Driven Method to Check the
Finiteness of CCS Processes . . . . . . 266
M. Mutz Using the HOL Prove Assistant for
Proving the Correctness of Term
Rewriting Rules reducing Terms of
Sequential Behaviour . . . . . . . . . . 277
M. Nesi Mechanizing a Proof by Induction of
Process Algebra Specifications in Higher
Order Logic . . . . . . . . . . . . . . 288
C.-J. Seger and
J. J. Joyce A Two-Level Formal Verification
Methodology using HOL and COSMOS . . . . 299
L. Christoff and
I. Christoff Efficient Algorithms for Verification of
Equivalences for Probabilistic Processes 310
D. K. Probst and
H. F. Li Partial-Order Model Checking: A Guide
for the Perplexed . . . . . . . . . . . 322
P. Godefroid and
P. Wolper Using Partial Orders for the Efficient
Verification of Deadlock Freedom and
Safety Properties . . . . . . . . . . . 332
J. Feigenbaum and
C. Lund and
J. A. Kahn Complexity Results for POMSET Languages 343
D. M. Goldschlag Mechanically Verifying Safety and
Liveness Properties of Delay Insensitive
Circuits . . . . . . . . . . . . . . . . 354
K. Schneider and
R. Kumar and
T. Kropf Automating Most Parts of Hardware Tools
in HOL . . . . . . . . . . . . . . . . . 365
J. Sifakis An Overview and Synthesis on Timed
Process Algebras . . . . . . . . . . . . 376
C. Courcoubetis and
M. Yannakakis Minimum and Maximum Delay Problems In
Real-Time Systems . . . . . . . . . . . 399
K. Hamaguchi and
H. Hiraishi and
S. Yajima Formal Verification of Speed-Dependent
Asynchronous Circuits Using Symbolic
Model Checking of Branching Time Regular
Temporal Logic . . . . . . . . . . . . . 410
A. Gabrielian and
R. Iyer Verifying Properties of HMS Machine
Specifications of Real-Time Systems . . 421
A. Jeffrey A Linear Time Process Algebra . . . . . 432
U. Holmer and
W. Yi and
K. Larsen Deciding Properties of Regular Real
Timed Processes . . . . . . . . . . . . 443
C. Corcoubetis and
S. Graf and
J. Sifakis An Algebra of Boolean Processes . . . . 454
M. Langevin and
E. Cerny Comparing Generic State Machines . . . . 466
G. G. de Jong An Automata Theoretic Approach to
Temporal Logic . . . . . . . . . . . . . 477
Kenji Koyama and
Ueli M. Maurer and
Tatsuaki Okamoto and
Scott A. Vanstone New Public-Key Schemes Based on Elliptic
Curves over the Ring $ Z_n $ . . . . . . 252--266
M. Abadi and
M. Burrows and
B. Lampson and
G. Plotkin A Calculus for Access Control in
Distributed Systems (Invited) . . . . . 1
Marie-Jeanne Toussaint Deriving the Complete Knowledge of
Participants in Cryptographic Protocols
(Extended Abstract) . . . . . . . . . . 24
Ray Bird and
Inder Gopal and
Amir Herzberg and
Phil Janson and
Shay Kutten and
Refik Molva and
Moti Yung Systematic Design of Two-Party
Authentication Protocols . . . . . . . . 44
Douglas R. Stinson Combinatorial characterizations of
authentication codes . . . . . . . . . . 62--73
Douglas R. Stinson Universal Hashing and Authentication
Codes . . . . . . . . . . . . . . . . . 74--85
Paul Camion and
Claude Carlet and
P. Charpin and
N. Sendrier On Correlation-Immune Functions . . . . 86--100
R. M. Capocelli and
A. De Santis and
L. Gargano and
U. Vaccaro On the Size of Shares for Secret Sharing
Schemes . . . . . . . . . . . . . . . . 101--113
Cynthia Dwork On Verification in Secret Sharing . . . 114--128
Torben Pryds Pedersen Non-interactive and
Information-Theoretic Secure Verifiable
Secret Sharing . . . . . . . . . . . . . 129--140
Michael J. Fischer and
Rebecca N. Wright Multiparty Secret Key Exchange Using a
Random Deal of Cards (Extended Abstract) 141
Eli Biham and
Adi Shamir Differential Cryptanalysis of Snefru,
Khafre, REDOC-II, LOKI and Lucifer
(Extended Abstract) . . . . . . . . . . 156
Anne Tardy-Corfdir and
Henry Gilbert A Known Plaintext Attack of FEAL-4 and
FEAL-6 . . . . . . . . . . . . . . . . . 172
Hikaru Morita and
Kazuo Ohta and
Shoji Miyaguchi A Switching Closure Test to Analyze
Cryptosystems (Extended Abstract) . . . 183
Bert den Boer and
Antoon Bosselaers An Attack on the Last Two Rounds of MD4 194
Bert den Boer and
Antoon Bosselaers An Attack on the Last Two Rounds of MD4 194
Yeow Meng Chee and
Antoine Joux and
Jacques Stern The Cryptanalysis of a New Public-Key
Cryptosystem Based on Modular Knapsacks 204
Dror Lapidot and
Adi Shamir A one-round, two-prover, zero-knowledge
protocol for NP . . . . . . . . . . . . 213--224
Joe Kilian and
Ronitt Rubinfeld Interactive Proofs with Space Bounded
Provers . . . . . . . . . . . . . . . . 225--231
Shang-Hua Teng Functional Inversion and Communication
Complexity . . . . . . . . . . . . . . . 232--241
Steven Rudich The Use of Interaction in Public
Cryptosystems (Extended Abstract) . . . 242
Tatsuaki Okamoto and
Kouichi Sakurai Efficient algorithms for the
construction of hyperelliptic
cryptosystems . . . . . . . . . . . . . 267--278
Neal Koblitz CM-Curves with Good Cryptographic
Properties . . . . . . . . . . . . . . . 279--287
Shigeo Tsujii and
Jinhui Chao A New ID-Based Key Sharing System . . . 288--299
Michael Luby Pseudo-random Generators from One-Way
Functions (Invited Abstract) . . . . . . 300
Jacques Patarin New results on pseudorandom permutation
generators based on the DES scheme . . . 301--213
Colin D. Walter Faster Modular Multiplication by Operand
Scaling . . . . . . . . . . . . . . . . 313
Tatsuaki Okamoto and
Kazuo Ohta Universal Electronic Cash . . . . . . . 324
Birgit Pfitzmann and
Michael Waidner How to Break and Repair a ``Provably
Secure'' Untraceable Payment System
(Extended Abstract) . . . . . . . . . . 338
Charles H. Bennett and
Gilles Brassard and
Claude Crépeau and
Marie-Hél\`ene Skubiszewska Practical Quantum Oblivious Transfer . . 351
Albert G. Broscius and
Jonathan M. Smith Exploiting Parallelism in Hardware
Implementation of the DES . . . . . . . 367
Donald Beaver Foundations of Secure Interactive
Computing . . . . . . . . . . . . . . . 377
Silvio Micali and
Phillip Rogaway Secure Computation (Abstract) . . . . . 392
Kenneth R. Iversen A Cryptographic Scheme for Computerized
General Elections . . . . . . . . . . . 405
Donald Beaver Efficient Multiparty Protocols Using
Circuit Randomization . . . . . . . . . 420
Charles Rackoff and
Daniel R. Simon Non-interactive Zero-Knowledge Proof of
Knowledge and Chosen Ciphertext Attack 433
Ivan Bjerre Damgård Towards Practical Public Key Systems
Secure against Chosen Ciphertext Attacks 445
Yvo Desmedt and
Yair Frankel Shared Generation of Authenticators and
Signatures (Extended Abstract) . . . . . 457
David Chaum and
Eug\`ene van Heijst and
Birgit Pfitzmann Cryptographically Strong Undeniable
Signatures, Unconditionally Secure for
the Signer (Extended Abstract) . . . . . 470
Anonymous Author Index . . . . . . . . . . . . . . 485