14 citations · 33 across the 10 of their papers we have counts for
12 papers
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…
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…