Source author record

Taylor J. Smith

Taylor J. Smith appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record

Formal Languages and Automata Theory Discrete Mathematics math.CO

Catalog footprint

What is connected

4works

3topics

4close collaborators

Actions

Connect this record

Open graph Browse works

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

preprint2022arXiv

Two-Dimensional Typewriter Automata

A typewriter automaton is a special variant of a two-dimensional automaton that receives two-dimensional words as input and is only capable of moving its input head through its input word in three directions: downward, leftward, and rightward. In addition, downward and leftward moves may only be made via a special "reset" move that simulates the action of a typewriter's carriage return. In this paper, we initiate the study of the typewriter automaton model and relate it to similar models, including three-way two-dimensional automata, boustrophedon automata, and returning automata. We study the recognition powers of the typewriter automaton model, establish closure properties of the class of languages recognized by the model, and consider operational state complexity bounds for the specific operation of row concatenation. We also provide a variety of potential future research directions pertaining to the model.

preprint2020arXiv

Concatenation Operations and Restricted Variants of Two-Dimensional Automata

A two-dimensional automaton operates on arrays of symbols. While a standard (four-way) two-dimensional automaton can move its input head in four directions, restricted two-dimensional automata are only permitted to move their input heads in three or two directions; these models are called three-way and two-way two-dimensional automata, respectively. In two dimensions, we may extend the notion of concatenation in multiple ways, depending on the words to be concatenated. We may row-concatenate (resp., column-concatenate) a pair of two-dimensional words when they have the same number of columns (resp., rows). In addition, the diagonal concatenation operation combines two words at their lower-right and upper-left corners, and is not dimension-dependent. In this paper, we investigate closure properties of restricted models of two-dimensional automata under various concatenation operations. We give non-closure results for two-way two-dimensional automata under row and column concatenation in both the deterministic and nondeterministic cases. We further give positive closure results for the same concatenation operations on unary nondeterministic two-way two-dimensional automata. Finally, we study closure properties of diagonal concatenation on both two- and three-way two-dimensional automata.

preprint2020arXiv

Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata

The row projection (resp., column projection) of a two-dimensional language $L$ is the one-dimensional language consisting of all first rows (resp., first columns) of each two-dimensional word in $L$. The operation of row projection has previously been studied under the name "frontier language", and previous work has focused on one- and two-dimensional language classes. In this paper, we study projections of languages recognized by various two-dimensional automaton classes. We show that both the row and column projections of languages recognized by (four-way) two-dimensional automata are exactly context-sensitive. We also show that the column projections of languages recognized by unary three-way two-dimensional automata can be recognized using nondeterministic logspace. Finally, we study the state complexity of projection languages for two-way two-dimensional automata, focusing on the language operations of union and diagonal concatenation.

preprint2016arXiv

Periodicity in Rectangular Arrays

We discuss several two-dimensional generalizations of the familiar Lyndon-Schutzenberger periodicity theorem for words. We consider the notion of primitive array (as one that cannot be expressed as the repetition of smaller arrays). We count the number of m x n arrays that are primitive. Finally, we show that one can test primitivity and compute the primitive root of an array in linear time.