COOKIES: By using this website you agree that we can place Google Analytics Cookies on your device for performance monitoring. |

University of Cambridge > Talks.cam > Isaac Newton Institute Seminar Series > Infinite Matroids and Pushdown Automata on Infinite Words

## Infinite Matroids and Pushdown Automata on Infinite WordsAdd 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 (
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. |
## Other listsBlueSci - Workshops on Science Communication Phonetics & Phonology Research Cluster Environment on the Edge Engineering Department Geotechnical Research Seminars Art Cell Gallery Exhibtions Cambridge University United Nations Association (CUUNA)## Other talksCANCELLED: How and why the growth and biomass varies across the tropics Comparative perspectives on social inequalities in life and death: an interdisciplinary conference Developing novel methods for interrogating tree ring anatomy for use in modelling carbon sequestration A V HILL LECTURE - The cortex and the hand of the primate: a special relationship International Snowballing and the Multi-Sited Research of Diplomats On Classical Tractability of Quantum Schur Sampling |