EATCS/LA Workshop on TCS, Jan.30 - Feb.1, 2005, Program

Go back to the workshop homepage
Created by O. Watanabe, 1/6/05.

IMPORTANT NOTICE:
EATCS/LA workshop is an unrefereed meeting; that is, all submissions are accepted for the presentation. Thus, there should be no problem of presenting these papers in refereed conferences and/or journals.

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

Jan. 30th (Mon)

1. Improved deterministic approximation algorithms for Max TSP
   a: Z. Chen, Y. Okamoto, and L. Wang
   c: Dept. of Mathematical Sciences, Tokyo Denki University
   k: approximation algorithms, MaxTSP, metric MaxTSP
   e: 03smr05@ed.ccs.dendai.ac.jp
2. An improved randomized approximation algorithm for Max TSP
   a: Z. Chen and L. Wang
   c: Dept. of Mathematical Sciences, Tokyo Denki University
   k: traveling salesman problem, approximation algorithms
   e: chen@rnc.r.dendai.ac.jp
3. A construction of non-3-colorable planar graphs
   a: Y. Hanatani, T. Horiyama, and K. Iwama
   c: Guraduate School of Informatics, Kyoto University
   k: 3-colorability, planar graph
   e: hanatani@kuis.kyoto-u.ac.jp
4. A hierarchy of tree edit distance measures
   a: T. Kuboyama, K. Shin, and T. Miyahara
   c: Center for Collaborative Research, University of Tokyo
   k: alignment of trees, tree edit distance
   e: ori-la@ccr.u-tokyo.ac.jp
5. Algorithm to evaluate similarities of parse trees
   a: H. Shiina and K. Akitomo
   c: Okayama University of Science
   k: parsing, matching, parse tree
   e: shiina@mis.ous.ac.jp
6. A subclass of context-free tree languages recognaizable in $O(n^3)$
   a: I. Kawaharada and A. Fujiyoshi
   c: Graduate School of Electro-Communications, Univ. of Electro-Communications
   k: context-free tree grammars, CKY algorithm, tree adjoining grammars
   e: ikuo@calvyn.cs.uec.ac.jp
7. Recursion removal from non-linear top recursive programs using array
   a: Y. Takasu, M. Sakai, N. Nishida, K. Kusakari, and T. Sakabe
   c: Graduate School of Eng., Nagoya University
   k: program transformation
   e: takasu@sakabe.i.is.nagoya-u.ac.jp
8. Learning unions and intersections of erasing regular pattern languages
   a: J. Uemura
   c: Osaka Prefecture Univ., College of Integrated Arts and Sciences, Mathematics and Information Sciences
   k: inductive inference from posotove data, formal languages
   e: jin@mi.cias.osakafu-u.ac.jp
9. Notes on online learning of ranking functions
   a: A. Nakamura
   c: Graduate School of Information Science and Technology, Hokkaido Univ.
   k: computational learning theory
   e: atsu@main.ist.hokudai.ac.jp
10. A model and methods for moderately-hard functions
    a: T. Onodera and K. Tanaka
    c: Dept. of Mathematical and Computing Sciences, Tokyo Inst. of Tech.
    k: one-Way function, computational complexity, discrete-log problem, factoring problem
    e: onodera0@is.titech.ac.jp
11. The sampling twice technique for the RSA-based cryptosystems with anonymity
    a: R. Hayashi and K. Tanaka
    c: Dept. of Mathematical and Computing Sciences, Tokyo Inst. of Tech.
    k: theory of cryptography, public-Key cryptosystems
    e: hayashi9@is.titech.ac.jp
12. On NK-community problem
    a: M. Yamamoto and T. Shigezumi
    c: Dept. of Mathematical and Computing Sciences, Tokyo Inst. of Tech.
    k: computational complexity, NP-completeness
    e: Takeya.Shigezumi@is.titech.ac.jp

    Jan. 31st (Tue)

13. On a mobile agent allocation problem
    a: A. Sasaki, K. Miyata, T. Araragi, and S. Masuyama
    c: Toyohashi University of Technology
    k: mobile agent, strongly NP-complete, approximation algorithm,
    e: masuyama@tutkie.tut.ac.jp
14. A new searching algorithm for evolving network
    a: T. Ogata, K. Sadakane, and M. Yamashita
    c: Graduate School of Information Sci. and Electrical Eng., Kyushu Univ.
    k: random walkCsmall worldCscale free
    e: tsukasa@tcslab.csce.kyushu-u.ac.jp
