BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Infinite Matroids and Pushdown Automata on Infinite Words - Wojcie
 chowski\, J (West Virginia University)
DTSTART:20151216T113000Z
DTEND:20151216T120000Z
UID:TALK62919@talks.cam.ac.uk
CONTACT:42080
DESCRIPTION:The aim of this talk is to propose a topic of study that conne
 cts infinite matroids with pushdown automata on words indexed by arbitrary
  linear orders. The motivation for this study is the key open conjecture c
 oncerning infinite matroids\, the Intersection Conjecture of Nash-Williams
 \, as well as a result from my paper "Infinite Matroidal Version of Hall's
  Matching Theorem\, J. London Math. Soc.\, (2) 71 (2005)\, 563578." The ma
 in result of this paper can be described using pushdown automata as follow
 s. Let P=(M\,W) be a pair of matroids on the same groundset E. We assign t
 o P a language L_P consisting of transfinite words (indexed by ordinals) o
 n the alphabet A={-1\,0\,1}. The language L_P is obtained by taking all in
 jective transfinite sequences of the elements of E and translating each su
 ch sequence f into a word of L_P. The translation involves replacing an el
 ement of f by -1\, 0 or 1 depending on whether it is spanned by its predec
 essors in both\, one or none of the matroids M and W.\n \nTheorem There ex
 ists a pushdown automaton T on transfinite sequences in the alphabet A suc
 h that the language L_T consisting of words accepted by T has the followin
 g property: For every pair P of matroids satisfying property (*)\, the lan
 guage L_P is a subset of L_T if and only if the pair P has a packing (the 
 ground set E can be partitioned into sets E_M and E_N that are spanning in
  M and N\, respectively).\n \nThe property (*) is that M is either finitar
 y or a countable union of finite co-rank matroids and W is finitary. \n
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR