Infinite Matroids and Pushdown Automata on Infinite Words
31 mins 31 secs,
458.20 MB,
MPEG-4 Video
640x360,
29.97 fps,
44100 Hz,
1.93 Mbits/sec
Share this media item:
Embed this media item:
Embed this media item:
About this item
| Description: |
Wojciechowski, J (West Virginia University)
Wednesday 16th December 2015 - 11:30 to 12:00 |
|---|
| Created: | 2015-12-21 16:45 |
|---|---|
| Collection: | Mathematical, Foundational and Computational Aspects of the Higher Infinite |
| Publisher: | Isaac Newton Institute |
| Copyright: | Wojciechowski, J |
| Language: | eng (English) |
| Distribution: |
World
(downloadable)
|
| Explicit content: | No |
| Aspect Ratio: | 16:9 |
| Screencast: | No |
| Bumper: | UCS Default |
| Trailer: | UCS Default |
| Abstract: | 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), 563–578." 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. |
|---|---|
Available Formats
| Format | Quality | Bitrate | Size | |||
|---|---|---|---|---|---|---|
| MPEG-4 Video * | 640x360 | 1.93 Mbits/sec | 458.20 MB | View | Download | |
| WebM | 640x360 | 622.99 kbits/sec | 143.89 MB | View | Download | |
| iPod Video | 480x270 | 522.0 kbits/sec | 120.50 MB | View | Download | |
| MP3 | 44100 Hz | 249.75 kbits/sec | 57.71 MB | Listen | Download | |
| Auto | (Allows browser to choose a format it supports) | |||||