List of Papers Presented at EATCS/LA Workshop on TCS 2004
Go back to the workshop homepage
Created by O. Watanabe, 3/30/04.
This is a list of papers presented
at the 2nd EATCS/LA Workshop on Theoretical Computer Science,
held at Univ. Kyoto on February 2 - 4, 2004.
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.
Feb. 2nd (Mon)
-
An algebraic analysis of neighborhoods of cellular automata
a:
H. Nishio and M. Margenstern
k:
cellular automaton, neighborhood, group, generator, horse of chess
e:
YRA05762@nifty.ne.jp
-
Information dynamics of cellular automata
---log-ring size and value size of generators of subrings
a:
H. Nishio
k:
cellular automaton, polynomials over finite fields,
subring generation, computational complexity
e:
YRA05762@nifty.ne.jp
-
Generalization of partitioned quantum cellular automata and their behaviors
a:
S. Inokuchi and Y. Mizoguchi
k:
quantum comtutation, cellular automata
e:
inokuchi@math.kyushu-u.ac.jp
-
Construction of logical circuits on asyncronous cellular spaces
a:
J. Qi and K. Morita
k:
asynchronous cellular automaton, logic circuit, logical universality
e:
morita@iec.hiroshima-u.ac.jp
-
Canonical MPQ-trees for probe interval graphs
a:
R. Uehara
k:
graph isomorphism, MPQ-tree, probe interval graph
e:
uehara@komazawa-u.ac.jp
-
Computing phylogenetic roots with bounded degrees
and errors is NP-complete
a:
T. Tsukiji and Z. Chen
k:
phylogenetic root, bounded degree, NP-complete
e:
tsukiji@j.dendai.ac.jp
-
Approximating vertex cover on dense graphs
a:
T. Imamura and K. Iwama
k:
approximation algorithm, vertex cover
e:
imamura@kuis.kyoto-u.ac.jp
-
An improved approximation ratio for task scheduling algorithm
using maximum matching
a:
M. Kato, M. Oyamaguchi, Y. Ohta, S. Niimi, and K. Yamamoto
k:
task scheduling, approximation algorithm,
approximation ratio, maximum matching, communication delay
e:
kato@cs.info.mie-u.ac.jp
-
Automated competitive analysis of online problems
a:
S. Masanishi, T. Horiyama, and K. Iwama
k:
online problems, online algorithms, competitive ratio,
knapsack problem
e:
masanisi@lab2.kuis.kyoto-u.ac.jp
-
Generating instances with optimal solutions for MAX2SAT
a:
M. Yamamoto
k:
instance generation, hard instance with optimal solution, MAX2SAT
e:
masaki.yamamoto@is.titech.ac.jp
-
Linear-time algorithms for apportionment methods
a:
A. Ito and K. Inoue
k:
apportionment, proportional representative system
e:
ito@csse.yamaguchi-u.ac.jp
Feb. 3rd (Tue)
-
New and old variants of alternating context-free grammars
and their characterizations in terms of alternating pushdown automata
a:
E. Moriya, D. Hofbauer, M. Huber, and F. Otto
k:
alternating context-free grammar, alternating pushdown automaton
e:
moriya@waseda.jp
-
A polynomial time learning algorithm for a sub-class of linear
languages via queries and a representative sample
a:
Y. Tajima, Y. Kotani, and M. Terada
k:
learning via queries, grammatical inference, linear grammar
e:
ytajima@cc.tuat.ac.jp
-
Polynomial-time identification of an extension of very Simple
grammars from positive data
a:
R. Yoshinaka
k:
grammatical inference, inductive inference, simple language
e:
ry@iii.u-tokyo.ac.jp
-
Efficiently mining frequent substructures from large unordered trees
a:
T. Asai, S. Fusanobu, H. Arimura, T. Uno, and S. Nakano
k:
data mining, frequent pattern discovery, semi-structured data, graph mining
e:
t-asai@i.kyushu-u.ac.jp
-
Parallelization of constructing positive functions on logical analysis of data
a:
H. Kataoka, H. Ono, K. Sadakane, and M. Yamashita
k:
Boolean functions, data mining
e:
hiroyuki@tcslab.csce.kyushu-u.ac.jp
-
Minimum universal evaluation tree for Boolean circuits
a:
K. Makiyama, H. Ono, K. Sadakane, and M. Yamashita
k:
optimization problem, evaluation tree
e:
makiyama@c.csce.kyushu-u.ac.jp
-
Recognition of ordered tree-shellable Boolean functions
with restrictions on term length
a:
T. Toukairin and Y. Takenaga
k:
Boolean function, prime implicant, ordered tree-shellable
e:
takashi@crimson.cs.uec.ac.jp
-
Logic design method of dual-rail RSFQ circuits using decision diagrams
a:
K. Obata, K. Takagi, and N. Takagi
k:
logic design, decision diagram, dual-rail logic
e:
obata@takagi.nuie.nagoya-u.ac.jp
-
A natural extension of Shannon's expansion theorem for multi-modal logics
a:
T. Oshiba
k:
mathematical logic
e:
oshiba@ss.sugiyama-u.ac.jp
-
Verification of consistency of timeliness QoS for distributed components
a:
K. Okano, K. Mori, and K. Taniguchi
k:
timeliness QoS, linear Constraints, distributed Components
e:
okano@ist.osaka-u.ac.jp
-
An efficient scheme for (n-t)-out-of-n threshold ring signature
a:
T. Isshiki and K. Tanaka
k:
theory of cryptography, digital signature, public-key cryptosystems
e:
isshiki9@is.titech.ac.jp
-
A construction of a family of RSA functions with a common domain
a:
R. Hayashi and K. Tanaka
k:
theory of cryptography, public-key cryptosystems, RSA function
e:
hayashi9@is.titech.ac.jp
-
An algorithm for counting vertices on right-angled isosceles triangulation
a:
K. Mikawa and M. Hasegawa
k:
combinatorial algorithm, image processing
e:
mikawa@cc.niigata-u.ac.jp
-
Fast algorithms of computing the Jones polynomials of certain links
a:
M. Murakami, M. Hara, M. Yamamoto, and S. Tani
k:
computational topology, combination algorithm, knot theory
e:
ryuusagi@mac.com}
-
New crossover operators in genetic algorithms for bandwidth problem
a:
T. Satou and K. Yamazaki
k:
genetic algorithm, bandwidth problem
e:
koichi@cs.gunma-u.ac.jp
-
Procedures for multiple input functions with DNA strands
a:
S. Kamio and A. Fujiwara
k:
DNA computing
e:
fujiwara@cse.kyutech.ac.jp,
satoshi@zodiac30.cse.kyutech.ac.jp
-
Efficient computation of scalar multiplication on elliptic curve
a:
D. Adachi and T. Hirata
k:
elliptic curve, scalar multiplication, direct computation, coordinate
e:
adachi@hirata.nuee.nagoya-u.ac.jp
-
A multiplication/division VLSI algorithm for modular arithmetic
a:
M. Kaihara and N. Takagi
k:
hardware algorithm, modular multiplication, modular division
e:
mkaihara@takagi.nuie.nagoya-u.ac.jp
-
On the generative power of an extention of minimal linear grammar
a:
Kaoru Onodera
k:
formal language
e:
kaoru@akane.waseda.jp
-
Mining indirect association rules
a:
S. Hamano, Y. Mukouchi, and M. Sato
k:
data mining, negative rules, basket analysis
e:
shincan0112@wizard.osakafu-u.ac.jp
-
Simple splicing systems and extended automata
a:
R. Takaishi, Y. Mukouchi, and M. Sato
k:
regular language, splicing system, H system, extended automata
e:
gaoshilihui@aol.com}
-
On routing in update networks
a:
S. Umeno
k:
update network, routing strategy, log-space computation, randomized strategy
e:
ml4c8@yahoo.co.jp
Feb. 4th (Wed)
-
The joinability and unification problems for confluent semi-constructor TRSs
a:
I. Mitsuhashi, M. Oyamaguchi, Y. Ohta, and T. Yamada
k:
TRS, decidability, joinability, unification, semi-constructor
e:
ichiro@cs.info.mie-u.ac.jp
-
Persistence of termination for locally confluent overlay term rewriting systems
a:
M. Iwami
k:
term rewriting system, termination, persistence
e:
munehiro@cis.shimane-u.ac.jp
-
Normalizing strategy for left-linear TRSs
having identical overlay left-hand sides
a:
K. Mizuno, K. Kusakari, M. Sakai, and T. Sakabe
k:
TRS, normalizing strategy
e:
kenmizuno@sakabe.nuie.nagoya-u.ac.jp
-
Development of an analogy-based generic human-oriented theorem prover
a:
Y. Shuping, K. Yamada, K. Hirata, and M. Harao
k:
analogy, human-oriented, generic theorem prover
e:
yin@dumbo.ai.kyutech.ac.jp,
{yamada, hirata, harao}@ai.kyutech.ac.jp
-
Maximum routing and delivery algorithms for moving-targets
a:
S. Shimoirisa, Y. Asahiro, and E. Miyano
k:
capacity, moving-targets, routing and delivery
e:
shinichi@theory.ces.kyutech.ac.jp
-
An $O(n^3)$ algorithm
for obtaining the minimum vertex spanning tree on permutation graphs
a:
S. Nakayama and S. Masuyama
k:
vertex ranking, spanning tree, graph theory, algorithm
e:
masuyama@tutkie.tut.ac.jp
-
A dynamic reconfiguration tolerant self-stabilizing token
circulation algorithm in ad-hoc networks
a:
H. Kakugawa and M. Yamashita
k:
distributed algorithm, adhoc network, token
e:
h.kakugawa@computer.org}
-
Leader election on anonymous networks with restriction on memory
a:
E. Ando, H. Ono, K. Sadakane, and M. Yamashita
k:
distributed algorithm, anonymous network, leader election
e:
ando@tcslab.csce.kyushu-u.ac.jp