Presentations of context-free shifts

Submission note: A thesis submitted in total fulfilment of the requirements for the degree of Doctor of Philosophy to the School of Engineering and Mathematical Sciences, Faculty of Science, Technology and Engineering, La Trobe University, Bundoora.

This thesis is devoted to the study of presentations of shift spaces. The study of finite presentations of shift spaces was motivated by the study of sofic shifts. As the finiteness of a presentation implies that every bi-infinite sequence of a sofic shift is the label of some bi-infinite walk, it is natural to investigate labels of bi-infinite walks in countably infinite presentations of non-sofic shift spaces. Non-sofic shifts are not always presented completely by their follower set graphs. Thus, we introduce some variations of the notion of presentation: onesided weak presentation, one-sided strong presentation, two-sided weak presentation and two-sided strong presentation. Every bi-infinite sequence of a shift is the label of some bi-infinite walk in its two-sided strong presentation. Under these definitions, we prove the follower set graph of every shift space is a one-sided strong presentation. In particular, the follower set graph of every transitive shift space having a Markov magic word is a two-sided weak presentation. Also, every finite one-sided weak presentation of a sofic shift is a two-sided strong presentation; this is true for follower set graphs of sofic shifts. Context-free languages are the first generalisation of regular languages in the Chomsky hierarchy. We consider shifts with context-free languages - “contextfree shifts” as a generalisation of sofic shifts. Transition graphs of pushdown automata always give one-sided strong presentations for context-free shifts. We show a deterministic pushdown automaton gives a right-resolving one-sided strong presentation. Therefore, the follower set graph of a non-deterministic context-free shift is never isomorphic to the transition graph of a nondeterministic pushdown automaton. Bi-resolving presentations of sofic shifts are studied via reversible finite automata. We characterise properties of the language of a sofic shift having a bi-resolving presentation. We also investigate shifts with self-reverse languages.