Research Interests of Charles Kelemen
I am generally interested in the areas of Theory, Computational
Complexity, and Algorithms. Many years ago I did some research
in each of these areas. More recently I have been working on
Seeking a Refined Chomsky-like Hierarchy for Finite Transducers.
Rich Wicentowski has alerted me to the use of FSTs in computational
linguistics. I do not know anything about this but would be
interested in exploring it some time. I could also be interested
in trying to develop some sort of graphical transducer simulator
if it would not be reinventing the wheel.
Seeking a Refined Chomsky-like Hierarchy for Finite Transducers
One of the biggest fundamental issues in computer science is the
attempt to quantify differences in computational power and efficiency
between deterministic devices, randomized devices, and fully
non-deterministic devices. The biggest open question of this sort is
the ? P = NP ? question (resolution of which will earn a $1,000,000
dollar reward as well as assured tenure at any college or university
in the world). The ? P = NP ? question concerns Turing Machines.
There are many simpler but less general-purpose computational models.
Many of these have practical implementations in embedded devices.
While much is known about the acceptor version of these devices, less
is known about the transducer variants. Twenty+ years ago some
colleagues and I (Demers, Kelemen, Reusch) at Cornell looked at the
translation (and coding-decoding) capabilities of finite state
transducers ("On some decidable properties of finite state
translations" ACTA INFORMATICA (17) 1982, 349-364). A 1983 review of
our paper appearing in COMPUTING REVIEWS said, "...if we are to have
a well-founded science of computing, it will need to be based on
basic, intuitive results of what we can and cannot do, like the ones
presented here..."
The fact that Turing machines are properly more powerful than linear
bounded automata which are properly more powerful than pushdown
automata which are properly more powerful than dfas is called the
Chomsky hierarchy. Since nondeterministic two-way pebble automata are
equivalent (in terms of what they can accept) to ordinary dfa, they
form one level in the hierarchy. But, nondeterminism and pebble
capability make a difference for finite state transducers. This
means that a Chomsky-like hierarchy for transducers must be more
refined than that for automata. It is also the case that many
classes of transducers fail to be hierarchical.
We propose to develop and prove the correctness of a refined
Chomsky-like hierarchy for transducers with various combinations of
the use of or exclusion of: nondeterminism, epsilon-moves, pushdown
store, two-way, pebble markers, nested pebbles, and endmarkers.
Furthermore, where there is lack of hierarchy, it will be proved.
Working with undergraduate students in 2001-2002 and the summer of
2003, examples and counter-examples have been constructed for
deterministic epsilon-free transducers. Some theorems to show that a
translation cannot be achieved by certain types of devices have also
been obtained. However many characterizations are currently missing.
An example of a translation that can be realized by a pushdown
transducer but cannot be achieved by any 2-way dft has been obtained
and the results proved. What about a non-deterministic 2-way pebble
transducer? At the present time, we do not have a refined enough
characterization of the kinds of translations achievable by
non-deterministic pebble transducers to answer this. It is this sort
of refined characterization that is the focus of our current work.
Similar refined characterizations will be sought for transducers with
endmarkers, epsilon-moves, etc.