Please use this identifier to cite or link to this item: http://hdl.handle.net/1942/15354
Full metadata record
DC FieldValueLanguage
dc.contributor.authorFiliot, Emmanuel-
dc.contributor.authorGauwin, Olivier-
dc.contributor.authorReynier, Pierre-Alain-
dc.contributor.authorSERVAIS, Frederic-
dc.date.accessioned2013-07-25T14:16:22Z-
dc.date.available2013-07-25T14:16:22Z-
dc.date.issued2013-
dc.identifier.citation2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, p. 468-477-
dc.identifier.isbn9781479904136-
dc.identifier.urihttp://hdl.handle.net/1942/15354-
dc.description.abstractAny two-way finite state automaton is equivalent to some one-way finite state automaton. This well-known result, shown by Rabin and Scott and independently by Shepherdson, states that two-way finite state automata (even non-deterministic) characterize the class of regular languages. It is also known that this result does not extend to finite string transductions: (deterministic) two-way finite state transducers strictly extend the expressive power of (functional) one-way transducers. In particular deterministic two-way transducers capture exactly the class of MSO-transductions of finite strings. In this paper, we address the following definability problem: given a function defined by a two-way finite state transducer, is it definable by a one-way finite state transducer? By extending Rabin and Scott’s proof to transductions, we show that this problem is decidable. Our procedure builds a one-way transducer, which is equivalent to the two-way transducer, whenever one exists.-
dc.language.isoen-
dc.publisherIEEE-
dc.subject.otherFormal Languages, Transducer, MSO-
dc.titleFrom Two-Way to One-Way Finite State Transducers-
dc.typeProceedings Paper-
local.bibliographicCitation.conferencedateJune 25–28, 2013-
local.bibliographicCitation.conferencename28th Annual ACM/IEEE Symposium on Logic in Computer Science-
local.bibliographicCitation.conferenceplaceNew Orleans, USA-
dc.identifier.epage477-
dc.identifier.spage468-
local.bibliographicCitation.jcatC2-
dc.relation.references[1] J. R. Bu ̈chi, “On a decision method in restricted second order arithmetic,” in Proc. of the International Congress on Logic, Methodology, and Philosophy of Science. Stanford University Press, 1962, pp. 1–11. [2] J. W. Thatcher and J. B. Wright, “Generalized finite automata theory with an application to a decision problem of second-order logic,” Mathematical Systems Theory, vol. 2, no. 1, pp. 57–81, 1968. [3] M. O. Rabin and D. Scott, “Finite automata and their decision problems,” IBM Journal of Research and Development, vol. 3, no. 2, pp. 114–125, 1959. [4] J. C. Shepherdson, “The reduction of two-way automata to one-way automata,” IBM Journal of Research and Development, vol. 3, no. 2, pp. 198–200, 1959. [5] J. Berstel, Transductions and context-free languages. Teubner, 1979. [6] J. Sakarovich, Elements of Automata Theory. Cambridge University Press, 2009. [7] B. Courcelle, “The expression of graph properties and graph transformations in monadic second-order logic,” in Handbook of Graph Transformation. World Scientific, 1996, vol. I, Foundations. [8] ——, “Monadic second-order definable graph transductions: a survey,” Theoretical Computer Science, vol. 126, no. 1, pp. 53–75, 1994. [9] J. Engelfriet and H. J. Hoogeboom, “MSO definable string transductions and two-way finite-state transducers,” ACM Transactions on Computa- tional Logic (TOCL), vol. 2, no. 2, pp. 216–254, 2001. [10] R. Alur and P. Cˇ erny ́ , “Expressiveness of streaming string transducers,” in FSTTCS, vol. 8. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2010, pp. 1–12. [11] ——, “Streaming transducers for algorithmic verification of single-pass list-processing programs,” in POPL, 2011, pp. 599–610. [12] R. de Souza, “Uniformisation of two-way transducers,” in LATA, ser. LNCS, vol. 7810. Springer, 2013, pp. 547–558. [13] E. M. Gurari and O. H. Ibarra, “A note on finite-valued and finitely ambiguous transducers,” Mathematical Systems Theory, vol. 16, no. 1, pp. 61–66, 1983. [14] M.-P. Be ́al, O. Carton, C. Prieur, and J. Sakarovitch, “Squaring transduc- ers: an efficient procedure for deciding functionality and sequentiality,” Theoretical Computer Science, vol. 292, no. 1, pp. 45–63, 2003. [15] A. Weber and R. Klemm, “Economy of description for single-valued transducers,” Information and Computation, vol. 118, no. 2, pp. 327– 340, 1995. [16] K. Culik and J. Karhumaki, “The equivalence problem for single- valued two-way transducers (on NPDT0L languages) is decidable,” SIAM Journal on Computing, vol. 16, no. 2, pp. 221–230, 1987. [17] M. Y. Vardi, “A note on the reduction of two-way automata to one-way automata,” Information Processing Letters, vol. 30, no. 5, pp. 261–264, 1989. [18] E. Filiot, O. Gauwin, P.-A. Reynier, and F. Servais, “Streamability of nested word transductions,” in FSTTCS, vol. 13. Schloss Dagstuhl– Leibniz-Zentrum fuer Informatik, 2011, pp. 312–324. [19] L. Segoufin and C. Sirangelo, “Constant-memory validation of streaming XML documents against DTDs,” in ICDT, ser. LNCS, vol. 4353. Springer, 2007, pp. 299–313. [20] V. Ba ́ra ́ny, C. Lo ̈ding, and O. Serre, “Regularity problems for visibly pushdown languages,” in STACS, ser. LNCS, vol. 3884. Springer, 2006, pp. 420–431. [21] O. Gauwin, J. Niehren, and S. Tison, “Queries on XML streams with bounded delay and concurrency,” Information and Computation, vol. 209, no. 3, pp. 409–442, 2011. [22] O. Carton, “Two-way transducers with a two-way output tape,” in DLT, ser. LNCS, vol. 7410. Springer, 2012, pp. 263–272. [23] M. Anselmo, “Two-way automata with multiplicity,” in ICALP, ser. LNCS. Springer, 1990, vol. 443, pp. 88–102. [24] E. Filiot, O. Gauwin, P.-A. Reynier, and F. Servais, “From two-way to one-way finite state transducers,” CoRR, vol. abs/1301.5197, 2013. 477 [25] C. Choffrut and J. Karhuma ̈ki, Combinatorics on words. Verlag, 1997, vol. 1, pp. 329–438. [26] J. Hopcroft and J. Ullman, Introduction to Automata Theory. Wesley, 1979. Springer- Addison- [27] J.-C.Birget,“State-complexityoffinite-statedevices,statecompressibil- ity and incompressibility,” Mathematical Systems Theory, vol. 26, no. 3, pp. 237–269, 1993. [28] R. Alur, E. Filiot, and A. Trivedi, “Regular transformations of infinite strings,” in LICS. IEEE, 2012, pp. 65–74.-
local.type.refereedRefereed-
local.type.specifiedProceedings Paper-
dc.identifier.doi10.1109/LICS.2013.53-
local.bibliographicCitation.btitle2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science-
item.contributorFiliot, Emmanuel-
item.contributorGauwin, Olivier-
item.contributorReynier, Pierre-Alain-
item.contributorSERVAIS, Frederic-
item.fulltextWith Fulltext-
item.accessRightsOpen Access-
item.fullcitationFiliot, Emmanuel; Gauwin, Olivier; Reynier, Pierre-Alain & SERVAIS, Frederic (2013) From Two-Way to One-Way Finite State Transducers. In: 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, p. 468-477.-
Appears in Collections:Research publications
Files in This Item:
File Description SizeFormat 
5020a468.pdfPublished version285.39 kBAdobe PDFView/Open
Show simple item record

Google ScholarTM

Check

Altmetric


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.