15. Problems on ID set generation in consideration of the uniqueness of portion ID
    c: K. Makiyama, S. Noutomi, and H. Yasuura
    a: Dept. of Computer Sci. and Communication Eng., Kyushu Univ.
    e: makiyama@c.csce.kyushu-u.ac.jp
16. Energy complexity for threshold circuits motivated by biological data
    a: K. Uchizawa and W. Maass
    c: Graduate School of Information Science, Tohoku Univ.
    k: thereshold circuits, circuits complexity, decision tree
    e: uchizawa@maruoka.ecei.tohoku.ac.jp
17. The Reachability and related decision problems for semi-constructor TRSs
    a: I. Mitsuhashi, M. Oyamaguchi, and T. Yamada
    c: Mie university
    k: term rewriting system
    e: ichiro@cs.info.mie-u.ac.jp
18. Relation between the technique for the growing TRS and the technique under a normalizing rule in the decidability of reachability for term
    a: T. Murata, M. Sakai, N. Nishida, K. Kusakari, and T. Sakabe
    c: Graduate School of Information Science, Nagoya University
    k: tree automata, approximation, reachability for term
    e: tatsuhiko@sakabe.i.is.nagoya-u.ac.jp
19. Termination proof of non-left-normal metaterm based on transformation and partial evaluation
    a: H. Takojima, M. Sakai, T. Sakabe, N. Nishida, K. Kusakari, and T. Sakabe
    c: Graduate School of Information Science, Nagoya University
    k: term rewriting system, metaterm rewriting calculus, termination
    e: takojima@sakabe.i.is.nagoya-u.ac.jp
20. Equivalent transformation of TRSs for completeness of weakly innermost strategy
    a: K. Okamoto, M. Sakai, T. Sakabe, N. Nishida, K. Kusakari, and T. Sakabe
    c: Graduate School of Information Science, Nagoya University
    k: term rewriting system, rewiriting strategy, TRS-transformation
    e: okamo@sakabe.i.is.nagoya-u.ac.jp
21. An improved recursive decomposition ordering for term rewriting systems revisited
    a: M. Iwami
    c: Faculty of Science and Eng., Shimane University
    k: term rewriting system, termination, improved recursive decomposition ordering, simplification ordering
    e: munehiro@cis.shimane-u.ac.jp
22. Algorithm of probabilistic timed simulation for probabilistic timed automata
    a: H. Kodera and S. Yamane
    c: Kanazawa University
    k: formal verification, probabilistic timed automata, simulation
    e: kodera@csl.ec.t.kanazawa-u.ac.jp
23. Hausdorff dimension and the stochastic traveling salesman problem
    a: H. Takahashi
    c: Dept. of Mathematical and Computing Sciences, Tokyo Inst. of Tech.
    k: Hausdorff dimension, traveling salesman problem, BHH theorem
    e: Hayato.Takahashi@is.titech.ac.jp
24. NP-completeness of generalized Puyopuyo, a puzzle problem
    a: M. Teruhisa and Y. Takenaga
    c: University of Electro-Communications, Dept. of Computer Science
    k: computational complexity, puzzle
    e: teru@edico.net
25. Coloring of comparability+ke graphs
    a: K. Higashide and Y. Takenaga
    c: University of Electro-Communications, Dept. of Computer Science
    k: comparability graph, vertex coloring problem, parameterized complexty
    e: higa@crimson.cs.uec.ac.jp
26. Perfectness and imperfectness of unit disk graphs on triangular lattice points
    a: Y. Miyamoto and T. Matsui
    c: Sophia University
    k: graph, coloring, algorithm
    e: y-miyamo@sophia.ac.jp
27. An approximation algorithm for matroid covering
    a: S. Kawano, Y. Otachi, and K. Yamazaki
    c: Gunma University
    k: approximation algorithms, matroid covering, edge-arboricity
    e: kawano@msc.cs.gunma-u.ac.jp

    Student Session

28. An algorithm for generating monotone trees
    a: Y. Niisato, Y. Kusakari, K. Masao, and N. Junichi
    c: Akita Prefectural University
    k: computational geometry, linkage, monotone tree, generating algorithm E-mail:m06b007@akita-pu.ac.jp
29. A polynomial time algorithm for 2-link-puzzle
    a: K. Makino
    c: Dept. of Information Sciences, Tokyo Inst. of Tech.
    k: complexity, algorithm, hamiltonian path, vertex disjoint path, rectangular grid graph
    e: makino2@is.titech.ac.jp
