SOFSEM'99: Theory and Practice of Informatics: 26th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, ... (Lecture Notes in Computer Science, 1725)

✍ Scribed by Jan Pavelka (editor), Gerard Tel (editor), Miroslav Bartosek (editor)

• Publisher: Springer
• Year: 1999
• Tongue: English
• Leaves: 510
• Category: Library

✦ Synopsis

This year the SOFSEM conference is coming back to Milovy in Moravia to th be held for the 26 time. Although born as a local Czechoslovak event 25 years ago SOFSEM did not miss the opportunity oe red in 1989 by the newly found freedom in our part of Europe and has evolved into a full-?edged international conference. For all the changes, however, it has kept its generalist and mul- disciplinarycharacter.Thetracksofinvitedtalks,rangingfromTrendsinTheory to Software and Information Engineering, attest to this. Apart from the topics mentioned above, SOFSEM’99 oer s invited talks exploring core technologies, talks tracing the path from data to knowledge, and those describing a wide variety of applications. TherichcollectionofinvitedtalkspresentsonetraditionalfacetofSOFSEM: that of a winter school, in which IT researchers and professionals get an opp- tunity to see more of the large pasture of today’s computing than just their favourite grazing corner. To facilitate this purpose the prominent researchers delivering invited talks usually start with a broad overview of the state of the art in a wider area and then gradually focus on their particular subject.

✦ Table of Contents

