Sofsem 2005: Theory And Practice Of Computer Science : 31st Conference On Current Trends In Theory And Practice Of Computer Science, Liptovský Ján, Slovakia, January 22-28, 2005 : Proceedings

This volume contains papers selected for presentation at the 31st Annual C- ference on Current Trends in Theory and Practice of Informatics – SOFSEM 2005, held on January 22–28, 2005 in LiptovskyJ ́ an, ́ Slovakia. The series of SOFSEM conferences, organized alternately in the Czech - public and Slovakia since 1974, has a well-established tradition. The SOFSEM conferences were originally intended to break the Iron Curtain in scienti?c - change. After the velvet revolution SOFSEM changed to a regular broad-scope international conference. Nowadays, SOFSEM is focused each year on selected aspects of informatics. This year the conference was organized into four tracks, each of them complemented by two invited talks: – Foundations of Computer Science (Track Chair: Bernadette Charron-Bost) – Modeling and Searching Data in the Web-Era (Track Chair: Peter Vojt ́ a? s) – Software Engineering (Track Chair: M ́ aria Bielikova) ́ – Graph Drawing (Track Chair: Ondrej Syk ́ ora) The aim of SOFSEM 2005 was, as always, to promote cooperation among professionalsfromacademiaandindustryworkinginvariousareasofinformatics. Each track was complemented by two invited talks. The SOFSEM 2005 Program Committee members coming from 13 countries evaluated 144 submissions (128 contributed papers and 16 student research - rum papers). After a careful review process (counting at least 3 reviews per paper), followed by detailed discussions in the PC, and a co-chairs meeting held on October 8, 2005 in Bratislava, Slovakia, 44 papers (overall acceptance rate 34. Front Matter....Pages - Discovering Treewidth....Pages 1-16 From Research Prototypes to Industrial Strength Open Source Products – The ObjectWeb Experience....Pages 17-27 How Hard Is It to Take a Snapshot?....Pages 28-37 Logical Foundations for Data Integration....Pages 38-40 Recent Advances in Graph Drawing....Pages 41-41 The Hyperdatabase Network – New Middleware for Searching and Maintaining the Information Space....Pages 42-46 Architecture of a Business Framework for the .NET Platform and Open Source Environments....Pages 47-52 Progress on Crossing Number Problems....Pages 53-61 Greedy Differential Approximations for Min Set Cover....Pages 62-71 A Methodology of Visual Modeling Language Evaluation....Pages 72-81 Local Computations on Closed Unlabelled Edges: The Election Problem and the Naming Problem....Pages 82-91 A Hierarchical Markovian Mining Approach for Favorite Navigation Patterns....Pages 92-95 Non-planar Orthogonal Drawings with Fixed Topology....Pages 96-105 A Topology-Driven Approach to the Design of Web Meta-search Clustering Engines....Pages 106-116 Computing Upward Planar Drawings Using Switch-Regularity Heuristics....Pages 117-126 Serial and Parallel Multilevel Graph Partitioning Using Fixed Centers....Pages 127-136 Two-Layer Planarization: Improving on Parameterized Algorithmics....Pages 137-146 On the Stability of Approximation for Hamiltonian Path Problems....Pages 147-156 Robustness of Composed Timed Systems....Pages 157-166 Topology Generation for Web Communities Modeling....Pages 167-177 Recursion Versus Replication in Simple Cryptographic Protocols....Pages 178-187 Modeling Data Integration with Updateable Object Views....Pages 188-198 Fixed-Parameter Tractable Algorithms for Testing Upward Planarity....Pages 199-208 Read/Write Based Fast-Path Transformation for FCFS Mutual Exclusion....Pages 209-218 Adjustment of Indirect Association Rules for the Web....Pages 219-228 Anonymous Communication with On-line and Off-line Onion Encoding....Pages 229-238 Characteristic Patterns for LTL....Pages 239-249 Planar Straight-Line Drawing in an $\mathcal{O}(n)\times \mathcal{O}(n)$ Grid with Angular Resolution $\it \Omega$ (1/ n )....Pages 250-258 Modeling Nested Relationships in XML Documents Using Relational Databases....Pages 259-268 RAQ: A Range-Queriable Distributed Data Structure....Pages 269-277 On Some Weighted Satisfiability and Graph Problems....Pages 278-287 On the Security and Composability of the One Time Pad....Pages 288-297 Lower Bounds on the OBDD Size of Graphs of Some Popular Functions....Pages 298-309 XML-Based Declarative Access Control....Pages 310-319 VCD: A Visual Formalism for Specification of Heterogeneous Software Architectures....Pages 320-329 Cost-Constrained Minimum-Delay Multicasting....Pages 330-339 Ontology-Based Inconsistency Management of Software Requirements Specifications....Pages 340-349 Suffix Tree Based Data Compression....Pages 350-359 Tier Aspect Model Based on Updatable Views....Pages 360-363 Well-Founded Metamodeling for Model-Driven Architecture....Pages 364-367 Stepwise Optimization Method for k -CNN Search for Location-Based Service....Pages 368-371 An Approach for Integrating Analysis Patterns and Feature Diagrams into Model Driven Architecture....Pages 372-375 Outerplanar Crossing Numbers of 3-Row Meshes, Halin Graphs and Complete p -Partite Graphs....Pages 376-379 Fast Bit-Vector Algorithms for Approximate String Matching Under Indel Distance....Pages 380-384 Feature Selection by Reordering....Pages 385-389 A Management Scheme for the Basic Types in High Level Languages....Pages 390-393 Bayesian Networks in Software Maintenance Management....Pages 394-398 A Multiagent System Aiding Information Retrieval in Internet Using Consensus Methods....Pages 399-402 Interval-Valued Data Structures and Their Application to e-Learning....Pages 403-407 Boolean Functions with a Low Polynomial Degree and Quantum Query Algorithms....Pages 408-412 Representation of Extended RBAC Model Using UML Language....Pages 413-417 A Methodology for Writing Class Contracts....Pages 418-422 Volumes of 3D Drawings of Homogenous Product Graphs....Pages 423-426 Back Matter....Pages - [pt. 1] Invited Talks -- Discovering Treewidth -- From Research Prototypes To Industrial Strength Open Source Products : The Objectweb Experience -- How Hard Is It To Take A Snapshot? -- Logical Foundations For Data Integration -- Recent Advances In Graph Drawing -- The Hyperdatabase Network : New Middleware For Searching And Maintaining The Information Space -- Architecture Of A Business Framework For The .net Platform And Open Source Environments -- Progress On Crossing Number Problems -- [pt. 2] Full Contributed Papers -- Greedy Differential Approximations For Min Set Cover -- A Methodology Of Visual Modeling Language Evaluation -- Local Computations On Closed Unlabelled Edges : The Election Problem And The Naming Problem -- A Hierarchical Markovian Mining Approach For Favorite Navigation Patterns -- Non-planar Orthogonal Drawings With Fixed Topology -- A Topology-driven Approach To The Design Of Web Meta-search Clustering Engines --^ Computing Upward Planar Drawings Using Switch-regularity Heuristics -- Serial And Parallel Multilevel Graph Partitioning Using Fixed Centers -- Two-layer Planarization : Improving On Parameterized Algorithmics -- On The Stability Of Approximation For Hamiltonian Path Problems -- Robustness Of Composed Timed Systems -- Topology Generation For Web Communities Modeling -- Recursion Versus Replication In Simple Cryptographic Protocols -- Modeling Data Integration With Updateable Object Views -- Fixed-parameter Tractable Algorithms For Testing Upward Planarity -- Read/write Based Fast-path Transformation For Fcfs Mutual Exclusion -- Adjustment Of Indirect Association Rules For The Web -- Anonymous Communication With On-line And Off-line Onion Encoding -- Characteristic Patterns For Ltl -- Planar Straight-line Drawing In An O(n)xo(n) Grid With Angular Resolution [ohm](1/n) -- Modeling Nested Relationships In Xml Documents Using Relational Databases --^ Raq : A Range-queriable Distributed Data Structure -- On Some Weighted Satisfiability And Graph Problems -- On The Security And Composability Of The One Time Pad -- Lower Bounds On The Obdd Size Of Graphs Of Some Popular Functions -- Xml-based Declarative Access Control -- Vcd : A Visual Formalism For Specification Of Heterogeneous Software Architectures -- Cost-constrained Minimum-delay Multicasting -- Ontology-based Inconsistency Management Of Software Requirements Specifications -- [pt. 3] The Best Student Paper -- Suffix Tree Based Data Compression -- [pt. 4] Short Contributed Papers -- Tier Aspect Model Based On Updatable Views -- Well-founded Metamodeling For Model-driven Architecture -- Stepwise Optimization Method For K-cnn Search For Location-based Service -- An Approach For Integrating Analysis Patterns And Feature Diagrams Into Model Driven Architecture -- Outerplanar Crossing Numbers Of 3-row Meshes, Halin Graphs And Complete P-partite Graphs --^ Fast Bit-vector Algorithms For Approximate String Matching Under Indel Distance -- Feature Selection By Reordering -- A Management Scheme For The Basic Types In High Level Languages -- Bayesian Networks In Software Maintenance Management -- A Multiagent System Aiding Information Retrieval In Internet Using Consensus Methods -- Interval-valued Data Structures And Their Application To E-learning -- Boolean Functions With A Low Polynomial Degree And Quantum Query Algorithms -- Representation Of Extended Rbac Model Using Uml Language -- A Methodology For Writing Class Contracts -- Volumes Of 3d Drawings Of Homogenous Product Graphs -- Author Index. Peter Vojtáš ... [et Al.] (eds.). Electronic Book Available Via Springer Link. Includes Bibliographical References And Index. This book constitutes the refereed proceedings of the 31st Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2005, held in Liptovský Ján, Slovakia in January 2005. The 28 revised full papers and 16 revised short papers presented together with 8 invited contributions were carefully reviewed and selected from 144 submissions. The papers were organized in four topical tracks on foundations of computer science, modeling and searching data in the web area, software engineering, and graph drawing and discrete computational mathematics About a quarter of a century, the notion of treewidth has now played a role in many investigations in algorithmic graph theory.