30. An improved approximation ratio for task scheduling algorithm using maximun matching
    a: S. Niimi, M. Oyamaguchi, Y. Ohta, and K. Yamamoto
    c: Faculty of Engineering, Mie University
    k: approximation algorithm, scheduling
    e: niimi@cs.info.mie-u.ac.jp
31. On digraphs obtained by shift operation
    a: Y. Tanaka and Y. Shibata
    c: Gunma Univ.
    k: de Bruijn digraph, Kautz digraph, group action graph
    e: tanaka@msc.cs.gunma-u.ac.jp
32. Reverssible celluler automata with triplet local transition rule
    a: T. Kawahara, K. Honda, S. Inokuchi, and T. Sato
    c: Dept. of Informatics, Kyushu University
    k: quantum cellular automata, shift automata, regular expressions
    e: ie204006@i.kyushu-u.ac.jp
33. A construction method of universal reversible Turing machines
    a: T. Abe and K. Morita
    c: Graduate School of Eng., Hiroshima University
    k: reversible computing, universal Turing machine
    e: abe@iec.hiroshima-u.ac.jp
34. Error analysis of factor oracles
    a: H. Iwasaki
    c: Dept. of Information Sciences, Tokyo Inst. of Tech.
    k: factor oracle ,string matching,data structure
    e: iwasaki2@is.titech.ac.jp

    Feb. 1st (Wed)

35. Chaitin's halting probability $\Omega$ and quantum measurements in an infinite dimensional quantum system
    a: K. Tadaki
    c: 21st Century Center Of Excellence Program, Chuo University
    k: algorithmic information theory, quantum measurement, POVM, computability in analysis, program-size complexity
    e: tadaki@kc.chuo-u.ac.jp
36. Robust quantum algorithms for oracle identification
    a: K. Iwama, A. Kawachi, R. Raymond, and S. Yamashita
    c: Graduate School of Informatics, Kyoto Univ. / Quantum Computation and Information, ERATO
    k: quantum computing, algorithms, oracle computation
    e: raymond@kuis.kyoto-u.ac.jp
37. A qutantum algorithm for counting string pattern occurrences approximately
    a: T. Kobayashi, H. Ono, K. Sadakane, and M. Yamashita
    c: Graduate School of Information Sci. and Electrical Eng., Kyushu Univ.
    k: pattern occurrences, quantum algorithm, counting, string search with mismatches
    e: kobayasi@tcslab.csce.kyushu-u.ac.jp
38. Modeling molecular conforamational change and theoretical analysis on reaction rate
    a: M. Shiozaki, H. Ono, K. Sadakane, and M. Yamashita
    c: Graduate School of Information Sci. and Electrical Eng., Kyushu Univ.
    k: molecular programming, Marcov process, reaction rate
    e: masashio@tcslab.csce.kyushu-u.ac.jp
39. A fast heuristic algorithm for barrier heights estimation in DNA molecular reactions
    a: T. Takeda, H. Ono, K. Sadakane, and M. Yamashita
    c: Graduate School of Information Sci. and Electrical Eng., Kyushu Univ.
    k: DNA computing, barrier height, Morgan and Higgs' heuristics, local search
    e: takeda@tcslab.csce.kyushu-u.ac.jp
40. Construction of sequential machines in an asyncronous cellular space
    a: J. Qi and K. Morita
    c: Graduate School of Eng., Hiroshima University
    k: asynchronous cellular automaton, sequential machine, logical universality
    e: morita@iec.hiroshima-u.ac.jp
41. On universal hyperbolic cellular automata
    a: K. Imai, C. Iwamoto, and K. Morita
    c: Graduate School of Eng., Hiroshima University
    k: hyperbolic cellular automata, computation-universality
    e: imai@iec.hiroshima-u.ac.jp
42. On algebraic structures of neighborhoods of cellular automata
    a: H. Nishio, M. Margenstern, and F. von Haeseler
    c: Kyoto University (ex)
    k: cellular automata, neighborhoods, algebraic structure
    e: YRA05762@nifty.ne.jp
43. Acceleration of parametric verification for parametric time-interval automata
    a: H. Hashimoto, T. Tanimoto, A. Nakata, and T. Higashino
    c: Osaka University
    k: timed automata, model checking, parametric verification, state space reduction, regular expression
    e: h-hasimt@ist.osaka-u.ac.jp