A Characterization Theorem for the K-functional Associated with the Algebraic Version of Trigonometric Jackson Integrals

2000 Mathematics Subject Classification: 41A25, 41A36.

A Note on the L2-norm of the Second Fundamental Form of Algebraic Manifolds

2000 Mathematics Subject Classification: 53C42, 53C55.

Algebraic duality theorems for infinite LP problems

In this paper we consider a primal-dual infinite linear programming problem-pair, i.e. LPs on infinite dimensional spaces with infinitely many constraints. We present two duality theorems for the problem-pair: a weak and a strong duality theorem. We do not assume any topology on the vector spaces, therefore our results are algebraic duality theorems. As an application, we consider transferable utility cooperative games with arbitrarily many players.

Algebraic theory of minimal nondeterministic finite automata with applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA’s behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

Algebraic Theory of Minimal Nondeterministic Finite Automata with Applications

Since the 1950s, the theory of deterministic and nondeterministic finite automata (DFAs and NFAs, respectively) has been a cornerstone of theoretical computer science. In this dissertation, our main object of study is minimal NFAs. In contrast with minimal DFAs, minimal NFAs are computationally challenging: first, there can be more than one minimal NFA recognizing a given language; second, the problem of converting an NFA to a minimal equivalent NFA is NP-hard, even for NFAs over a unary alphabet. Our study is based on the development of two main theories, inductive bases and partials, which in combination form the foundation for an incremental algorithm, ibas, to find minimal NFAs. An inductive basis is a collection of languages with the property that it can generate (through union) each of the left quotients of its elements. We prove a fundamental characterization theorem which says that a language can be recognized by an n-state NFA if and only if it can be generated by an n-element inductive basis. A partial is an incompletely-specified language. We say that an NFA recognizes a partial if its language extends the partial, meaning that the NFA's behavior is unconstrained on unspecified strings; it follows that a minimal NFA for a partial is also minimal for its language. We therefore direct our attention to minimal NFAs recognizing a given partial. Combining inductive bases and partials, we generalize our characterization theorem, showing that a partial can be recognized by an n-state NFA if and only if it can be generated by an n-element partial inductive basis. We apply our theory to develop and implement ibas, an incremental algorithm that finds minimal partial inductive bases generating a given partial. In the case of unary languages, ibas can often find minimal NFAs of up to 10 states in about an hour of computing time; with brute-force search this would require many trillions of years.

Locally recurrent functions, density topologies and algebraic genericity

We study the algebraic and topological genericity of certain subsets of locally recurrent functions, obtaining (among other results) algebrability and spaceability within these classes.

Locally recurrent functions, density topologies and algebraic genericity

We study the algebraic and topological genericity of certain subsets of locally recurrent functions, obtaining (among other results) algebrability and spaceability within these classes.

A monoidal algebraic model for rational SO(2)-spectra

The category of rational SO(2)--equivariant spectra admits an algebraic model. That is, there is an abelian category A(SO(2)) whose derived category is equivalent to the homotopy category of rational$SO(2)--equivariant spectra. An important question is: does this algebraic model capture the smash product of spectra? The category A(SO(2)) is known as Greenlees' standard model, it is an abelian category that has no projective objects and is constructed from modules over a non--Noetherian ring. As a consequence, the standard techniques for constructing a monoidal model structure cannot be applied. In this paper a monoidal model structure on A(SO(2)) is constructed and the derived tensor product on the homotopy category is shown to be compatible with the smash product of spectra. The method used is related to techniques developed by the author in earlier joint work with Roitzheim. That work constructed a monoidal model structure on Franke's exotic model for the K_(p)--local stable homotopy category. A monoidal Quillen equivalence to a simpler monoidal model category that has explicit generating sets is also given. Having monoidal model structures on the two categories removes a serious obstruction to constructing a series of monoidal Quillen equivalences between the algebraic model and rational SO(2)--equivariant spectra.

Problems in Algebraic Vision

Thesis (Ph.D.)--University of Washington, 2016-08

Ein Ansatz zur methoden- und werkzeuggestützten Anforderungs- und Systemspezifikation auf der Grundlage objektorientierter Modellierungs- und Simulationstechniken

Vorgestellt wird ein Ansatz zur objektorientierten Modellierung, Simulation und Animation von Informationssystemen. Es wird ein Vorgehensmodell dargestellt, mit dem unter Verwendung des beschriebenen Ansatzes Anforderungs- oder Systemspezifikationen von Rechnergestützten Informationssystemen erstellt werden können. Der Ansatz basiert auf einem Metamodell zur Beschreibung Rechnergestützter Informationssysteme und verfügt über eine rechnergestützte Modellierungsumgebung. Anhand eines Projektes zur Entwicklung einer Anforderungsspezifikation für ein rechnergestütztes Pflegedokumentations- und -kommunikationssystems wird der Einsatz der Methode beispielhaft illustriert.

