List of Papers Presented at EATCS/LA Workshop on TCS 2003

This is a list of papers presented at the 1st EATCS/LA Workshop on Theoretical Computer Science, held at Univ. Kyoto on February 3 - 5, 2003.

Go back to the workshop homepage
Created by O. Watanabe, 3/30/03.

IMPORTANT NOTICE:
This workshop is a norefereed meeting; that is, all proposed talks are accepted for the presentation. Although some of the papers for the presented talks are published in a RIMS proceedings, these are essentially equivalent to ordinary technical reports. Thus, there should be no problem of presenting these papers in refereed conferences and/or journals.

Less Important Notice:

Created by O. Watanabe, 3/30/03.

k = key words, a = author(s), and e = e-mail address.

ALGORITHMS: ON GRAPHS

  1. A Study of the Minimal Covering Tree Problem for the Unordered and Contractible Binary Tree
    a: K. Makiyama, H. Yasuura
    e: makiyama@c.csce.kyushu-u.ac.jp

  2. A Linear-Time Algorithm for 7-Coloring 1-Planar Graphs
    a: Z.Z. Chen, M. Kouno
    e: chen@r.dendai.ac.jp

  3. An Experimental Evaluation of Volume Respecting Embedding Approach for the Bandwidth Problem
    a: Y. Komahara, Y. Nakano, K. Yamazaki
    k: the bandwidth problem, approximation algorithm, volume respecting embedding
    e: koichi@cs.gunma-u.ac.jp

ALGORITHMS: ON SOME OTHER OBJECTS

  1. Robot Scheduling for Ball Collecting Problem
    a: T. Sakuma, H. Ono, M. Yamashita, Y. Asahiro, K. Makino, T. Horiyama
    k: moving-target TSP, combinatorial optimization, ball collecting problem
    e: sakuma@tcslab.csce.kyushu-u.ac.jp

  2. Capacitated Routing and Delivery Problems for Moving-Targets
    a: S. Shimoirisa, Y. Asahiro, E. Miyano
    k: capacity, moving-targets, routing and delivery
    e: miyano@ces.kyutech.ac.jp

  3. Recent Advancement of a Genetic Algorithm to Solve the Set Covering Problem
    a: K. Iwamura, N. Okada, Y. Deguchi
    k: genetic algorithm, set covering problem, computational study
    e: kiwamura@math.josai.ac.jp

  4. A General Scheme for Reducing Delay of Enumeration Algorithms
    a: T. Uno
    k: discrete algorithm, enumeration, delay
    e: uno@nii.jp

  5. An $O(1)$ Time Algorithm for Generating Integer Compositions
    a: K. Mikawa, I. Semba
    e: mikawa@mx.ibaraki.ac.jp
  6. Convex Case Capital Investment
    a: T. Tsukiji, Y. Yokoyama
    k: capital investment, convex case, competitive ratio
    e: tsukiji@info.human.nagoya-u.ac.jp

  7. Algorithms for Table Editing
    a: T. Motohashi, S. Tani, K. Tsuchida, T. Yaku
    k: data structures, table interface, graphs
    e: yaku@cs.chs.nihon-u.ac.jp

  8. Test Instance Generation for MAX 2SAT with Fixed Optimal Value
    a: M. Motoki
    k: combinatorial optimization, randomized algorithm
    e: mmotoki@jaist.ac.jp

  9. An Improved Analysis of Goemans-Williamson's LP-Relaxation for MAX SAT
    a: T. Asano
    k: MAX-SAT, approximation algorithm
    e: asano@ise.chuo-u.ac.jp

  10. Improved Algorithms for 2-Interval Scheduling and NMR Spectral Peak Assignment
    a: Z.Z. Chen, T. Jiang, G. Lin, J. Wen
    k: approximation algorithms, computational biology
    e: chen@r.dendai.ac.jp

  11. Approximating Minimum Vertex Cover for Graphs with Perfect Matching: Improvement for High Degree Graphs
    a: M. Takeuchi, T. Tsukiji
    k: vertex cover, perfect matching, degree
    e: tsukiji@info.human.nagoya-u.ac.jp

  12. A New Approximation Algorithm for Task Scheduling
    a: K. Katayanagi, A. Sunasaka, M. Oyamaguchi, Y. Ohta
    k: task scheduling, approximation algorithm, communication delay
    e: ohta@cs.info.mie-u.ac.jp

  13. A New Polynomial-Time Solvable Class of Satisfiability
    a: T. Asano, M. Motoki, K. Nakano
    k: SAT, constraint satisfaction
    e: mmotoki@jaist.ac.jp

  14. Approximte Counting Scheme for mxn Contingency Tables
    a: S. Kijima, T. Matsui
    k: approximate counting, contingency table
    e: kijima@misojiro.t.u-tokyo.ac.jp

