2 citations · 4 across the 10 of their papers we have counts for
13 papers
Generating Fibonacci Words via the Prefix--Suffix Duplication Operation
Diego Cabrera Salamanca, Taylor J. Smith
The finite and infinite Fibonacci words are classical objects in combinatorics on words. Bio-inspired language operations provide a useful tool for studying how finite and infinite…
Complexity of Universality and Related Decision Problems for Unary Two-Dimensional Automata
Taylor J. Smith
A two-dimensional automaton is able to move its input head through its input word in four directions: upward, downward, leftward, and rightward. If we prevent the input head from m…
Primitive Two-Dimensional Words and Iterated Pedal Triangles via Symbolic Coding
Taylor J. Smith
The notion of a two-dimensional word arises naturally in the study of combinatorics on words, while the iterative construction of pedal triangles results in a rich dynamical system…
Illustrating Finite Automata with Grail+ and TikZ
Alastair May, Taylor J. Smith
In this article, we discuss a new software tool that interacts with Grail+, a library of automata-theoretic command-line utilities. Our software, the Grail+ Visualizer, takes the t…
Improved Randomized Approximation of Hard Universality and Emptiness Problems
Pantelis Andreou, Stavros Konstantinidis, Taylor J. Smith
We build on recent research on polynomial randomized approximation (PRAX) algorithms for the hard problems of NFA universality and NFA equivalence. Loosely speaking, PRAX algorithm…
Descriptional Complexity of Finite Automata -- Selected Highlights
Arto Salomaa, Kai Salomaa, Taylor J. Smith
The state complexity, respectively, nondeterministic state complexity of a regular language is the number of states of the minimal deterministic, respectively, of a minimal non…
Two-Dimensional Typewriter Automata
Taylor J. Smith
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 inp…
Degrees of Restriction for Two-Dimensional Automata
Taylor J. Smith, Kai Salomaa
A three-way (resp., two-way) two-dimensional automaton has a read-only input head that moves in three (resp., two) directions on a finite array of cells labelled by symbols of the…
Recognition and Complexity Results for Projection Languages of Two-Dimensional Automata
Taylor J. Smith, Kai Salomaa
The row projection (resp., column projection) of a two-dimensional language is the one-dimensional language consisting of all first rows (resp., first columns) of each two-dime…
Concatenation Operations and Restricted Variants of Two-Dimensional Automata
Taylor J. Smith, Kai Salomaa
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-dimensio…
Decision Problems for Restricted Variants of Two-Dimensional Automata
Taylor J. Smith, Kai Salomaa
A two-dimensional finite automaton has a read-only input head that moves in four directions on a finite array of cells labelled by symbols of the input alphabet. A three-way two-di…
Site-Directed Insertion: Decision Problems, Maximality and Minimality
Da-Jung Cho, Yo-Sub Han, Kai Salomaa +1
Site-directed insertion is an overlapping insertion operation that can be viewed as analogous to the overlap assembly or chop operations that concatenate strings by overlapping a s…
Periodicity in Rectangular Arrays
Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit +1
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 canno…