ACM SIGLOG News · 2016 · 77 citations · 27 references
ComputingComputer ScienceMathematicsAlgorithmsSyntaxTheory Of ComputationAutomata TheoryFinite AutomataFinite-state MachinesFormal Language FoundationsFormal LanguagesRegular LanguagesFinite Automata TheoryFinite Automata With OutputFinite-state TransducersRegular ExpressionsTransducersTwo-way AutomataTwo-way Finite Automata
The robust theory of regular languages is based on three important pillars: computation (automata), logic, and algebra. In this paper, we survey old and recent results on extensions of these pillars to functions from words to words. We consider two important classes of word functions, the rational and regular functions, respectively defined by one-way and two-way automata with output words, called transducers.
27
Transductions and Context-Free Languages
Jean Berstel · 1979 · 1.3K citations
Weak Second‐Order Arithmetic and Finite Automata
J Büchi · Mathematical logic quarterly · 1960 · 819 citations