/ Satoshi Okawa / Professor
/ Zoltan Esik / Visiting Professor
/ Qian Ping Gu / Associate Professor
/ Takafumi Hayashi / Associate Professor
/ Shuichi Yukita / Associate Professor
The research and education activities in this laboratory focus on the theoretical foundations of computers and computations. In particular, our work covers the following areas.
The second part of our work is the creative research in some specific areas of the theoretical foundations of computer science. Currently, we are working on
Machine learning is another major area that we are interested in. Our focuses are on computational learning theory and its relationship with empirical machine learning conducted in the field of artificial intelligence. The works in dynamical systems in discrete mathematics include tessellation automata theory, algebra structures of interconnection networks, and so on. The works in formal language theory focus on homomorphic characterization, Dyck reduction,, and so on. Many of our works have been published/accepted by leading international journals and conferences.
The research activities in this laboratory are based on the free work of each faulty member. Faculty members exchange their ideas and results through regular seminars and free discussions to work on common global areas. Several leading experts in the world were invited to give talks in several areas of computer science last year. These talks have greatly stimulated and brought fresh air to the work here. Joint researchs with other laboratories and other universities/institutions have been actively conducted as well.
The members of this laboratory give lectures in discrete mathematics, geometry, algorithms and data structures, programming languages, language processing systems, and guide student extracurricular projects (SCCP). Currently, there are three SCCP projects in this laboratory:
Refereed Journal Papers
This paper introduces the penmutational graph, a new network topology, which preserves the same desirable properties as those of a star graph topology. A permutational graph can be decomposed into subgraphs induced by node sets defined by equivalence classes. Using this decomposition, its structual properties as well as the relationship among graph families, permutational graphs, star graphs, and complete graphs are studied. Moreover, the diameters of permutational graphs are investigated and good estimates are obtained which are better than those of some network topologies of similar orders.
This paper presents both new analytical and new numerical solutions to the problem of generating waveforms exhibiting a low peak-to-peak factor. One important application of these results is in the generation of pseudo-white noise signals that are commonly uses in multi-frequency measurements. These measurements often require maximum signal-to-noise ratio while maintaining the lowest peak-to-peak excursion. The new synthesis scheme introduced in this paper uses the Discrete Fourier Transform (DFT) to generate pseudo-white noise sequence that theoretically has a minimized peak-to-peak factor, $F_{p-p}$. Unlike theoretical works in the literature, the method presented here is based in purely discrete mathematics, and hence is directly applicable to the digital synthesis of signals. With this method the shape of the signal can be controlled with about $\sqrt{N}$ parameters given N harmonic components. A different permutation of the same set of offset phases of the ``source harmonics'' %$\{\psi_{\kappa}\}_{\kappa=1}^{\sqrt{N}-1}$ creates an entirely different sequence.
Abstract: An undirected routing problem is a pair $(G, R)$ where $G$ is an undirected graph and $R$ is an undirected multigraph such that $V(G) = V(R)$. A {\em solution} to an undirected routing problem $(G, R)$ is a collection $P$ of undirected paths of $G$ (possibly containing multiple occurrences of the same path) such that edges of $R$ are in one-to-one correspondence with the paths of $P$, with the path corresponding to edge $\{u, v\}$ connecting $u$ and $v$. We say that a collection of paths $P$ is $k$-colorable if each path of $P$ can be colored by one of the $k$ colors so that the paths of the same color are edge-disjoint (each edge of $G$ appears at most once in the paths of each single color). In the circuit-switched routing context, and in optical network applications in particular, it is desirable to find a solution to a routing problem that is colorable with as few colors as possible. Let $Q_n$ denote the $n$-dimensional hypercube, for arbitrary $n \geq 1$. We show that a routing problem $(Q_n, R)$ always admits a $4d$-colorable solution where $d$ is the maximum vertex degree of $R$. This improves over the $16\lceil d/2\rceil $-color result which is implicit in the previous work of Aumann and Rabani [SODA95, pages 567-576]. Since, for any positive $d$, there is a multigraph $R$ of degree $d$ such that any solution to $(Q_n, R)$ requires at least $d$ colors, our result is tight up to a factor of four. In fact, when $d = 1$, it is tight up to a factor of two, since there is a graph of degree one (the antipodal matching) that requires two colors.
Unicast in hypercubes with large number of faulty nodes.
Cluster fault tolerant routing in star graphs.
A 2-approximation algorithm for genome rearrangements by reversals and transpositions.
An efficient algorithm for $k$-pairwise disjoint paths problem in star graphs.
Node-to-set and set-to-set cluster fault tolerant routing in hypercubes.
The notions of a Garden-of-Eden(GOE) configuration and mutually erasable configurations were discovered and investigated in the framework of Euclidean tessellations in the 1960s and 1970s. In 1993, Machi and Mignosi extended the GOE theorem for tessellation automata on Cayley graphs of non-exponential growth.
We give an alternative proof to the GOE theorem for the discrete Heisenberg groups. Our proof has the advantage that it fully exploits the particular group structure so that a Moore-Myhill like tiling can be explicitly constructed. The tiling, as the wording suggests, is a spatially economic covering. The non-uniform packing method is introduced as a key technique for the construction."
Dynamical theory of cellular automata on groups is developed. Main results are non-Euclidean extensions of Sato and Honda's results on the dynamics of Euclidean cellular automata. The notion of the period of a configuration is redefined in a more group theoretical way. The notion of a co-finite configuration substitutes the notion of a periodic configuration, where the new term is given to it to reflect and emphasize the importance of finiteness involved. With these extended or substituted notions, the relations among period preservablity, injectivity, and Poisson stability of parallel maps are established. Residually finite groups are shown to give a nice topological property that co-finite configurations are dense in the configuration space.
Cellular automata on groups with asymptotic boundary conditions are studied. The main results are non-Euclidean extensions of Maruoka and Kimura's results on injectivity and surjectivity. They introduced the notions of weak injectivity/surjectivity and strong injectivity/surjectivity, and showed a hierarchical structure among these properties. The Garden of Eden (GOE) property and the periodic construction technique are used to extend their results. Groups that are residually finite and of non-exponential growth are shown to form a good class for non-Euclidean extensions of classical results.
The max-sum algebra of natural numbers has no finite equational basis.
A note on equations for commutative regular languages.
Axiomatizing iteration categories.
The variety of Kleene algebras with conversion is not finitely based.
A variety theorem for trees and theories.
The power of the group identities for iteration.
A new proof of the Krohn--Rhodes.
Group axioms for iteration.
Refereed Proceeding Papers
This paper presents a new technique for the synthesis of sets of low-peak sequences exhibiting low peak cross correlation. The sequences also have flat power spectra and are suitable for many applications requiring such sets of uncorrelated pseudo-white-noise sources. k cross correlation. The {\it ta sequence} method presented here provides the means for generating various sequences at the lengths required for such applications as system measurement (needing uncorrelated test signals), pseudo-noise synthesis (for spread spectrum communication), and audio signal processing for sound production (for enhancing spatial imagery in stereo signals synthesized from mono sources) and sound reproduction (for controlling unwanted interference effects in multiple-loudspeaker arrays).
A new technique of color image segmentation is disscused. The method uses a metric color space.
Various kinds of technique which is required for the digital image analysis of the microphotograph of composite materials is discussed.
Various kinds of technique which is required for the digital image processing of photographs.
This paper presents a new technique for the synthesis of sets of low-peak sequences exhibiting low peak cross correlation. The sequences also have flat power spectra and are suitable for many applications requiring such sets of uncorrelated pseudo-white-noise sources. k cross correlation. The ta sequence method presented here provides the means for generating various sequences at the lengths required for such applications as system measurement (needing uncorrelated test signals), pseudo-noise synthesis (for spread spectrum communication), and audio signal processing for sound production (for enhancing spatial imagery in stereo signals synthesized from mono sources) and sound reproduction (for controlling unwanted interference effects in multiple-loudspeaker arrays).
Sorting permutations and its applications in genome analysis.
Efficient broadcasting algorithms in faulty hypercubes.
Routing in hypercubes with large number of faults.
Cluster fault tolerant routing in hypercubes.
Distributed algorithms for leader election on partially ordered keys.
Computer drawing tools for knot diagrams have been developedby many researchers and educators. Some of them allow users to interact with diagrams on computer screens. These tools help students to acquire intuitive understanding of the topology of knots and links. However, in these tools algebraic representations of knot diagrams are not properly maintained during interactive operations, thereby topological invariants must be handled \textit{off-line}. To overcome this we developed a new knot diagram editor that supports Reidemeister moves in a discrete algebraic manner while the visualization of a knot is accomplished with an acceptable simplification.
A platform independent intuitive programming environment, the Visual Legacy Basic(VLB), is presented. VLB is emerged from a project that aims at providing: (1) simple yet well furnished programming tools that reduce teachers' load in elementary and high schools, (2) platform independent tools that ease the maintenance of educational software, and (3) a language design workbench for educational language developers.
Technical Reports
Accepted for presentation at the international conference WORD, Rouen, France, September, 1999.
Grants
Research on low peak psuudo white noise and its applications.
Academic Activities
Others