Recent Developments in the Theory of Arrangements of Surfaces / Micha Sharir
Session 1(a)
Dynamic Compressed Hyperoctrees with Application to the N-body Problem / Srinivas Aluru ; Fatih E. Sevilgen
Largest Empty Rectangle among a Point Set / Jeet Chaudhuri ; Subhas C. Nandy
Session 1(b)
Renaming Is Necessary in Timed Regular Expressions / Philippe Herrmann
Product Interval Automata: A Subclass of Timed Automata / Deepak D'Souza ; P. S. Thiagarajan
Session 2(a)
The Complexity of Rebalancing a Binary Search Tree / Rolf Fagerberg
Fast Allocation and Deallocation with an Improved Buddy System / Erik D. Demaine ; Ian J. Munro
Session 2(b)
Optimal Bounds for Transformations of ω-Automata / Christof Löding
CTL+ Is Exponentially More Succinct than CTL / Thomas Wilke
A Top-Down Look at a Secure Message / Martín Abadi ; Cédric Fournet ; Georges Gonthier
Session
Explaining Updates by Minimal Sums / Jürgen Dix ; Karl Schlechta
A Foundation for Hybrid Knowledge Bases / James J. Lu ; Neil V. Murray ; Erik Rosenthal
Hoare Logic for Mutual Recursion and Local Variables / David von Oheimb
Explicit Substitutions and Programming Languages / Jean-Jacques Lévy ; Luc Maranget
Session 5(a)
Approximation Algorithms for Routing and Call Scheduling in All-Optical Chains and Rings / Luca Becchetti ; Miriam Di Ianni ; Alberto Marchetti-Spaccamela
A Randomized Algorithm for Flow Shop Scheduling / Naveen Garg ; Sachin Jain ; Chaitanya Swamy
Session 5(b)
Synthesizing Distributed Transition Systems from Global Specifications / Ilaria Castellani ; Madhavan Mukund
Beyond Region Graphs: Symbolic Forward Analysis of Timed Automata / Supratik Mukhopadhyay ; Andreas Podelski
Implicit Temporal Query Languages: Towards Completeness / Nicole Bidoit ; Sandra de Amo
On the Undecidability of Some Sub-classical First-Order Logics / Matthias Baaz ; Agata Ciabattoni ; Christian Fermüller ; Helmut Veith
How to Compute with DNA* / Lila Kari ; Mark Daley ; Greg Gloor ; Rani Siromoney ; Laura F. Landweber
Session 7(a)
A High Girth Graph Construction and a Lower Bound for Hitting Set Size for Combinatorial Rectangles / L. Sunil Chandran
Protecting Facets in Layered Manufacturing / Jörg Schwerdt ; Michiel Smid ; Ravi Janardan ; Eric Johnson ; Jayanth Majhi
Session 7(b)
The Receptive Distributed π-Calculus (Extended Abstract) / Roberto M. Amadio ; Gérard Boudol ; Cédric Lhoussaine
Series and Parallel Operations on Pomsets / Zoltán Ésik ; Satoshi Okawa
Unreliable Failure Detectors with Limited Scope Accuracy and an Application to Consensus / Achour Mostéfaoui ; Michel Raynal
Graph Isomorphism: Its Complexity and Algorithms / Seinosuke Toda
Session 9(a)
Computing with Restricted Nondeterminism: The Dependence of the OBDD Size on the Number of Nondeterministic Variables / Martin Sauerhoff
Lower Bounds for Linear Transformed OBDDs and FBDDs (Extended Abstract) / Detlef Sieling
Session 9(b)
A Unifying Framework for Model Checking Labeled Kripke Structures, Modal Transition Systems, and Interval Transition Systems / Michael Huth
Graded Modalities and Resource Bisimulation / Flavio Corradini ; Rocco De Nicola ; Anna Labella
Session 10(a)
The Non-recursive Power of Erroneous Computation / Christian Schindelhauer ; Andreas Jakoby
Analysis of Quantum Functions (Preliminary Version) / Tomoyuki Yamakami
Session 10(b)
On Sets Growing Continuously / Bernhard Heinemann
Model Checking Knowledge and Time in Systems with Perfect Recall (Extended Abstract) / Ron van der Meyden ; Nikolay V. Shilov
FST&TCS - ISAAC Joint Session Talks
The Engineering of Some Bipartite Matching Programs / Kurt Mehlhorn
Author Index
Invited Talk
Recent Developments in the Theory of Arrangements of Surfaces / Micha Sharir
Validation of Synchronous Reactive Systems: From Formal Verification to Automatic Testing / N. Halbwachs ; P. Raymond
Emerging Application Domains and the Computing Fabric / K. V. Palem
Regular Papers
The Game of the Name in Cryptographic Tables / R. M. Amadio ; S. Prasad
A Parallel Approximation Algorithm for the Max Cut Problem on Cubic Graphs / T. Calamoneri ; I. Finocchi ; Y. Manoussakis ; R. Petreschi
Rapid Prototyping Techniques for Fuzzy Controllers / C. Chantrapornchai ; S. Tongsima ; E. Sha
Transactional Cache Management with Aperiodic Invalidation Scheme in Mobile Environments / I. Chung ; C.-S. Hwang
Observable Sharing for Functional Circuit Description / K. Claessen ; D. Sands
Relating May and Must Testing Semantics for Discrete Timed Process Algebras / L. F. L. DÃaz ; D. de Frutos Escrig
A Framework for Formal Reasoning about Open Distributed Systems / a. Fredlund ; D. Gurov
Structural Sharing and Efficient Proof-Search in Propositional Intuitionistic Logic / D. Galmiche ; D. Larchey-Wendling
Verifying Probabilistic Programs Using a Hoare like Logic / J. I. den Hartog
An Expressive Extension of TLC / J. G. Henriksen
Completeness and Decidability of a Fragment of Duration Calculus with Iteration / D. V. Hung ; D. P. Guelev
Logical Relations in Circuit Verification / M. Indrika
Lemma Generalization and Non-unit Lemma Matching for Model Elimination / K. Iwanuma ; K. Kishino
On Automating Inductive and Non-inductive Termination Methods / F. Kamareddine ; F. Monin
Asynchronous Links in the PBC and M-Nets / H. Klaudel ; F. Pommereau
Demand-Driven Model Checking for Context-Free Processes / J. Knoop
Programming the Mobility Behaviour of Agents by Composing Itineraries / S. W. Loke ; H. Schmidt ; A. Zaslavsky
Faster Model Checking for Open Systems / M. Mukund ; K. N. Kumar ; S. A. Smolka
An Argumentation Approach to Semantics of Declarative Programs with Defeasible Inheritance / E. Nantajeewarawat ; V. Wuwongse
Entailment of Non-structural Subtype Constraints / J. Niehren ; T. Priesnitz
A CPS-Transform of Constructive Classical Logic / I. Ogata
Formal Verification of the MCS List-Based Queuing Lock / K. Ogata ; K. Futatsugi
BDD-Nodes Can Be More Expressive / F. Reffel
Formal Verification of Descriptions with Distinct Order of Memory Operations / G. Ritter ; H. Hinrichsen ; H. Eveking
Beyond Tamaki-Sato Style Unfold/Fold Transformations for Normal Logic Programs / A. Roychoudhury ; C. R. Ramakrishnan ; I. V. Ramakrishnan
Separators Are as Simple as Cutsets / A. Seth ; H. Shen ; K. Li ; S.-Q. Zheng
Ant Colony Optimization for the Ship Berthing Problem / C. J. Tong ; H. C. Lau ; A. Lim
Poster Session Abstracts
Security Modeling and Evaluation for the Mobile Code Paradigm / A. H. W. Chan ; M. R. Lyu
CASA - Structured Design of a Specification Language for Intelligent Agents / S. Flake ; C. Geiger
An Efficient Location Management by Optimal Location Area Partitioning in PCS Networks / J.-M. Gil
Programming with Explicit Regions / K. Kagawa
A Verification Technique Based on Syntactic Action Refinement in a TCSP-like Process Algebra and the Hennessy-Milner-Logic / M. Majster-Cederbaum ; F. Salger
Formal Verification of Secret Sharing Protocol Using Coq / K. M. Yew ; M. Z. Rahman ; S. P. Lee
Deduction in Logic of Association Rules / N. D. Quang ; J. Rauch
Asynchronous Migration in Parallel Genetic Programming / S. Tongchim ; P. Chongstitvatana
Verification Results for a Multimedia Protocol / T. Tsang ; R. Lai
Multipoint-to-Point ABR Service with Fair Intelligent Congestion Control in ATM Networks / Q. Yu ; D. B. Hoang
Author Index
Invited Talks
Validation of Synchronous Reactive Systems: From Formal Verification to Automatic Testing / N. Halbwachs ; P. Raymond
Emerging Application Domains and the Computing Fabric / K. V. Palem
Decision Rules, Bayes' Rule and Rough Sets / Z. Pawlak
A New Direction in System Analysis: From Computation with Measurements to Computation with Perceptions / L. A. Zadeh
On Text Mining Techniques for Personalization / C. C. Aggarwal ; P. S. Yu
A Road to Discovery Science / S. Arikawa
Rough Computing: Foundations and Applications
Calculi of Granules Based on Rough Set Theory: Approximate Distributed Synthesis and Granular Semantics for Computing with Words / L. Polkowski ; A. Skowron
Discovery of Rules about Complications / S. Tsumoto
Rough Genetic Algorithms / P. Lingras ; C. Davies
Classifying Faults in High Voltage Power Systems: A Rough-Fuzzy Neural Computational Approach / L. Han ; J. F. Peters ; S. Ramanna ; R. Zhai
Rough Set Theory and Its Applications
Toward Spatial Reasoning in the Framework of Rough Mereology
An Algorithm for Finding Equivalence Relations from Tables with Non-deterministic Information / H. Sakai ; A. Okuma
On the Extension of Rough Sets under Incomplete Information / J. Stefanowski ; A. Tsoukias
On Rough Relations: An Alternative Formulation / Y. Y. Yao ; T. Wang
Formal Rough Concept Analysis / J. Saquer ; J. S. Deogun
Noise Reduction in Telecommunication Channels Using Rough Sets and Neural Networks / R. Krolikowski ; A. Czyzewski
Rough Set Analysis of Electrostimilation Test Database for the Prediction of Post-Operative Profits in Cochlear Implanted Patients / H. Skarzynski ; B. Kostek
A Rough Set-Based Approach to Text Classification / A. Chouchoulas ; Q. Shen
Modular Rough Fuzzy MLP: Evolutionary Design / P. Mitra ; S. Mitra ; S. K. Pal
Approximate Reducts and Association Rules: Correspondence and Complexity Results / H. S. Nguyen ; D. Slezak
Handling Missing Values in Rough Set Analysis of Multi-Attribute and Multi-Criteria Decision Problems / S. Greco ; B. Matarazzo ; R. Slowinski
The Generic Rough Set Inductive Logic Programming Model and Motifs in Strings / A. Siromoney ; K. Inoue
Rough Problem Settings for Inductive Logic Programming / C. Liu ; N. Zhong
Using Rough Sets with Heuristics to Feature Selection / J. Z. Dong ; S. Ohsuga
The Discretization of Continuous Attributes Based on Compatibility Rough Set and Genetic Algorithm / L. Sun ; W. Gao
Fuzzy Set Theory and Its Applications
Level Cut Conditioning Approach to the Necessity Measure Specification / M. Inuiguchi ; T. Tanino
Four c-regression Methods and Classification Functions / S. Miyamoto ; K. Umayahara ; T. Nemoto
Context-Free Fuzzy Sets in Data Mining Context / T. Y. Lin
Applying Fuzzy Hypothesis Testing to Medical Data / M. Last ; A. Schenker ; A. Kandel
Generating A Macroeconomic Fuzzy Forecasting System Using Evolutionary Search / R. Veliev ; A. Rubinov ; A. Stranieri
Fuzzy Control of Nonlinear Systems Using Nonlinearized Parameterization / H. Han ; H. Kawabata
Control of Chaotic Systems Using Fuzzy Model-Based Regulators / K. Watanabe ; L. Udawatta ; K. Kiguchi ; K. Izumi
Fuzzy Behavior-Based Control for the Obstacle Avoidance of Multi-Link Manipulators / P. Dassanayake
Fuzzy Future Value and Annual Cash Flow Analyses / N. Cetin ; C. Kahraman
Semi-Linear Equation with Fuzzy Parameters / S. Melliani
Non-Classical Logic and Approximate Reasoning
First Order Rough Logic-Revisited / Q. Liu
A Generalized Decision Logic in Interval-set-valued Information Tables
Many-Valued Dynamic Logic for Qualitative Decision Theory / C. J. Liau
Incorporating Fuzzy Set Theory and Matrix Logic in Multi-Layer Logic / H. Yamauchi
Fuzzy Logic as Interfacing Media for Constraint Propagation Based on Theories of Chu Space and Information Flow / K. Sato ; T. Horiuchi ; T. Hiraoka ; H. Kawakami ; O. Katai
Pattern Reasoning: A New Solution for Knowledge Acquisition Problem / H. Tsukimoto
Probabilistic Inference and Bayesian Theorem Based on Logical Implication / Y. Yamauchi ; M. Mukaidono
Reasoning with Neural Logic Networks / R. Yasdi
The Resolution for Rough Propositional Logic with Lower (L) and Upper (H) Approximate Operators
Information Granulation and Granular Computing
Information Granules in Distributed Environment / J. Stepaniuk
Evolving Granules for Classification for Discovering Difference in the Usage of Words / T. Yoshida ; T. Kondo ; S. Nishida
Interval Evaluation by AHP with Rough Sets Concept / K. Sugihara ; Y. Maeda ; H. Tanaka
Interval Density Functions in Conflict Analysis / K. Senoo
Incorporating Personal Databases by Granular Computing / Y. Kakemoto
Data Mining and Knowledge Discovery
Knowledge-Driven Discovery of Operational Definitions / J. M. Żytkow
A Closest Fit Approach to Missing Attribute Values in Preterm Birth Data / J. W. Grzymala-Busse ; W. J. Grzymala-Busse ; L. K. Goodwin
Visualizing Discovered Rule Sets with Visual Graphs Based on Compressed Entropy Density / E. Suzuki ; H. Ishihara
A Distance-Based Clustering and Selection of Association Rules on Numeric Attributes / X. Du ; S. Suzuki ; N. Ishii
Knowledge Discovery for Protein Tertiary Substructures / C. K. Chen ; D. Y. Y. Yun
Integrating Classification and Association Rule Mining: A Concept Lattice Framework / K. Hu ; Y. Lu ; L. Zhou ; C. Shi
Using Rough Genetic and Kohonen's Neural Network for Conceptual Cluster Discovery in Data Mining / H. Kiem ; D. Phuc
Towards Automated Optimal Equity Portfolios Discovery in A Knowledge Sharing Financial Data Warehouse / Y. C. Lu ; H. Cheng
Rule-Evolver: An Evolutionary Approach for Data Mining / C. Lopes ; M. Pacheco ; M. Vellasco ; E. Passos
Machine Learning
Decision Making with Probabilistic Decision Tables / W. Ziarko
The Iterated Version Space Learning / J. J. Zhang ; N. Cercone
An Empirical Study on Rule Quality Measures / A. An
Rules as Attributes in Classifier Construction / M. S. Szczuka
An Algorithm to Find the Optimized Network Structure in An Incremental Learning / J. C. Lee ; W. D. Lee ; M. S. Han
Patterns in Numerical Data: Practical Approximations to Kolmogorov Complexity
Performance Prediction for Classification Systems / F. Sun
Intelligent Agents and Systems
Flexible Optimization and Evolution of Underwater Autonomous Agents / E. Eberbach ; R. Brooks ; S. Phoha
Ontology-Based Multi-Agent Model of An Information Security System / V. I. Gorodetski ; L. J. Popyack ; I. V. Kotenko ; V. A. Skormin
Optimal Multi-Scale Time Series Decomposition for Financial Forecasting Using Wavelet Thresholding Techniques / T. Shin ; I. Han
Computerized Spelling Recognition of Words Expressed in the Sound Approach / M. Higgins
An Adaptive Handwriting Recognition System / G. Qian
Author Index
Invited Talks
Decision Rules, Bayes' Rule and Rough Sets / Z. Pawlak
A New Direction in System Analysis: From Computation with Measurements to Computation with Perceptions / L. A. Zadeh
The volume presents 28 revised full papers carefully selected for inclusion in the book from 42 submissions
The papers address a variety of graph-theoretic issues relevant from the computer science point of view such as graph algorithms, cycles, graph decompositions, interconnection networks, local search, graph orderings, graph matching, graph languages, tree-width computation, etc
The volume presents 28 revised full papers carefully selected for inclusion in the book from 42 submissions
The papers address a variety of graph-theoretic issues relevant from the computer science point of view such as graph algorithms, cycles, graph decompositions, interconnection networks, local search, graph orderings, graph matching, graph languages, tree-width computation, etc
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width / B. Courcelle ; J.A. Makowsky ; U. Rotics
Minus Domination in Small-Degree Graphs / Peter Damaschke
The Vertex-Disjoint Triangles Problem / V. Guruswami ; C.P. Rangan ; M.S. Chang ; G.J. Chang ; C.K. Wong
Communication in the Two-Way Listen-in Vertex-disjoint Paths Mode / Hans-Joachim Böckenhauer
Broadcasting on Anonymous Unoriented Tori / S. Dobrev ; P. Ru icka
Families of Graphs Having Broadcasting and Gossiping Properties / Guillaume Fertin ; André Raspaud
Optical All-to-All Communication in Inflated Networks / Olivier Togni
A Generalization of AT-free Graphs and a Generic Algorithm for Sol- ving Treewidth, Minimum Fill-In and Vertex Ranking / Hajo Broersma ; Ton Kloks ; Dieter Kratsch ; Haiko Müller
A Polynomial-Time Algorithm for Finding Total Colorings of Partial k-Trees / Shuji Isobe ; Xiao Zhou ; Takao Nishizeki
Rankings of Directed Graphs / Jan Kratochv'il ; Zsolt Tuza
Drawing Planar Partitions II: HH-Drawings / Therese Biedl ; Michael Kaufmann ; Petra Mutzel
Triangles in Euclidean Arrangements / Stefan Felsner ; Klaus Kriegel
Graphs with Bounded Induced Distance / Serafino Cicerone ; Gabriele Di Stefano
Diameter Determination on Restricted Graph Families / Derek G. Corneil ; Feodor F. Dragan ; Michel Habib ; Christophe Paul
Independent Tree Spanners / Dagmar Handke
Upgrading Bottleneck Constrained Forests / S. O. Krumke ; M. V. Marathe ; H. Noltemeier ; S. S. Ravi ; H.-C. Wirth
Routing in Recursive Circulant Graphs: Edge Forwarding Index and Hamiltonian Decomposition / G. Gauyacq ; C. Micheneau ; A. Raspaud
Improved Compressions of Cube-Connected Cycles Networks / Ralf Klasing
Efficient Embeddings of Grids into Grids / Markus Röttger ; Ulf-Peter Schroeder
Integral Uniform Flows in Symmetric Networks / Farhad Shahrokhi ; László A. Székely
Splitting Number is NP-complete / L. Faria ; C. M. H. de Figueiredo ; C. F. X. Mendonça
Tree Spanners in Planar Graphs / Sandor P. Fekete ; Jana Kremer
A Linear-Time Algorithm to Find Four Independent Spanning Trees in Four-Connected Planar Graphs / Kazuyuki Miura ; Daishiro Takahashi ; Shin-ichi Nakano
Linear Algorithms for a k-partition Problem of Planar Graphs without Specifying Bases / Koichi Wada ; Wei Chen
Domination and Steiner Tree Problems on Graphs with Few P4s / Luitpold Babel ; Stephan Olariu
Minimum Fill-in and Treewidth for Graphs Modularly Decomposable into Chordal Graphs / Elias Dahlhaus
Interval Completion with the Smallest Max-degree / Fedor V. Fomin ; Petr A. Golovach
An Estimate of the Tree-Width of a Planar Graph Which Has Not a Given Planar Grid as a Minor / K.Yu. Gorbunov
Author Index
Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width / B. Courcelle ; J.A. Makowsky ; U. Rotics
Minus Domination in Small-Degree Graphs / Peter Damaschke
The Vertex-Disjoint Triangles Problem / V. Guruswami ; C.P. Rangan ; M.S. Chang ; G.J. Chang ; C.K. Wong
Abstracting a Human's Decision Process by PRISM / Yoshitaka Kameya ; Taisuke Sato
Mechanisms of Self-Organized Renormalizability / Hiroshi H. Hasegawa ; Yoshikazu Ohtaki
An Efficient Tool for Discovering Simple Combinatorial Patterns from Large Text Databases / Hiroki Arimura ; Atsushi Wataki ; Ryoichi Fujino ; Shinichi Shimozono
A Similarity Finding System under a Goal Concept / Makoto Haraguchi ; Tokuyasu Kakuta
Parallel Induction Algorithms for Large Samples / Tohgoroh Matsui ; Nobuhiro Inuzuka ; Hirohisa Seki ; Hidenori Itoh
Toward Effective Knowledge Acquisition with First Order Logic Induction / Xiaolong Zhang ; Tetsuo Narita ; Masayuki Numao
A Logic of Discovery / Jānis Bārzdiņ&sbreve; ; Rūsiņš Freivalds ; Carl H. Smith
A Strong Relevant Logic Model of Epistemic Processes in Scientific Discovery / Jingde Cheng
Four-Fold Table Calculi for Discovery Science / Jan Ranch
Parallel Organization Algorithm for Graph Matching and Subgraph Isomorphism Detection / Yoshinori Nakanishi
Visualizing Semantic Clusters in the Internet Information Space / Etsuya Shibayama ; Jun Yabe ; Shin Takahashi ; Mitsuru Matsuda
KN on ZK - Knowledge Network on Network Note Pad ZK / Sachio Hirokawa ; Tsuyoshi Taguchi
Virtual Integration of Distributed Database by Multiple Agents / Takao Mohri ; Yuji Takada
Development of Some Methods and Tools for Discovering ConceptualKnowledge / Tu Bao Ho ; Trong Dung Nguyen ; Ngoc Binh Nguyen ; Takuya Ito
Reducing the Dimensions of Attributes by Selection and Aggregation / Akiko Aizawa
On the Number of Clusters in Cluster Analysis / Atsuhiro Takasu
Geometric Clustering Models in Feature Space / Mary Inaba ; Hiroshi Imai
Efficient Mining of Association Rules with Item Constraints / Shin-Mu Tseng
GDT-RS: A Probabilistic Rough Induction Approach / Juzhen Dong ; Ning Zhong ; Setsuo Ohsuga
A Constructive Fuzzy NGE Learning System / Maria do Carmo Nicoletti ; Flavia Oliveira Santos
Composing Inductive Applications Using Ontologies for Machine Learning / Akihiro Suyama ; Naoya Negishi ; Takahira Yamagchi
TDDA, a Data Mining Tool for Text Databases: A Case History in a Lung Cancer Text Database / Jeffrey A. Goldman ; Wesley Chu ; D. Stott Parker ; Robert M. Goldman
Crowww Classification and Retrieval on WWW / Phyllis Anwyl ; Atsushi Itoh ; Ayako Oono
Extracting Knowledge Patterns from Ticket Data / Maria de Fatima Rodrigues ; Carlos Ramos ; Pedro Rangel Henriques
Automatic Acquisition of Phoneme Models and Its Application to Phoneme Labeling of a Large Size of Speech Corpus / Motoyuki Suzuki ; Teruhiko Maeda ; Hiroki Mori ; Shozo Makino
An Experimental Agricultural Data Mining System / Kazunori Matsumoto
Data Mining Oriented System for Business Applications / Yukinobu Hamuro ; Naoki Katoh ; Katsutoshi Yada
Moving Object Recognition Using Wavelets and Learning of Eigenspaces / Shigeru Takano ; Teruya Minamoto
Search for New Methods for Assignment of Complex Molecular Spectra and a Program Package for Simulation of Molecular Spectra / Takehiko Tanaka ; Takashi Imajo
Computer Aided Hypotheses Based Drug Discovery Using CATALYSTRTM and PC GUHA Software Systems (A Case Study of Catechol Analogs Against Malignant Melanoma) / Jaroslava Halova ; Oldrich Strouf ; Premysl Zak ; Anna Sochorova ; Noritaka Uchida ; Hiroshi Okimoto ; Tomoaki Yuzuri ; Kazuhisa Sakakibara ; Minora Hirota
Knowledge Discovery through the Navigation Inside the Human Body / Toyofumi Saito ; Jun-ichiro Toriwaki ; Kensaku Mori
図書
