La Trobe
38077_SOURCE01_3_A.pdf (827.9 kB)

Presentations of context-free shifts

Download (827.9 kB)
posted on 2023-01-18, 17:43 authored by Thi Thuy Dung Nguyen
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.


Center or Department

Faculty of Science, Technology and Engineering. School of Engineering and Mathematical Sciences.

Thesis type

  • Ph. D.

Awarding institution

La Trobe University

Year Awarded


Rights Statement

The thesis author retains all proprietary rights (such as copyright and patent rights) over the content of this thesis, and has granted La Trobe University permission to reproduce and communicate this version of the thesis. The author has declared that any third party copyright material contained within the thesis made available here is reproduced and communicated with permission. If you believe that any material has been made available without permission of the copyright owner please contact us with the details.

Data source

arrow migration 2023-01-10 00:15. Ref: latrobe:38077 (9e0739)

Usage metrics

    Open Theses


    No categories selected



    Ref. manager