No description available.

A Fourier transform for a finite group G is an isomorphism from the complex group algebra CG to a direct product of complex matrix algebras, which are determined beforehand by the structure of G. Given such an isomorphism, naive application of that isomorphism to an arbitrary element of CG takes time proportional to |G|2. A fast Fourier transform for some (family of) groups is an algorithm which computes the Fourier transform of a group G of the family in less than O(|G|2) time, generally O(|G| log |G|) or O(|G|(log |G|)2). I describe the construction of a fast Fourier transform for the special linear groups SL(q) with q = 2n.

No description available.

No description available.

Thesis (M.Sc. in Physical Chemistry) -- Faculty of Graduate Studies, Mahidol University, 1978. / Supported by the University Development Commission and the National Research Council.

Thesis (Ph. D.)--Virginia Polytechnic Institute and State University, 1993. / Vita. Abstract. Includes bibliographical references (leaves 224-239). Also available via the Internet.

In this thesis we present two important closely related examples of Bratteli diagrams: the Pascal triangle and the Eulerian Bratteli diagram. The former is well-known and related to binomial coefficients. The latter, which is the main object of the thesis, is related to the Eulerian numbers. Bratteli diagrams were introduced in 1972 by Ola Bratteli in his study of approximately finite dimensional (AF) C*-algebras. In 1976, George Arthur Elliott associated to an AF C*-algebra or to a corresponding Bratteli diagram an ordered group, he called dimension group. In the first part of the thesis we study the space of infinite paths of the Eulerian diagram, and we realize it as a projective limit of finite permutation groups. In the second part, we study the state space of the dimension group associated to the Eulerian Bratteli diagram. It is a compact convex set and we describe its extremal points. Finally, we use this description to give a necessary and sufficient condition for an element of this dimension group to be positive.

Because of limited tester time and memory, a primary goal of digital circuit manufacture test generation is to create compact test sets. Test generation programs that use Ordered Binary Decision Diagrams (OBDDs) as their primary functional representation excel at this task. Unfortunately, the use of OBDDs limits the application of these test generation programs to small circuits. This is because the size of the OBDD used to represent a function can be exponential in the number of the function's switching variables. Working with these functions can cause OBDD-based programs to exceed acceptable time and memory limits. This research proposes using Ordered Partial Decision Diagrams (OPDDs) instead as the primary functional representation for test generation systems. By limiting the number of vertices allowed in a single OPDD, complex functions can be partially represented in order to save time and memory. An OPDD-based test generation system is developed and techniques which improve its performance are evaluated on a small benchmark circuit. The new system is then demonstrated on larger and more complex circuits than its OBDD-based counterpart allows.

Because of limited tester time and memory, a primary goal of digital circuit manufacture test generation is to create compact test sets. Test generation programs that use Ordered Binary Decision Diagrams (OBDDs) as their primary functional representation excel at this task. Unfortunately, the use of OBDDs limits the application of these test generation programs to small circuits. This is because the size of the OBDD used to represent a function can be exponential in the number of the function's switching variables. Working with these functions can cause OBDD-based programs to exceed acceptable time and memory limits. This research proposes using Ordered Partial Decision Diagrams (OPDDs) instead as the primary functional representation for test generation systems. By limiting the number of vertices allowed in a single OPDD, complex functions can be partially represented in order to save time and memory. An OPDD-based test generation system is developed and techniques which improve its performance are evaluated on a small benchmark circuit. The new system is then demonstrated on larger and more complex circuits than its OBDD-based counterpart allows.

Influence diagrams (ID) are graphical frameworks for decision making in stochastic situations with mathematical models embedded in them. The goal of an optimal algorithm for an ID is to find a strategy that would maximize the expected utility. We will explain a few algorithms for influence diagrams in this thesis. There exists an obvious temporal ordering among decisions in an ID; and any information used in the past will always be available in the future: these two properties are respectively called the “regularity” and “noforgetting” assumptions. A limited memory influence diagram (LIMID) does not follow these two properties. The existing state-of-art depthirst-branch-and-bound (DFBnB) algorithm for solving influence diagrams does not scale very well due to the exponential increase of nodes proportional to the depth of the search (or total stages in the ID). In this paper, we propose and implement an algorithm that combines two widely used methods, depth first branch-andbound search (DFBnB) and value iteration with incremental pruning, for solving IDs and POMDPs, respectively. We describe an algorithm to convert the strategy tree to a strategy graph. Experiments show the effectiveness of these approaches. Algorithms for solving traditional influence diagrams are not easily generalized to solve LIMIDs, however, and only recently have exact algorithms for solving LIMIDs been developed. In this thesis, we provide an exact algorithm for solving LIMIDs that is based on branch-and-bound search. Our approach is related to the approach of solving an influence diagram by converting it to an equivalent decision tree, with the difference that the LIMID is converted to a much smaller decision graph that can be searched more efficiently.