University of South Florida

College of Arts and Sciences

Search

Menu

Give Now

Title: Coloring Knots by Maple Speaker: Masahiko Saito and Chad Smudde Time: 4:00pm‐5:00pm Place: ENB 108

In the first half of the talk, definitions of knot colorings and knot “invariants” will be given, and we will explain what we are trying to compute using Maple. Then we will demonstrate how to use the Maple programs we wrote, that are posted at www.math.usf.edu/~saito/maple.html.

Title: Duality in Bose-Mesner Algebras, Part II Speaker: Brian Curtin Time: 4:00pm‐5:00pm Place: ENB 108

Title: Duality in Bose-Mesner Algebras Speaker: Brian Curtin Time: 4:00pm‐5:00pm Place: ENB 108

We recall Bose-Mesner algebras, some examples, and some notions of duality for Bose-Mesner algebras.

Title: Cellular Automata: the Implications an Alternative Metric on the Space of Configurations, Part II Speaker: David Kephart Time: 4:00pm‐5:00pm Place: ENB 108

Title: Cellular Automata: the Implications an Alternative Metric on the Space of Configurations Speaker: David Kephart Time: 4:00pm‐5:00pm Place: ENB 108

The behavior of a cellular automaton is the iteration of a locally deterministic rule on an array of “cells”. We summarize the main characteristics of cellular automata, including what is meant by chaotic behavior. We show how the non-trivial additive CAs produce chaos even in the one-dimensional case. We define the shift-invariant metric introduced by Cattaneo, Formenti, and Mazoyer $$ d(x,y)=\limsup_{k\to\infty}\frac{\#\{i : x_i\ne y_i, |i|\le k\}}{2k+1} $$ and present some of its unexpected side-effects. Finally, we discuss prospects for applying this style of metric to the space of formal languages.

Title: How far from an affine mapping can a permutation of a vector space be?, Part II Speaker: Edwin Clark Time: 4:00pm‐5:00pm Place: ENB 108

Title: How far from an affine mapping can a permutation of a vector space be? Speaker: Edwin Clark Time: 4:00pm‐5:00pm Place: ENB 108

I will discuss a problem Xiang-dong Hou recently told to me at the dinner for a recent colloquium visitor. The problem apparently arose in cryptography, but I will not talk about that. Here's the problem: Let \(V(n,2)\) be the vector space of dimension \(n\) over the field with \(2\) elements. This is just all binary \(n\)-tuples with coordinate addition \(\operatorname{mod}\,2\). A \(2\)-dimensional affine subspace of \(V(n,2)\) is just a set \(\{x,y,z,w\}\) of 4 distinct vectors \(x\), \(y\), \(z\), \(w\) such that \(x+y+z+w=0\) (the zero vector). The question is: Does there exist a permutation \(p\) of \(V(n,2)\) such that whenever \(U\) is a \(2\)-dimensional affine subspace of \(V(n,2)\) then \(p(U)\) is NOT an affine subspace? It is known that this is true if \(n\) is odd. If \(n=2\) it is trivially false. If \(n=4\), Xiang-dong has proved it is false. The smallest open case is \(n=6\). Brute force search is out since the number of permutations of \(V(6,2)\) is \(64!\) which is larger than \(10^{90}\). I will discuss some progress on this case, a new conjecture and generalizations.

Title: Enumeration of Certain Affine Invariant Extended Cyclic Codes, Part II Speaker: Xiang-Dong Hou Time: 4:00pm‐5:00pm Place: ENB 108

Title: Enumeration of Certain Affine Invariant Extended Cyclic Codes Speaker: Xiang-Dong Hou Time: 4:00pm‐5:00pm Place: ENB 108

Let \(p\) be a prime and let \(r\), \(e\), \(m\) be positive integers such that \(r|e\) and \(e|m\). We introduce a partial order \(\prec\) in \(\mathcal{U}=\{0,1,\dotsc,\frac me(p-1)\}^e\) defined by an \(e\)-dimensional simplicial cone. We show that extended cyclic codes of length \(p^m\) over \(\mathbb{F}_{p^r}\) which are invariant under \(\mathrm{AGL}\left(\frac me,\mathbb{F}_{p^e}\right)\) can be enumerated by the ideals of \((\mathcal{U},\prec)\) which are invariant under the \(r\)th power of a circulant permutation matrix. When \(e=2\), we enumerate all such invariant ideals by describing their boundaries. Explicit formulas are obtained for the total number of \(\mathrm{AGL}(\frac m2,\mathbb{F}_{p^2})\)-invariant extended cyclic codes of length \(p^m\) over \(\mathbb{F}_{p^r}\) and for the dimension of such codes. We also enumerate all self-dual \(\mathrm{AGL}(\frac m2,\mathbb{F}_{2^2})\)-invariant extended cyclic codes of length \(2^m\) over \(\mathbb{F}_{2^2}\) when \(\frac m2\) is odd; the restrictions on the parameters are necessary conditions for the existence of self-dual affine invariant codes with \(e=2\).

Title: Tridiagonal Pairs Speaker: Hasan Al-Najjar Time: 4:00pm‐5:00pm Place: ENB 108

Let \(\mathcal{F}\) denote a field, and let \(V\) denote a vector space over \(\mathcal{F}\) with finite, positive dimension. Let \(\operatorname{End}(V)\) denote the \(\mathcal{F}\)-algebra consisting of all \(\mathcal{F}\)-linear transformations from \(V\) to \(V\). An ordered pair \(A\), \(A^*\) of elements from \(\operatorname{End}(V)\) is said to be a tridiagonal pair on \(V\) whenever the following four conditions are satisfied:

Assume that \(A\), \(A^*\) is a mild tridiagonal pair on \(V\) of \(q\)-Serre type. First, we find a nice basis for \(V\) and describe the action of \(A\), \(A^*\) on this basis in terms of six parameters. Then, we relate \(A\), \(A^*\) to the quantum affine algebra \(U_q(\widehat{\mathrm{sl}_2})\). We show that \(A\), \(A^*\) can be endowed with the structure of an irreducible module for \(U_q(\widehat{\mathrm{sl}_2})\). Finally, we consider this \(U_q(\widehat{\mathrm{sl}_2})\)-module structure on \(A\), \(A^*\). We show that it is isomorphic to a tensor product of two particular evaluation modules for \(U_q(\widehat{\mathrm{sl}_2})\).

There will be no seminar this week.

Title: Algebraic Properties of Involution Codes Speaker: Kalpana Mahalingam Time: 4:00pm‐5:00pm Place: ENB 108

We consider codes that are extensions from comma-free and infix codes. These codes are defined through an involution (\(\theta\)) on the set of symbols. Although the background motivation for these codes comes from the cross hybridization of DNA strands, they define new classes of languages and as such present new models of codes. We present definitions and some basic properties of these codes and consider properties of their syntactic monoid. Necessary and sufficient conditions on a monoid to be the syntactic monoid of a \(\theta\)-infix or a \(\theta\)-k-codes are discussed.

Title: Indefinite Sequences of Universal Quantifications: A Case Study in Fixed Point Logic, Part II Speaker: Greg McColm Time: 4:00pm‐5:00pm Place: ENB 108

Title: Indefinite Sequences of Universal Quantifications: A Case Study in Fixed Point Logic Speaker: Greg McColm Time: 4:00pm‐5:00pm Place: ENB 108

Some of the most popular logics in theoretical computer science are the “fixed point logics” that repeatedly iterate a formula or system of formulas. One of these popular logics is Least Fixed Point logic, which can be described in terms of 2-player games. Another is Datalog, which could be regarded as a near-solitaire version of the Least Fixed Point logic game, where the player associated with existential quantification gets to make most of the moves.

Both these logics can be used to characterize PTIME.

We review the least fixed point logic, and look at the Datalog-like logic where the universal quantification player makes most of the moves. We explore this “co-Datalog” logic and its strengths and weaknesses.

NOTE: There will be an organizational meeting prior to the talk.