The 4th JFLI-LRI-NII Workshop on Consequence Finding and Satisfiability Testing in Distributed Environments and Systems Biology
(co-sponsored by NII Collaborative Research)


  • Dates:
19th - 20th, November 2012
  • Venue:
University Paris-Sud
Meeting room in Laboratoire de Recherche en Informatique (LRI)
  • Address:
Bat 650 Universite Paris-Sud 11,
91405 Orsay Cedex, France


Vincent Armant University Paris-Sud (Orsay, France)
Mutsunori Banbara Kobe University (Kobe, Japan)
Gauvain Bourgne University Pierre and Marie Curie (Paris, France)
Hei Chan Transdisciplinary Research Integration Center (Tokyo, Japan)
Philippe Chatalic University Paris-Sud (Orsay, France)
Sarah Cohen Boulakia University Paris-Sud (Orsay, France)
Philippe Dague University Paris-Sud (Orsay, France)
Christine Froidevaux University Paris-Sud (Orsay, France)
François Goasdoué University Paris-Sud (Orsay, France)
Daisuke Hatano Kobe University (Kobe, Japan)
Katsutoshi Hirayama Kobe University (Kobe, Japan)
Hiroshi Hosobe National Institute of Informatics (Tokyo, Japan)
Katsumi Inoue National Institute of Informatics (Tokyo, Japan)
Nicolas Maudet University Pierre and Marie Curie (Paris, France)
Hidetomo Nabeshima University of Yamanashi (Kofu, Japan)
Tenda Okimoto Transdisciplinary Research Integration Center (Tokyo, Japan)
Sabine Peres University Paris-Sud (Orsay, France)
Anne Poupon INRA, CNRS (Tours, France)
Tony Ribeiro National Institute of Informatics (Tokyo, Japan)
Adrien Rougny University Paris-Sud (Orsay, France)
Nicolas Schwind National Institute of Informatics (Tokyo, Japan)
Laurent Simon University Paris-Sud (Orsay, France)
Takehide Soh Kobe University (Kobe, Japan)
Naoyuki Tamura Kobe University (Kobe, Japan)
Yoshitaka Yamamoto University of Yamanashi (Kofu, Japan)


Monday, November 19th

9:30-9:45 Opening
9:45-10:00 On NII Collaborative Research Project: "Consequence Finding and SAT/MaxSAT Solving in a Distributed Environment"
Katsutoshi Hirayama.


10:00-10:30 Distributed Diagnostics
Vincent Armant.


10:30-11:00 A Best-First Search Strategy for SOL Tableau Calculus
Hidetomo Nabeshima.


11:00-11:15 Coffee Break
11:15-11:45 Generalized Production Fields in SOLAR
Gauvain Bourgne.


11:45-13:00 Discussions
13:00-14:00 Lunch
14:00-14:30 Knowledge-Based Reasoning to Design Signaling Networks
Adrien Rougny.


14:30-15:00 Logical Verification of Biological Networks with Gene Expression Data
Yoshitaka Yamamoto*, Haruka Sakamoto and Koji Iwanuma .

Along with high-throughput experimental tools like microarrays, it is recently required to verify the consistency between a large amount of data and biological networks. In this talk, we propose a qualitative way for verifying the consistency of those networks with gene expression data in the context of multi-valued logic.

15:00-15:30 Modular Reasoning in ASP
Tony Ribeiro*, Katsumi Inoue, Gauvain Bourgne.

We are concerned with multi-agent systems (MAS) in dynamic environment, and focus on knowledge representation and context-aware reasoning of such systems. In dynamic environment, an agent needs to be able to manage its knowledge according to context changes. To achieve this goal, an agent has to adapt his beliefs and behaviour with respect to the current state of the world. In this work, we define a method to design agents' knowledge and reason efficiently in dynamic contexts. For this purpose, we use the expressiveness of answer set programming (ASP) and propose a method based on combinations of modules that are represented in ASP. Using meta-knowledge on these combinations, we can easily realise dynamic behaviour and meta-reasoning. We propose an algorithm to combine modules and implement the framework in an example of multi-agent systems in a dynamic world. Using experimental results, we show that modular knowledge can be used to optimise reasoning time.

