Back to search

University of South Florida

Recognizable Languages Defined by Two-dimensional Shift Spaces

Abstract

dc:description

There are numerous connections between the theory of formal languages and that of symbolic dynamics. In each, the transition from one dimension to two dimensionsis accompanied by much difficulty due in large part to the emptiness problem, which is related to the presence (or lack thereof) of periodic points and is known to be undecidable. Here, we focus on two-dimensional languages that have the property that all blocks allowed by the language can be extended to a configuration of the plane satisfying the structure of the language; for such languages the emptiness problem is not an issue. We first show that dot systems may be associated with two-dimensional languages having this property, so that we might employ these languages as varied examples. We next define a new type of finite automaton and with it, a tool for recognizing two-dimensional "strings" of data. It is then shown that these automata correctly represent the sofic shift spaces that result from the application of block maps to shifts of finite type. Thereafter, these automataare utilized to investigate properties of transitivity in the two-dimensional languages that they represent. More specifically, new definitions for different types of two-dimensional transitivity are adapted from topological dynamics and then illustrated through the use of dot systems. The appearance of periodic points in the languages represented by these automata is also explored, with a main result being that the existence of a periodic pointis guaranteed under certain conditions. Finally, issues of equivalence are introduced in the two-dimensional setting with regards to formal languages (syntactic monoids) and symbolic dynamics (the follower sets of a graph representing a sofic shift space).

Degree

thesis:*
Level thesis:degree_level
Dissertation
Discipline thesis:degree_discipline
Mathematics and Statistics
Grantor
University of South Florida
Year dc:date
2006

Author and committee

dc:creator, dc:contributor.*
Author dc:creator
  • Pirnot, Joni Burnette
Contributors dc:contributor
  • Natasha Jonoska, Ph.D.
  • Lilia Woods, Ph.D.
  • Gregory McColm, Ph.D.
  • Stephen Suen, Ph.D.
  • Masahico Saito, Ph.D.
  • Xiang-Dong Hou, Ph.D.

Subjects

dc:subject × 7

Rights

Language dc:language
EN-US

Identifiers

dc:identifier.*
Repository record dc:identifier
https://digitalcommons.usf.edu/etd/2660

Chain of custody

source
Harvested from
University of South Florida
Base URL
digitalcommons.usf.edu/do/oai/
Last updated
2026-11-19
Source record
OAI-PMH GetRecord
citation

Pirnot, Joni Burnette. Recognizable Languages Defined by Two-dimensional Shift Spaces. Dissertation thesis, University of South Florida, 2006. https://digitalcommons.usf.edu/etd/2660