MSO definable string transductions and two-way finite-state transducers
Open Access
- 1 April 2001
- journal article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Computational Logic
- Vol. 2 (2) , 216-254
Abstract
We extend a classic result of Büchi, Elgot, and Trakhtenbrot: MSO definable string transductions i.e., string-to-string functions that are definable by an interpretation using monadic second-order (MSO) logic, are exactly those realized by deterministic two-way finite-state transducers, i.e., finite-state automata with a two-way input tape and a one-way output tape. Consequently, the equivalence of two mso definable string transductions is decidable. In the nondeterministic case however, MSO definable string tranductions, i.e., binary relations on strings that are mso definable by an interpretation with parameters, are incomparable to those realized by nondeterministic two-way finite-state transducers. This is a motivation to look for another machine model, and we show that both classes of MSO definable string transductions are characterized in terms of Hennie machines, i.e., two-way finite-state transducers that are allowed to rewrite their input tape, but may visit each position of their input only a bounded number of times.Keywords
All Related Versions
This publication has 46 references indexed in Scilit:
- A Comparison of Tree Transductions Defined by Monadic Second Order Logic and by Attribute GrammarsJournal of Computer and System Sciences, 2000
- Two-way automata and length-preserving homomorphismsTheory of Computing Systems, 1996
- Monadic second-order definable graph transductions: a surveyTheoretical Computer Science, 1994
- The monadic second-order logic of graphs VII: graphs as relational structuresTheoretical Computer Science, 1992
- The monadic second-order logic of graphs V: on closing the gap between definability and recognizabilityTheoretical Computer Science, 1991
- Serial composition of 2-way finite-state transducers and simple programs on stringsLecture Notes in Computer Science, 1977
- A characterization of two-way deterministic classes of languagesJournal of Computer and System Sciences, 1970
- A general theory of translationTheory of Computing Systems, 1969
- Weak Second‐Order Arithmetic and Finite AutomataMathematical Logic Quarterly, 1960
- Three models for the description of languageIEEE Transactions on Information Theory, 1956