0
$\begingroup$

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)

Improve this question
$\endgroup$
12
  • 3
    $\begingroup$ The keyword you should be looking for is "transducer", which means an automaton that produces output. $\endgroup$
    – Jan Johannsen
    May 10 at 14:37
  • 2
    $\begingroup$ 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). $\endgroup$
    – Damiano Mazza
    May 11 at 9:08
  • 2
    $\begingroup$ 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"? $\endgroup$
    – Damiano Mazza
    May 11 at 20:52
  • 1
    $\begingroup$ 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? $\endgroup$
    – Damiano Mazza
    May 11 at 20:56
  • 1
    $\begingroup$ 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! $\endgroup$
    – Sam
    May 15 at 8:10

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.