COMBINATORICS & DISCRETE MATHEMATICS

  1. Centralizers and Monoids in Mathematical Clone Theory
    a: M. Hajime, I.G. Rosenberg
    k: clone, Galois connection
    e: machida@math.hit-u.ac.jp

  2. Logical Analysis of Data by Threshold Functions
    a: H. Kataoka, H. Ono, M. Yamashita
    k: logical analysis of data, threshold function, Boolean function
    e: hiroyuki@tcslab.csce.kyushu-u.ac.jp

  3. Kolmogorov Complexity Upper Bound of Probability in Computable POVM Measurement
    a: K. Tadaki
    k: Kolmogorov complexity, POVM, universal probability, computability
    e: tadaki@qci.jst.go.jp

  4. On Mathematical Properties of Join-Irreducibles in MPR-Lattices
    a: K. Miyakawa, H. Narushima
    k: evolutionary tree, maximum parsimony, lattice-theoretic properties
    e: miyakawa@cssa.chs.nihon-u.ac.jp

COMPUTATIONAL COMPLEXITY

  1. PSPACE Completeness of Generalized Sliding Block Puzzle, Another Proof
    a: T. Kitagawa, S. Iwata
    k: sliding block puzzle, PSPACE complete, another proof
    e: graywind@np.cs.uec.ac.jp

  2. On Computational Complexity of the Unknotting Problem of Knots
    a: M. Hara, S. Tani, M. Yamamoto
    k: computational topology, intractable proof system
    e: sei-ichi@tani.cs.chs.nihon-u.ac.jp

COMPUTATIONAL LEARNING

  1. Polynomial Time Inductive Inference of Ordered Term Trees with Contractible Variables from Positive Data
    a: Y. Suzuki, T. Shoudai, T. Miyahara, T. Uchida, S. Hirokawa
    k: machine learning, polynomial time inductive inference, data mining
    e: y-suzuki@i.kyushu-u.ac.jp

  2. Strategic Mining via Indirect Association Rules
    a: S. Hamano, M. Sato
    k: data mining, basket analysis
    e: shincan0112@wizard.osakafu-u.ac.jp

  3. Online Algorithms for Discovering Frequent Substructures from Semi-Structured Data Streams
    a: T. Asai, K. Abe, S. Kawasoe, H. Arimura, S. Arikawa
    k: data mining, semi-structured data
    e: t-asai@i.kyushu-u.ac.jp

  4. Containment Problem for Intersections of Regular Pattern Languages
    a: M. Terada, M. Sato
    k: containment problem, regular pattern languages
    e: miterada@kcn.ne.jp

  5. Learning of Regular Elementary Formal Systems with Two Clauses from Positive Examples
    a: J. Uemura, M. Doshoda, M. Sato
    k: inductive inference, elementary formal system, positive example
    e: moontan_222@ybb.ne.jp

  6. Learning of Term Tree Languages
    a: S. Matsumoto, Y. Suzuki, T. Shoudai, T. Uchida, T. Miyahara
    k: computational learning theory
    e: matumoto@ss.u-tokai.ac.jp

CRYPTOGRAPHY

  1. Knapsack Cryptosystems with a Different Enumerative Source Encoding
    a: K. Oomura, K. Tanaka
    e: oomura8@is.titech.ac.jp

  2. On Short Exponent DDH
    a: T. Koshiba, K. Kurosawa
    k: cryptography, DDH problem, discrete logarithm
    e: koshiba@jp.fujitsu.com