Behavioral equivalence of hidden k-logics: an abstract algebraic approach

This work advances a research agenda which has as its main aim the application of Abstract Algebraic Logic (AAL) methods and tools to the specification and verification of software systems. It uses a generalization of the notion of an abstract deductive system to handle multi-sorted deductive systems which differentiate visible and hidden sorts. Two main results of the paper are obtained by generalizing properties of the Leibniz congruence — the central notion in AAL. In this paper we discuss a question we posed in [1] about the relationship between the behavioral equivalences of equivalent hidden logics. We also present a necessary and sufficient intrinsic condition for two hidden logics to be equivalent.

Causal structure of the entanglement renormalization ansatz

We show that the multiscale entanglement renormalization ansatz (MERA) can be reformulated in terms of a causality constraint on discrete quantum dynamics. This causal structure is that of de Sitter space with a flat space-like boundary, where the volume of a spacetime region corresponds to the number of variational parameters it contains. This result clarifies the nature of the ansatz, and suggests a generalization to quantum field theory. It also constitutes an independent justification of the connection between MERA and hyperbolic geometry which was proposed as a concrete implementation of the AdS-CFT correspondence.

Strong shift equivalence, algebraic K-theory, and isolating zero-dimensional dynamics on manifolds

We study the relations of shift equivalence and strong shift equivalence for matrices over a ring $\mathcal{R}$, and establish a connection between these relations and algebraic K-theory. We utilize this connection to obtain results in two areas where the shift and strong shift equivalence relations play an important role: the study of finite group extensions of shifts of finite type, and the Generalized Spectral Conjectures of Boyle and Handelman for nonnegative matrices over subrings of the real numbers. We show the refinement of the shift equivalence class of a matrix $A$ over a ring $\mathcal{R}$ by strong shift equivalence classes over the ring is classified by a quotient $NK_{1}(\mathcal{R}) / E(A,\mathcal{R})$ of the algebraic K-group $NK_{1}(\calR)$. We use the K-theory of non-commutative localizations to show that in certain cases the subgroup $E(A,\mathcal{R})$ must vanish, including the case $A$ is invertible over $\mathcal{R}$. We use the K-theory connection to clarify the structure of algebraic invariants for finite group extensions of shifts of finite type. In particular, we give a strong negative answer to a question of Parry, who asked whether the dynamical zeta function determines up to finitely many topological conjugacy classes the extensions by $G$ of a fixed mixing shift of finite type. We apply the K-theory connection to prove the equivalence of a strong and weak form of the Generalized Spectral Conjecture of Boyle and Handelman for primitive matrices over subrings of $\mathbb{R}$. We construct explicit matrices whose class in the algebraic K-group $NK_{1}(\mathcal{R})$ is non-zero for certain rings $\mathcal{R}$ motivated by applications. We study the possible dynamics of the restriction of a homeomorphism of a compact manifold to an isolated zero-dimensional set. We prove that for $n \ge 3$ every compact zero-dimensional system can arise as an isolated invariant set for a homeomorphism of a compact $n$-manifold. In dimension two, we provide obstructions and examples.

The Real-Quaternionic Indicator of Irreducible Self-Conjugate Representations of Real Reductive Algebraic Groups and A Comment on the Local Langlands Correspondence of GL(2, F )

The real-quaternionic indicator, also called the $\delta$ indicator, indicates if a self-conjugate representation is of real or quaternionic type. It is closely related to the Frobenius-Schur indicator, which we call the $\varepsilon$ indicator. The Frobenius-Schur indicator $\varepsilon(\pi)$ is known to be given by a particular value of the central character. We would like a similar result for the $\delta$ indicator. When $G$ is compact, $\delta(\pi)$ and $\varepsilon(\pi)$ coincide. In general, they are not necessarily the same. In this thesis, we will give a relation between the two indicators when $G$ is a real reductive algebraic group. This relation also leads to a formula for $\delta(\pi)$ in terms of the central character. For the second part, we consider the construction of the local Langlands correspondence of $GL(2,F)$ when $F$ is a non-Archimedean local field with odd residual characteristics. By re-examining the construction, we provide new proofs to some important properties of the correspondence. Namely, the construction is independent of the choice of additive character in the theta correspondence.