Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/15354Full metadata record
| DC Field | Value | Language |
|---|---|---|
| dc.contributor.author | Filiot, Emmanuel | - |
| dc.contributor.author | Gauwin, Olivier | - |
| dc.contributor.author | Reynier, Pierre-Alain | - |
| dc.contributor.author | SERVAIS, Frederic | - |
| dc.date.accessioned | 2013-07-25T14:16:22Z | - |
| dc.date.available | 2013-07-25T14:16:22Z | - |
| dc.date.issued | 2013 | - |
| dc.identifier.citation | 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science, p. 468-477 | - |
| dc.identifier.isbn | 9781479904136 | - |
| dc.identifier.uri | http://hdl.handle.net/1942/15354 | - |
| dc.description.abstract | Any 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.iso | en | - |
| dc.publisher | IEEE | - |
| dc.subject.other | Formal Languages, Transducer, MSO | - |
| dc.title | From Two-Way to One-Way Finite State Transducers | - |
| dc.type | Proceedings Paper | - |
| local.bibliographicCitation.conferencedate | June 25–28, 2013 | - |
| local.bibliographicCitation.conferencename | 28th Annual ACM/IEEE Symposium on Logic in Computer Science | - |
| local.bibliographicCitation.conferenceplace | New Orleans, USA | - |
| dc.identifier.epage | 477 | - |
| dc.identifier.spage | 468 | - |
| local.bibliographicCitation.jcat | C2 | - |
| 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.refereed | Refereed | - |
| local.type.specified | Proceedings Paper | - |
| dc.identifier.doi | 10.1109/LICS.2013.53 | - |
| local.bibliographicCitation.btitle | 2013 28th Annual ACM/IEEE Symposium on Logic in Computer Science | - |
| item.accessRights | Open Access | - |
| item.contributor | Filiot, Emmanuel | - |
| item.contributor | Gauwin, Olivier | - |
| item.contributor | Reynier, Pierre-Alain | - |
| item.contributor | SERVAIS, Frederic | - |
| item.fulltext | With Fulltext | - |
| item.fullcitation | Filiot, 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 | Size | Format | |
|---|---|---|---|---|
| 5020a468.pdf | Published version | 285.39 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
18
checked on Sep 2, 2020
WEB OF SCIENCETM
Citations
20
checked on Apr 16, 2024
Page view(s)
86
checked on Sep 7, 2022
Download(s)
216
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.