15:30-15:45 Coffee Break
15:45-18:00 Discussions
19:00 Dinner

Tuesday, November 20th

9:30-9:45 Opening
9:45-10:15 CSPSAT and CSPSAT2 Projects
Naoyuki Tamura* and Katsumi Inoue.

This talk introduces a brief overview of CSPSAT and CSPSAT2 projects. CSPSAT project was finished on March 2011, and during the project the following softwares were developed: Sugar (winner of 2008 and 2009 CSP solver competitions), GlueMiniSat (winner of 2011 SAT competition), QMaxSAT (winner of 2011 and 2012 Max-SAT evaluations). CSPSAT2 is an ongoing project started from April 2012 for three years. Its research objective is a R&D of enhanced SAT technologies as a high-performance inference engine for intractable and hard problems. Its research topics include extensions for flexible constraints, extensions for dynamic constraints, and extensions of constraint domains.

10:15-10:45 Recent Progresses in Glucose 2.1
Laurent Simon.


10:45-11:00 Coffee Break
11:00-11:30 Toward Cooperative Rolling Stock Operation by Distributed SAT
Katsutoshi Hirayama.

The rolling stock operation involves assigning rolling stocks (railway vehicles) to a given timetable of railway operations. Since some railway companies in Japan often share their operations that use the same railway tracks, it is necessary for the companies to coordinate their actions while not revealing the whole information. Our goal is to explore the possibility of cooperative rolling stock operation by distributed constraint reasoning techniques. In this talk, we present both centralized and distributed SAT formulations of rolling stock operation and report our preliminary experimental results.

11:30-12:45 Discussions
12:45-14:00 Lunch
14:00-14:15 On Systems Resilience
Katsumi Inoue*, Hiroshi Maruyama.


14:15-14:45 Systems Resilience: A Challenge Problem for Dynamic Constraint-Based Agent Systems
Hei Chan, Katsumi Inoue, Hiroshi Maruyama, Kazuhiro Minami, Tenda Okimoto, Tony Ribeiro, Nicolas Schwind*, Tomoya Tanjo.

Resilience can be informally defined as "the capacity of a system to maintain its core purpose in the face of dramatically changed circumstances". It is a new concept of transdisciplinary science, and can be seen in many natural and artificial systems. To take a systems approach to resilience, we explore the basic theory of resilience from the computational viewpoint, in particular first by defining a model called SR-model where we can measure important properties of resilience such as resistance and recoverability.

14:45-15:00 Coffee Break
15:00-15:30 Metabolic Networks Analysis with Elementary Flux Modes
Sabine Peres


15:30-16:00 Extended Evaluation of the Prediction of Gene Knockout Effects by Minimal Pathway Enumeration
Takehide Soh*, Katsumi Inoue, Tomoya Baba, Toyoyuki Takada, and Toshihiko Shiroishi.

In this talk, we explain a method to predict gene knockout effects for the cell growth by utilizing biological databases such as KEGG and EcoCyc, in which biological knowledge and experimental results have been collected. We construct biological networks from such databases and configure experimental conditions by giving source metabolites, target metabolites, and knockout genes. We then enumerate all minimal active pathways, which are minimal subsets of a given network using source metabolites to produce target metabolites. We simulate the effects of gene knockouts by measuring the difference of minimal active pathways between original networks and knockout ones.

In the experiments, we applied it to predict the single gene knockout effects on the glycolysis pathway and amino acids biosynthesis in Escherichia coli. We also analyze which pathways are important to Escherichia col and predict lethal pairs of knockout genes. In the results, our method predicted three out of four essential genes, which agree with the biological results of the Keio collection containing comprehensive cell growth data. In addition, predicted lethal pairs of genes also agree with the biological results of double gene knockouts.

16:00-17:30 Workshops

Other Remarks

  • Presentation slides will be available online after the workshop.
  • For any question, please send an email to Gauvain Bourgne.