SOFSEM 2007 : theory and practice of computer science : 33rd Conference on Current Trends in Theory and Practice of Computer Science, Harrachov, Czech Republic, January 20-26, 2007 : proceedings

This book constitutes the refereed proceedings of the 33rd Conference on Current Trends in Theory and Practice of Computer Science, SOFSEM 2007, held in Harrachov, Czech Republic in January 2007. The 69 revised full papers, presented together with 11 invited contributions were carefully reviewed and selected from 283 submissions. The papers were organized in four topical tracks on foundations of computer science, multi-agent systems, emerging Web technologies, as well as dependable software and systems. Front Matter....Pages - Graphs from Search Engine Queries....Pages 1-8 Model-Checking Large Finite-State Systems and Beyond....Pages 9-28 Interaction and Realizability....Pages 29-50 A Short Introduction to Computational Social Choice....Pages 51-69 Distributed Models and Algorithms for Mobile Robot Systems....Pages 70-87 Point-to-Point Shortest Path Algorithms with Preprocessing....Pages 88-102 Games, Time, and Probability: Graph Models for System Design and Analysis....Pages 103-110 Agreement Technologies....Pages 111-113 Automatic Testing of Object-Oriented Software....Pages 114-129 Architecture-Based Reasoning About Performability in Component-Based Systems....Pages 130-137 Multimedia Retrieval Algorithmics....Pages 138-154 Size of Quantum Finite State Transducers....Pages 155-163 Weighted Nearest Neighbor Algorithms for the Graph Exploration Problem on Cycles....Pages 164-175 Straightening Drawings of Clustered Hierarchical Graphs....Pages 176-187 Improved Upper Bounds for λ -Backbone Colorings Along Matchings and Stars....Pages 188-199 About the Termination Detection in the Asynchronous Message Passing Model....Pages 200-211 Fast Approximate Point Set Matching for Information Retrieval....Pages 212-223 A Software Architecture for Shared Resource Management in Mobile Ad Hoc Networks....Pages 224-234 Compressed Prefix Sums....Pages 235-247 On Optimal Solutions for the Bottleneck Tower of Hanoi Problem....Pages 248-259 Competitive Maintenance of Minimum Spanning Trees in Dynamic Graphs....Pages 260-271 Exact Max 2-Sat : Easier and Faster....Pages 272-283 Maximum Finding in the Symmetric Radio Networks with Collision Detection....Pages 284-294 An Approach to Modelling and Verification of Component Based Systems....Pages 295-308 Improved Undecidability Results on the Emptiness Problem of Probabilistic and Quantum Cut-Point Languages....Pages 309-319 On the (High) Undecidability of Distributed Synthesis Problems....Pages 320-329 Maximum Rigid Components as Means for Direction-Based Localization in Sensor Networks....Pages 330-341 Online Service Management Algorithm for Cellular/WALN Multimedia Networks....Pages 342-346 A Simple Algorithm for Stable Minimum Storage Merging....Pages 347-356 Generating High Dimensional Data and Query Sets....Pages 357-366 Partial vs. Complete Domination: t -Dominating Set....Pages 367-376 Estimates of Data Complexity in Neural-Network Learning....Pages 377-387 Concurrent and Located Synchronizations in π -Calculus....Pages 388-399 Efficient Group Key Agreement for Dynamic TETRA Networks....Pages 400-409 Algorithmic Aspects of Minimum Energy Edge-Disjoint Paths in Wireless Networks....Pages 410-421 The P k Partition Problem and Related Problems in Bipartite Graphs....Pages 422-433 Spatial Selection of Sparse Pivots for Similarity Search in Metric Spaces....Pages 434-445 A Model of an Amorphous Computer and Its Communication Protocol....Pages 446-455 A Branch-and-Bound Algorithm to Solve Large Scale Integer Quadratic Multi-Knapsack Problems....Pages 456-464 Indexing Factors with Gaps....Pages 465-474 Information Efficiency....Pages 475-487 Deterministic Simulation of a NFA with k –Symbol Lookahead....Pages 488-497 Mobility Management Using Virtual Domain in IPv6-Based Cellular Networks....Pages 498-509 Restarting Tree Automata....Pages 510-521 A Polynomial Time Constructible Hitting Set for Restricted 1-Branching Programs of Width 3....Pages 522-531 Formal Translation Directed by Parallel LLP Parsing....Pages 532-543 Self-adaptive Lagrange Relaxation Algorithm for Aggregated Multicast....Pages 544-553 A Language for Reliable Service Composition....Pages 554-565 Operational Semantics of Framed Temporal Logic Programs....Pages 566-578 Constraints for Argument Filterings....Pages 579-590 Performance Analysis of a Multiagent Architecture for Passenger Transportation....Pages 591-600 Teacher-Directed Learning with Mixture of Experts for View-Independent Face Recognition....Pages 601-611 FTTH-Enhanced Mini-System m TBCP-Based Overlay Construction and Evaluation....Pages 612-623 On Efficient Resource Allocation in Communication Networks....Pages 624-635 Protecting Agent from Attack in Grid Computing III ....Pages 636-643 Incremental Learning of Planning Operators in Stochastic Domains....Pages 644-655 Competitive Contract Net Protocol....Pages 656-668 Agent Oriented Methodology Construction and Customization with HDA....Pages 669-681 Building an Ontological Base for Experimental Evaluation of Semantic Web Applications....Pages 682-692 Semantic Web Approach in Designing a Collaborative E-Item Bank System....Pages 693-704 A Hybrid Region Weighting Approach for Relevance Feedback in Region-Based Image Search on the Web....Pages 705-715 Rapid Development of Web Interfaces to Heterogeneous Systems....Pages 716-725 Enhancing Security by Embedding Biometric Data in IP Header....Pages 726-737 Runtime-Efficient Approach for Multiple Continuous Filtering in XML Message Brokers....Pages 738-749 A Semantic Peer-to-Peer Overlay for Web Services Discovery....Pages 750-760 Multi-document Summarization Based on Cluster Using Non-negative Matrix Factorization....Pages 761-770 A Program Slicing Based Method to Filter XML/DTD Documents....Pages 771-782 A Hybrid Approach for XML Similarity....Pages 783-795 Personalized Presentation in Web-Based Information Systems....Pages 796-807 Immune-Inspired Online Method for Service Interactions Detection....Pages 808-818 Separation of Concerns and Consistent Integration in Requirements Modelling....Pages 819-831 Checking Interaction Consistency in MARMOT Component Refinements....Pages 832-843 Towards a Versatile Contract Model to Organize Behavioral Specifications....Pages 844-855 Improved Processing of Textual Use Cases: Deriving Behavior Specifications....Pages 856-868 A Dialogue-Based NLIDB System in a Schedule Management Domain....Pages 869-877 Experimental Assessment of the Practicality of a Fault-Tolerant System....Pages 878-887 A Polynomial-Time Checkable Sufficient Condition for Deadlock-Freedom of Component-Based Systems....Pages 888-899 Extracting Zing Models from C Source Code....Pages 900-910 Parameterised Extra-Functional Prediction of Component-Based Control Systems – Industrial Experience....Pages 911-922 Explicit Connectors in Component Based Software Engineering for Distributed Embedded Systems....Pages 923-934 Back Matter....Pages -