MSO definable string transductions and two-way finite state transducers

Details MSO definable string transductions and two-way finite state transducers MSO definable string transductions and two-way finite state transducers

1999-06-04

arxiv.org/abs/cs/9906007v1

Computer Science

Logic in Computer Science

63 pages, LaTeX2e. Extended abstract presented at 26-th ICALP, 1999

Scientific paper

String transductions that are definable in monadic second-order (mso) logic (without the use of parameters) are exactly those realized by deterministic two-way finite state transducers. Nondeterministic mso definable string transductions (i.e., those definable with the use of parameters) correspond to compositions of two nondeterministic two-way finite state transducers that have the finite visit property. Both families of mso definable string transductions are characterized in terms of Hennie machines, i.e., two-way finite state transducers with the finite visit property that are allowed to rewrite their input tape.

Affiliated with

Also associated with

No associations

Rating

MSO definable string transductions and two-way finite state transducers does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with MSO definable string transductions and two-way finite state transducers, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and MSO definable string transductions and two-way finite state transducers will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-126851