DISTRIBUTED COMPUTING

  1. The Reserch of Distributed Cooperation in Robocup Soccer Simulation
    a: T. Ogata, H. Ono, M. Yamashita
    k: multi agent system, Robocup, distributed cooperation
    e: tsukasa@tcslab.csce.kyushu-u.ac.jp

DNA COMPUTING and QUANTUM COMPUTING

  1. Quantum Walks on Cycles with Even Nodes
    a: T. Sato, A. Maruoka
    k: quantum walk, cycle, upper bound
    e: taka@info.sendai-ct.ac.jp

  2. Quantum Bit-Commitment with Small Strage from Quantum One-Way Permutations
    a: K. Tanaka
    k: quantum protocols, cryptographic protocols
    e: keisuke@is.titech.ac.jp

  3. Noise-Tolerant Quantum Oracles
    a: R.H. Putra, S. Yamashita, K. Iwama
    k: quantum computation, EQ oracle, IP oracle, noise
    e: raymond@kuis.kyoto-u.ac.jp

  4. Algorithms for Finding a Maximum Clique with Maximum Vertex Weight
    a: T. Nakamura, E. Tomita, T. Nishino, Y. Nakui
    k: maximum clique, vertex weight, quantum circuit
    e: tomonori@ice.uec.ac.jp

  5. On the Minimization of the Quantum Circuit Depth Based on a Maximum Clique with Maximum Vertex Weight
    a: Y. Nakui, T. Nishino, E. Tomita, T. Nkamura
    k: quantum circuit, circuit depth, minimization problem of ESOP, maximum clique, NP-complete problem
    e: nakui@ice.uec.ac.jp

  6. An Algorithm for Subgraph Isomorphism Problem on an DNA Computing Model
    a: T. Katayama, R. Ukai, K. Goshonoo, N. Itoh, N. Inuzuka, K. Wada
    k: DNA computing, subgraph isomorphism problem, remove operation
    e: dna@phaser.elcom.nitech.ac.jp

FORMAL LANGUAGE AND AUTOMATA THEORY

  1. Shrinking Alternating Two-Pushdown Automata
    a: E. Moriya, F. Otto
    k: formal language, automaton, alternating automaton
    e: moriya@waseda.jp

  2. Information Dynamics of Cellular Automata: CA Computation and Information Theory
    a: H. Nishio, T. Saito
    k: cellular automaton, polynomial, finite field, entropy, Kolmogorov complexity, information dynamics
    e: YRA05762@nifty.com

PARALLEL ALGORITHMS

  1. Robust Parallelizations of Metaheuristics
    a: M. Isibashi, Y. Asahiro, M. Yamashita
    k: combinatorial optimization problem, metaheuristics, parallelization
    e: isibashi@tcslab.csce.kyushu-u.ac.jp

  2. A Simple Group Mutual Exclusion Algorithm on the Asynchronous Shared Memory Model
    a: M. Takamura, Y. Igarashi
    k: distributed algorithms
    e: takamura@comp.cs.gunma-u.ac.jp

SEMANTICS & TERM REWRITING SYSTEMS

  1. Model Checking for Parallel Processes with a Coordination Language
    a: H. Ohtsuka
    k: model checking, parallel, coordination
    e: ohtsuka@math.sci.ehime-u.ac.jp

  2. Typing Exceptions in an Object Oriented Calculus with Recursive Types
    a: M. Horie, M. Sakai, T. Sakabe
    k: object calculus, object oriented language, exception handling, type system
    e: mihoko@sakabe.nuie.nagoya-u.ac.jp

  3. Development of an Interactive Theorem Prover for Sequent Calculi Based on Analogy
    a: K. Yamada, K. Hirata, M. Harao
    k: analogy, schema guided, higher order matching, interractive proving, teaching assistance
    e: yamada@ai.kyutech.ac.jp

  4. Narrowing-based Effective Rewriting and its Termination for Term Rewriting Systems with Extra Variables
    a: N. Nishida, M. Sakai, T. Sakabe
    k: TRS, computation model, narrowing, termination
    e: nishida@sakabe.nuie.nagoya-u.ac.jp