2 citations · 4 across the 10 of their papers we have counts for
10 papers · 1 filter
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…
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…
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…