Infinite Matroids and Pushdown Automata on Infinite Words

Add to your list(s) Download to your calendar using vCal

• Wojciechowski, J (West Virginia University)
• Wednesday 16 December 2015, 11:30-12:00
• Seminar Room 1, Newton Institute.

If you have a question about this talk, please contact webseminars.

Mathematical, Foundational and Computational Aspects of the Higher Infinite

The aim of this talk is to propose a topic of study that connects infinite matroids with pushdown automata on words indexed by arbitrary linear orders. The motivation for this study is the key open conjecture concerning 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 main result of this paper can be described using pushdown automata as follows. Let P=(M,W) be a pair of matroids on the same groundset E. We assign to P a language L_P consisting of transfinite words (indexed by ordinals) on the alphabet A={-1,0,1}. The language L_P is obtained by taking all injective transfinite sequences of the elements of E and translating each such sequence f into a word of L_P. The translation involves replacing an element of f by -1, 0 or 1 depending on whether it is spanned by its predecessors in both, one or none of the matroids M and W.

Theorem There exists a pushdown automaton T on transfinite sequences in the alphabet A such that the language L_T consisting of words accepted by T has the following property: For every pair P of matroids satisfying property (), the language 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).

The property () is that M is either finitary or a countable union of finite co-rank matroids and W is finitary.

This talk is part of the Isaac Newton Institute Seminar Series series.

This talk is included in these lists:

• All CMS events
• Featured lists
• INI info aggregator
• Isaac Newton Institute Seminar Series
• School of Physical Sciences
• Seminar Room 1, Newton Institute
• bld31

Note that ex-directory lists are not shown.