Sixth Workshop on Learning with Logics
and Logics for Learning


July 6(Mon)-7(Tue), 2009
Kyodai Kaikan, Kyoto, Japan


July 6th (Mon)
13:00 Opening
13:10-15:10 Session 1

Takashi Yamada, Hitoshi Yamasaki, Takayoshi Shoudai
A Polynomial Time Algorithm for Finding a Minimally Generalized Externally Extensible Outerplanar Graph Pattern

Taku Aratsu, Kouichi Hirata, Tetsuji Kuboyama
Local Frequency Distances for Rooted Ordered Trees

Yuichi Kameda and Hiroo Tokunaga
Inferability of Unbounded Unions of Certain Closed Set Systems

Mahito Sugiyama, Eiju Hirowatari, Hideki Tsuiki, Akihiro Yamamoto
Learning Figures with the Hausdorff Metric by Self-similar Sets
15:30-16:30 Invited Talk 1

Thomas Zeugmann
The Normalized Information Distance and its Applications Using Graph Cuts
16:50-18:20 Session 2

Fumiya Nakagaito, Tomonobu Ozaki, Takenao Ohkawa
Discovery of Quantitative Sequential Patterns from Event Sequences

Takashi Katoh, Hiroki Arimura, Koichi Hirata
Mining Frequent $k$-Partite Episodes from Event Sequences

Haruya Iwasaki, Elsa Loekito, Shin-ichi Minato, James Bailey
Comparison of ZDD-Vectors and WZDDs for Frequent Pattern Mining

July 7th (Tue)

10:00-11:00 Session 3

Kimihito Ito, Thomas Zeugmann and Yu Zhu
Clustering the Normalized Compression Distance for Virus Data

Joe Suzuki
A Conjecture on Strongly Consistent Learning
11:20-12:20 Invited Talk 2

Marta Arias
A Canonical Representation for Propositional Horn Theories and its Relation to Query Learning
13:20-14:50 Session 4

Ken Satoh
Computing Minimal Models by Minimal DNF formula

Yoshitaka Yamamoto, Katsumi Inoue, Koji Iwanuma
Hypothesis Enumeration by CF-induction

Seishi Ouchi and Akihiro Yamamoto
Learning from Positive Data based on the MINL Strategy with Refinement Operators
14:50-15:00 Closing
18:00- Joint Banquet with DMSS

Scope of the Workshop

Logic is one of the mathematical methods of representing data as well as rules in Machine Learning and Knowledge Discovery. Recently some methods are developed based on algebraic concepts, e.g. closed sets, for the aim. In the converse, Machine Learning procedures are found to provide procedural semantics to algebraic, and logical inference.

The aim of LLLL is to bring together researchers who are interested in both of the areas of machine learning and computational logic, and to have intensive discussions on various relations between the two with making their interchange more active. The LLLL workshop was started as a domestic workshop in 2002. As an international workshop, we held LLLL at Kitakyushu in 2005, at Tokyo in 2006, and at Miyazaki in 2007. LLLL2009 is supported by SIG-FPAI. LLLL2009 is collocated with DMSS2009, which is held July 7-8 at the same site. The CFP of DMSS2009 is available at

Potential (but not exclusive) topics include :

  • Learning and knowledge discovery using logics
  • Learning and knowledge discovery using algebraic methods
  • Algorithmic aspects of learning based on logics
  • Logics for machine learning and knowledge discovery
  • Logics using machine learning
  • Machine learning as a foundation of mathematics/mathematical procedures
  • Amalgamation of logic-based learning and statistical/information theoretical learning
  • Learning and knowledge discovery from relational data
  • Learning and knowledge discovery from structured/semi-structured data

Registration fee: Free, but joining Banquet costs 6,000 JPY.

Inivited Speakers

Marta Arias Vicente (Universitat Politècnica de Catalunya, Spain)

A Canonical Representation for Propositional Horn Theories and its Relation to Query Learning

Abstract: In this talk I will describe a canonical representation for propositional Horn theories known as the Guigues-Duquenne basis (or GD basis), that was introduced in the field of Formal Concept Analysis. I will show strong connections between this representation and two topics in query learning theory. First, I will show that a well-known algorithm by Angluin, Frazier and Pitt that learns Horn CNF always outputs the GD basis independently of the counterexamples it receives; second, and if time permits, I will show how to construct strong polynomial certificates from the GD basis directly. This is joint work with JosEL. Balcázar.

Thomas Zeugmann (Hokkaido University)

The Normalized Information Distance and its Applications Using Graph Cuts

Abstract: First we recall some background necessary to understand the definition of the Normalized Information Distance. Then we outline as possibleapproximations the Normalized Compression Distance and the Google Distance. Next, we turn our attention to clustering. Clustering algorithms working with a matrix of pairwise similarities (kernel matrix) for the data are widely known and used, a particularly popular class being spectral clustering algorithms. In contrast, working directly with the pairwise distance matrix has found less attention despite the fact that in many applications distance matrices are often directly given. So, we look at clustering algorithms based on Semidefinite Programming (SDP) based on the work of Frieze and Jerrum and on spectral clustering working over similarity matrices. Finally, we shortly propose a simple heuristic for dealing with missing data, i.e., the case where some of the pairwise distances or similarities are not known.

Workshop Banquet

Workshop Banquet is held with DMSS at 18:00 on July 7th. Attendees who would like to join the banquet must send an email with the followings in the body:
- your name,
- affiliation, and
- email
Banquet fee is 6,000 JPY (JPY cash only).

How to Submit

LLLL2009 accepts extended abstracts written in English only. The abstracts are distributed in the workshop sites only and not considered to be formal publications. The extended abstract should be 1-8 pages in the format at the address:

The authors should send their submitted papers as a PDF file to,, and (all).

Please write the text `[LLLL09: Paper Submission]' in the subject of the massage, and put the following in the body:
- Title of your paper,
- A list of all authors and their affiliations (please add "*" mark to the presenter),
- Name, Telephone number, and E-mail address of the corresponding author.

Important dates
June 8, 2009
June 11, 2009
Paper submission deadline (extended)
June 19, 2009
June 22, 2009
Notification of acceptance/rejection (extended)
July 6-7, 2009 Workshop

Meeting Venue


Tel: +81-75-751-8311
Fax: +81-75-761-5403



- From Kyoto JR Station, take the bus 206 at terminal D2, stop at the bus stop Kyodai-seimon-mae and walk about 5 mins.
- By Keihan train, get off at Keihan Marutamachi Station and walk about 7 mins.

Committee Members

Workshop Chair

Akihiro Yamamoto (Kyoto University)

PC Co-chairs

Kouichi Hirata (Kyushu Institute ofTechnology)
Shin-ichi Minato (Hokkaido University)

Program Commitee (current status)

Yoji Akama (Tohoku University)
Marta Arias (Universitat Politecnica de Catalunya)
Kouichi Hirata (Kyushu Institute ofTechnology)
Tamas Horvath (University of Bonn and Fraunhofer IAIS)
Katsumi Inoue (National Institute of Infomatics)
Shin-ichi Minato (Hokkaido University)
Tetsuhiro Miyahara (Hiroshima City University)
Taisuke Sato (Tokyo Institute ofTechnology)
Takayoshi Shoudai (Kyushu University)
Hiroo Tokunaga (Tokyo Metropolitan University)
Gyorgy Turan (University of Illinois)
Akihiro Yamamoto (Kyoto University)

Website and Contact

Postal addess : Akihiro Yamamoto

Graduate School of Informatics, Kyoto University
Yoshida-Honmachi, Sakyo-ku, Kyoto
606-8501 JAPAN
Email : about LLLL2009
Tel: +81 75 753 5995
Fax: +81 75 753 5628