[Shacs] Some interesting CS topics in amongst this.

[Peter Cooper]

Attendance is free and CS students are especially welcome.


On April 18, Sam Houston will host six one hour talks related to  
algebra,
logic, and computer science.  Guests are welcome, though these will be  
higher level
scientific talks to a specialist audience.

The 2:00 talk by Moshe Vardi entitled "And logic begat computer  
science" is
designed specifically for an undergraduate audience.


Tentative Schedule:

9:00 	Zoran Sunik (Texas A&M)

Title: Chinese Rings and coverings

Abstrsact: We show how to model the Chinese Rings puzzle by a group of
rooted tree automorphisms. This group can be generated by a 3-state  
automaton and it is
the iterated monodromy group of the Chebyshev - Ulam
- von Neumann map z -> z^2-2. The discussion naturally leads to the
self-covering of the unit interval by the tent map, which then leads  
to a whole family of groups
of intermediate growth (one of which is the well known Grigorchuk  
group). This is a joint
work with Volodymyr Nekrashevych.



10:00	Jeremy Alm (University of Dallas)

Title:  "How logic begat (some) combinatorics"

11:00	Elbert Walker (New Mexico State University)

"A Family of Finite De Morgan Algebras"

The algebra of truth values for fuzzy sets of type-2 consists of all
mappings from the unit interval [0,1] into itself, with operations  
certain convolutions of these
mappings with respect to pointwise max and min. This algebra has been  
studied rather
extensively in the last few years, both from an applications point of  
view and a theoretical
one. Most of the theory goes through when [0,1] is replaced by any two  
finite chains, in
which case interesting finite algebras arise---De Morgan algebras and  
Kleene algebras
in particular---and a basic question is just where these algebras fit  
into the
world of all such finite algebras. The calculation of their orders is  
an interesting
combinatorial exercise, and leads to other representations of these  
algebras. In the De
Morgan case, the algebras are characterized as those whose poset of  
join irreducible elements
has a particularly simple structure. This leads to the determination  
of the
automorphism groups of these algebras. Some combinatorial results are  
presented, detailing the
sizes of these De Morgan and Kleene algebras. Our basic tool is an  
alternate representation of
these algebras, making their operations much more intuitive.


12:00-2:00 Lunch

2:00	Moshe Vardi (Rice)

Title: "And Logic Begat Computer Science: When Giants Roamed the Earth"

During the past fifty years there has been extensive, continuous, and
growing interaction between logic and computer science. In fact, logic  
has been called "the
calculus of computer science". The argument is that logic plays a  
fundamental role in computer
science, similar to that played by calculus in the physical sciences  
and traditional
engineering disciplines. Indeed, logic plays an important role in  
areas of computer science as
disparate as architecture (logic gates), software engineering  
(specification and
verification), programming languages (semantics, logic programming),  
databases (relational
algebra and SQL), artificial intelligence (automated theorem proving),  
algorithms
(complexity and expressiveness), and theory of computation (general  
notions of
computability). This non-technical talk will provide an overview of  
the unusual effectiveness of
logic in computer science by surveying the history of logic in  
computer science,
going back all the way to Aristotle and Euclid, and showing how logic  
actually gave rise to
computer science.

3:00	Coffee Break

3:30	Jonathan Farley (CalTech)

Three Weddings and a Funeral

Act One.
At the 1981 Banff Conference on Ordered Sets, Anders Bjorner posed the
following problem (stemming from unpublished work of his in the  
1970's): Let L be a geometric
lattice of finite rank r at least 3.  Is there a matching, that is, a  
one-to-one
function from the set of atoms to the set of co-atoms sending each  
atom to a co-atom above it?
(We will also talk about subsets of atoms having a matching.)
Curtis Greene had previously proven that the answer is yes if L is  
finite.
Bjorner showed that the answer is yes if r=3.  He also showed that the  
answer is yes if the
cardinality of L is at most aleph_omega.

The resolution of this problem will clearly use the extension of Hall's
Marriage Theorem to the infinite case.  If C is a subset of atoms, let  
N[C] be the set of
co-atoms above any one of the atoms in C.  Call a subset C of atoms  
"critical" if it has a matching
and every matching is onto N[C]. As a pet problem, can one find a  
nice, direct proof
that, if L is countably infinite (maybe even of rank 3), there is no  
critical subset C of
atoms and an atom x not in C such that N[x] is a subset of N[C]?  Can  
one characterize
the lattices whose sets of atoms are critical?  (In the finite case,  
as Greene proved, they are
just the modular geometric lattices.)

Act Two.
Let S be a subset of a poset P, and let g be a strictly order- 
preserving map
from S into the linearly ordered set of integers.  Necessary and  
sufficient conditions are
found for there to be a strictly order-preserving map Psi from P to  
the set of integers
extending g.  This partially solves a problem of Daykin and Daykin  
from the 1984 Banff
Conference on Graphs and Order: They ask for a solution to the  
extension problem both for the case
where g and Psi are strictly order-preserving maps and for the case  
where g and Psi are
one-to-one order-preserving maps--- a case that remains unsettled, but  
regarding which
the following is shown:

Let P be a poset and S a subset such that P is the convex hull
of S.  Let g be an injective order-preserving map from S to the set of
integers.  Necessary and sufficient conditions are found for when g  
has an injective
order-preserving extension Psi to all of P.  The task of trying to  
prove this theorem was set by
Skilton in 1985.

Act Three.
We confirm the independence of the conditions in Rado's Generalization  
of
Hall's Marriage Theorem, thus solving a problem attributed to Rado  
from Mirsky's 1971
monograph "Transversal Theory".


4:30	Ralph McKenzie (Vanderbilt)

Title:  "Algebra, structure and algorithms"

All talks are currently scheduled to be in Room 412 of the Lee Drain
Building. 
  
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.shsu.edu/pipermail/shacs/attachments/20080417/c861e5e7/attachment.html