Reducibilities between Regular Languages

Abstract

The topic of this masters thesis is to investigate when a regular set A is reducible to a regular set B in the following sense:

A is automaton reducible to B if there is an automatic and injective function f mapping A to B.

A is transducer reducible to B if there is a function f mapping A to B where f can computed by a finite nondeterministic transducer.

One of the central questions investigated is whether it holds for every two regular languages that they are comparable under the given reduction.

For the first reducibility, it is shown that any two polynomial sized regular sets are comparable and every polynomial sized regular set is reducible to every exponential sized regular set. Comparability between two exponential sized regular sets remains an open problem.

For the second reducibility, it is shown that any two regular sets are comparable and exponential sized regular sets form a single equivalence class under this reducibility.