• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • No language data
  • Tagged with
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • 1
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Recognizable languages defined by two-dimensional shift spaces

Pirnot, Joni Burnette 01 June 2006 (has links)
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).

Page generated in 0.0884 seconds