Charles Kelemen: Theory of Computation

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 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.

Charles Kelemen's homepage: https://www.cs.swarthmore.edu/~cfk