Lecture Notes in Computer Science
SOFSEM’99: Theory and Practice of Informatics
Preface
SOFSEM'99 Committees
Organization
Table of Contents
Quantum Challenges
Prologue
Introduction
State of the Art
Mathematical Framework
Quantum Resources
Quantum Principles
Apt Killers
Obstacles
Quantum Challenges
Quantum Processors
Quantum Cryptography
Quantum Entanglement
Decoherence
Managing Decoherence and Imperfections
Quantum Measurement
Quantum Information Theory
Bypassing Quantum Limitations
Quantum Automata Theory
Quantum Algorithms and Communication Protocols
Foundational Issues
Quantum Paradoxical Phenomena
Exploring Relations and Impacts to Other Sciences
Stability of Approximation Algorithms for Hard Optimization Problems
Introduction
The Concept of the Stability of Approximation
Stability of Approximation and Traveling Salesperson Problem
Superstability and Knapsack Problem
Conclusion and Discussion
Algorlthms on Compressed Strings and Arrays
Introduction
Sequential Searching in Compressed Texts
Periodicities in Strings
Run-Length Compression
1-Dimensional Straight-Line Programs
The Lempel-Ziv Compression
LZW Compression
Texts Compressed by Using Antidictionaries
Sequential Searching in Compressed Arrays
2-Dimensional Run-Length Encoding
2-Dimensional Straight-Line Programs
2D-Compressions in Terms of Finite Automata
2D-Compression Using LZ-Encodings
Compressibility of Subsegments
Parallel Searching in Compressed Texts and Arrays
The Compressed Language Membership Problems
Word Equations
Morphic Representations
Final Remarks
WWW Based Collaboration with the BSCW System
Introduction
General Approach of the BSCW System
Implementation of the BSCW System
Functionality of the BSCW System
Usage of the BSCW System
Related Systems
Conclusions
Middleware and Quality of Service
Introduction
Some Key Concepts
Why Mix Middleware and QoS?
QoS in Distributed Multimedia Systems
Layered Model
Main Operations
QoS Specification
QoS Mechanisms
Communication Layers
Network Layer.
Transport Layer.
QoS Architectures
Platform Example: QoS-A
Conclusion QoS
Middleware
Characteristics
OMA Architecture
CORBA Architecture
ORB Functionalities
QoS CORBA Architectures
Example: TAO
Comparison Tables
Bases for a QoS CORBA
Conclusion on QoS and Middleware
Future Work
Dynamic Reconfiguration of CORBA-Based
Introduction
Using an Interpreted Language
LuaOrb
LuaOrb's Client Binding
LuaOrb's Server Binding
Access to the Interface Repository
Configuration of Applications
Interfaces and Application Configuration
Event-Driven Applications
Component Modification
Final Remarks
Fast, Error Correcting Parser Combinators: A Short Tutorial
Introduction
Basic Combinator Parsing
Extending the Library
Advantages of this Approach
Analysis
Error Locating Parsing Combinators
Error Correcting Parsing Combinators
Continuation Based Parser Combinators
Further Details
Error Reporting
How to Stop?
Pitfalls
Speeding Up
Conclusions and Further Reading
IBM SanFrancisco: Java Based Business Components, and New tools to Develop Applications
Introduction
Overview of SanFrancisco
Foundation Layer
Common Business Objects
Core Business Processes
Architectural Aspects of SanFrancisco
System Organization
The Java Environment.
Layered Architecture.
Distribution.
Component Structure
Model Driven Development.
Design Patterns.
Framework Extensions.
San Francisco Programming Models.
SanFrancisco and Enterprise JavaBeans.
Traditional Ways to Develop SanFrancisco Applications
A Wish List for SanFrancisco Development Tools
Business Component Prototyper
Overview
BC-Prototyper Building Blocks
GUI Generation
Use of Components in BC-Prototyper
The Architecture of BC-Prototyper
The Code Generator
A Look Back at the Wish List
Conclusion
Databases and the World Wide Web
Introduction
Web Information Systems
Databases in WIS
Data Modeling in WIS
From the Web to Databases: Extraction and Querying
From Databases to the Web: Generating and Managing Sites
The Next Step: XML
Exploiting Formality in Software Engineering
Introduction
Three Converging Lines of Research
Advancement of Formal Methods
Technology Transfer of Formal Methods
Formalisation of Industrial Methods
Results of Technology Transfer Projects
Heterogeneous Development Using VDM and B
MaFMeth: The Measurement and Analysis of a Formal Method
SPECTRUM: A Step Toward a Unified Method
Evidence of Error Reduction
Evidence of Cost Reduction
Relative Benefit of Formal Activities
Ongoing Work and Conclusions
The Integration of Two Industrially Relevant Formal Methods (VDM+B)
Objects, Associations and Subsystems: A Hierarchical Approach to Encapsulation
Conclusions
Software Change and Evolution
Introduction
Minicycle of Change
Partitioned Annotations
Change Propagation
Other Work
Browsers
Change Impact Analysis
Evolvable Architectures
Conclusions and Future Work
Distributed Simulation with Cellular Automata: Architecture and Applications
Introduction
Background of Cellular Automata Concepts
Introduction
Simple 1D Cellular Automata
Requirements for Computability in Cellular Automata
Information in CA
Computation in Cellular Automata
Modeling with Cellular Automata
Execution Models for Cellular Automata
Synchronous Cellular Automata versus Asynchronous Cellular Automata
Types of Simulation
Discrete-Time Models and Time-Driven Simulation
Discrete-Event Models and Event-Driven Simulation
Parallel Simulation of Cellular Automata Models
Parallel Synchronous Cellular Automata Simulation
Parallel Asynchronous Cellular Automata Simulation
Cellular Automata as Models for Fluid Flow
Introduction
Associating Physics with the LGA-CA
The FHP Model
The Lattice Boltzmann Method
Parallelism and Applications
Selected Applications
Modeling Growth and Form in a Moving Fluid Using Synchronous Cellular Automata
Biological Background
A CA model of Flow and Nutrient Distributions
A CA Model of the Growth Process
Parallelization of the CA models
Comparison of the Load Balancing Strategies
Simulated Growth Forms in a Mono Directional Flow Regime
Simulated Growth Forms in a Bidirectional (Alternating)Flow Regime
Discussion
Ising Spin Model Using Asynchronous Cellular Automata
The Ising Spin Model
The Dynamics in the Ising Spin Model
Continuous-Time Ising Spin System
Optimistic Simulation of the Parallel ACA Model
Summary and Discussion
Supporting Group-By and Pipelining in Bitmap-Enabled Query Processors
Introduction
Bitmap Indexing Revisited
Pipelining
Optimization of Group-By
Execution of Group-By
Conclusions
Coherent Concepts, Robust Learning
Introduction
Preliminaries
Class Coherency
Distributional Coherency
Learning Linear Separators
Robustness
Coherency Implies Robustness
Conclusions
Application of Artificial Neural networks for Different Engineering Problems
Introduction
Artificial Neural Nets
Restoration of Colors in Scanned Images
Color Representation, Distortions and Approach
Color Data Acquisition and Neural Network Architecture
Discussion
Data Evaluation Method for Hybrid Gas Sensing Systems
Selected Case Study
Qualitative Analysis
Quantitative Analysis
Discussion
Internet Information Search and Delivery
Neural Network Clusterisation
Hierarchical Radius-Based Competitive Learning
Advantages of HRCL
Discussion
Prediction of Functional Yield of Chips in Semiconductor Industry Applications
Data Samples
Methods
Results
Discussion
Real Time Processing of Nerve Signals for Controlling a Limb Prostheses
The Neurosensor
Data Set
Classification Using Kohonens SOM
Control Unit of the Prostheses
Discussion
Conclusion
Factor Oracle: A New Structure for Pattern Matching
Introduction
Factor Oracle
Construction Algorithm
On-line Algorithm
String Matching
A Linear Algorithm in the Worst Case
Experimental Results
Conclusions
Principles of Forecasting - A Short Overview
History
Why Forecast?
Economical and Legal Aspects of Forecasting
The Forecasting Process
Problem Identification and Description
Relevant Input Variables Selection
Prediction Quality Specification
Choosing a Forecasting Model
Fitting Method Specification
Fitting and Validation Data Specification
Model Architecture Optimizing
Testing
Model Implementation and Using
Forecasting Formulas
Prediction Intervals
Judgmental Forecasting
Forecasting Software
Forecasting Journals, Conferences and Internet Addresses
Two Examples
Foreign Exchange Rate Forecasting
Electric Load Forecasting
Conclusion
UPV-Curry: An Incremental Curry Interpreter
Introduction
Preliminaries
Curry
Operational Semantics of Curry
UPV-Curry
Incremental Defininitional Trees
Incremental Evaluation
Experimental Results
Conclusions
Quantum Finite Multitape Automata
Introduction
Quantum vs. Probabilistic Automata
Decomposable Bulk Synchronous Parallel Computers
Introduction
Description of dBSP
Elementary Algorithms
Period of Pipelined Computation
A BSP Simulation of dBSP
Conclusion
Component Change and Version Indentification in SOFA
Introduction
Overview of SOFA
SOFA Component Compatibility and Versioning
Determining Component Compatibility
Revision Numbers and Change Indications
Examples of Use
Related Work
Open Issues and Future Research
Conclusion
Pattern Equations and Equations with Stuttering
Introduction
Basic Definitions
Notation
Pattern Equations
NP-Completeness of the Pattern-Equation Problem
Elimination of Conjunction and Disjunction
Stuttering Equations
Garbage Collection for Mobile and Replicated Objects
Introduction
Object References Overview
Locators
The Main Xdoor
The Main Locator
Garbage Collection
Garbage Collection for Migratable Objects
Reference Counting Fault Tolerance
Related Work and Conclusions
Randomized Gossiping by Packets in Faulty Networks
Introduction
Model Description and Preliminaries
Randomized Gossiping Algorithm
Probability of Correctness
Conclusions
Object-Oriented Specification with the Parallel Multi-Label-Selective e -calculus?
Introduction
The Parallel Multi-Label-Selective lambda-calculus
The Translation
Conclusions and Future Work
Simulation Problems for One-Counter Machines
Introduction
Decidability for Weak One-Counter Machines
Undecidability for One-Counter Machines
Proof of the Belt Theorem
On Semantics of petrl Nets over Partial Algebra
Introduction
Basic Definitions
Petri Nets over Partial Algebra
Relationships between Classes of Weak and Strong Marking Graphs
Towards Possibillistic Decision Functions with Minimum-Based Sugeno Integrals
Decision Problem under Uncertainty
Possibilistic Measures and Minimum-Based Sugeno Integral
Possibilistic Decision Functions
An Example+.1667em--0+.1667emDecision Making Based on Coin Tossing
Quantum Finite One-Counter Automata
Introduction
Classical One-Counter Automata
Quantum Finite One-Counter Automata
Language Recognition for QF1CA
Negative Values of the Counter
Languages Recognizable by QF1CA
Recognizing L3 and L4
A Performance Comparison of Mobile Agents and RPC
Introduction
Prior Studies
Experiment Design
Experiment Description
Experiment Variables
The Experiment Environment
Results
Timing Results
Latency Results.
Memory Use
Network Load
CPU Load
IO Load
Conclusion
Cyclic Cutwidth of the Mesh
Introduction
Definitions and Notations
Lower Bounds
Conclusions
Some Afterthoughts on Hopfield Networks
Introduction
A Size-Optimal Simulation of Asymmetric Networks
Convergence Time Analysis
Approximating the Minimum Energy Problem
Turing Universality of Finite Analog Hopfield Nets
A Persistent-Set Approach to Abstract State-Space Construction in Verification
Introduction
Preliminaries
Abstraction
Partial-Order Methods and Abstraction
Persistent Sets
Conclusion
Computational Power of Neuroidal Nets*
Introduction
Neuroidal Nets
Variants of Neuroidal Nets
Bounded Weight Neuroidal Nets and Finite Automata
Neuroidal Nets with Finite Weights and Turing Machines
Conclusions
Cellular Automata with Dynamically Reconfigurable Buses
Introduction
Basic Notions
RCA Are in the Second Machine Class
A Characterization of RCA Time by TM Reversal
Summary
Author Index