0

From what I know, there is a vast literature on language recognizers in computer science. Language recognizers are machines (e.g., Finite State Automata, Pushdown Automata, Turing Machines, ...) that, for a given string of symbols, decide if the string belongs to a given language or not.

For my research, I need to study deterministic functions that map strings to strings, i.e., $f:\Sigma^*\to\Sigma^*$. I know that some models, like Turing Machines, can be "modified" to produce a sequence of output symbols.

Is there literature where I can find a categorization of machines that maps input string to output strings? I would like to know which models exist, and their categorization (e.g., something similar to the Chomsky classification)

Sam
  • 101
  • 1
  • 3
    The keyword you should be looking for is "transducer", which means an automaton that produces output. – Jan Johannsen May 10 '23 at 14:37
  • Thanks! I now found Mealey Machine and Finite State Transducer, and very little material on "Pushdown Transducer". I am not sure if there is a classical definition for a model of "Turing complete" Transducer. Do you know some good book on the topic? It would be nice also to have a sort of "Chomsky categorization of transducer", based on their "expressivity" – Sam May 10 '23 at 15:42
  • 2
    Well, computability theory is about functions just as much as it is about languages: all the notions of formal computability that were introduced about 100 years ago were introduced to define computable functions, not languages. Most "nice enough" notions of machines/programs induce classes of functions: recursive, primitive recursive, elementary, polynomial-time-computable, logarithmic-space-computable, first-order-computable... (continued below). – Damiano Mazza May 11 '23 at 09:08
  • People focus on classes of languages, rather than classes of functions, because most function classes are trivially separable and there's nothing very interesting to say about their relationship. For example, we no not know whether $\mathsf P$ and $\mathsf{PSPACE}$ are different, but the polyomial-space-computable functions are obviously strictly more than polynomia-time-computable functions, simply because in polynomial space you may output exponentially long strings, whereas in polynomial time you can't. For automata/transducers of course the story is different, and there is more on them. – Damiano Mazza May 11 '23 at 09:12
  • Thanks, Damiano, for your answer. But let me rephrase a bit better my questions. As far as I know, there are many acceptors (automata that decide whether a string belongs to a language): i.e., Turing machines, tag systems, register machines, random access machines, linearly bounded automata, pushdown automata, finite state automata, etc. And I know well how they are classified: e.g., Turing machine, tag systems, register machines, random access machines are Turing complete (type 0), LBA are type 1 PDA are type 2, and FSA are type 3 – Sam May 11 '23 at 11:01
  • However, since yesterday, I have only discovered a few transducers (namely, Mealey machine, finite state transducer, and push-down transducers). It is true that in many cases it is trivial to transform a Turing Machine into a transducer, but I would like to use a standardized "Turing Transducer" instead of making up my own. Further, I suspect (but not sure), that Transducers could potentially have a higher number of classes: e.g., Finite State Transducers are a superset of Mealey machines. I would like to access a unified documentation on transducers, but until now, I haven't been able to – Sam May 11 '23 at 11:08
  • while I have found plenty of material on acceptors. – Sam May 11 '23 at 11:08
  • 2
    I don't understand. What's wrong with the usual notion of Turing machine that writes its output on one of its tapes? Maybe on a write-only, one-way output tape. I mean, the convention of how a Turing machine produces its output may change, but it's just a matter of minor details, the resulting notion of computable function is the same. What's wrong with taking a usual deterministic Turing machine, under any of these conventions, as the definition of "Turing transducer"? – Damiano Mazza May 11 '23 at 20:52
  • 1
    About automata-based transducers, which are not Turing-powerful, I am not an expert at all but I do know that people study them a lot. For example, this article defines a class of functions from strings to strings and characterizes it by means of several transducers. Maybe it contains references that you will find interesting? – Damiano Mazza May 11 '23 at 20:56
  • Also, about "classes": the Chomsky hierarchy is a rather old (I personally would say outdated, but maybe that's excessive) classification of languages, there's nothing really canonical about it and I don't think that any contemporary researcher in TCS would claim that there are just four classes of languages/types of acceptors. The same holds for function classes and transducers: asking whether there's a hierarchy of a fixed number of "types" to which every possible definition of transducer belongs is, in my eyes, a misguided question. But maybe I am misunderstanding you... – Damiano Mazza May 11 '23 at 21:07
  • About the Chomsky hierarchy, I found an interesting discussion here on TCS Stack Exchange: https://cstheory.stackexchange.com/q/2252. Some people definitely agree with me :-) – Damiano Mazza May 11 '23 at 21:13
  • 1
    Dear Damiano, thanks a lot for sharing Boja´nczyk paper with me. I think it is going very much in the direction I am interested in it, and introduces a lot of terminology that will help my research! I'm really glad I asked! Thanks also for pointing out that Chomsky hierarchy is outdated. I am currently a researcher in machine learning, so I am not up to date in theoretical CS (my only knowledge is what I studied during my master). I wish I had two lives to study CS in depth! :) Thanks a lot for your help! – Sam May 15 '23 at 08:10

0 Answers0