[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.1145/2933575.2935315acmconferencesArticle/Chapter ViewAbstractPublication PageslicsConference Proceedingsconference-collections
research-article

Two-Way Visibly Pushdown Automata and Transducers

Published: 05 July 2016 Publication History

Abstract

Automata-logic connections are pillars of the theory of regular languages. Such connections are harder to obtain for transducers, but important results have been obtained recently for word-to-word transformations, showing that the three following models are equivalent: deterministic two-way transducers, monadic second-order (MSO) transducers, and deterministic one-way automata equipped with a finite number of registers. Nested words are words with a nesting structure, allowing to model unranked trees as their depth-first-search linearisations. In this paper, we consider transformations from nested words to words, allowing in particular to produce unranked trees if output words have a nesting structure. The model of visibly pushdown transducers allows to describe such transformations, and we propose a simple deterministic extension of this model with two-way moves that has the following properties: i) it is a simple computational model, that naturally has a good evaluation complexity; ii) it is expressive: it subsumes nested word-to-word MSO transducers, and the exact expressiveness of MSO transducers is recovered using a simple syntactic restriction; iii) it has good algorithmic/closure properties: the model is closed under composition with a unambiguous one-way letter-to-letter transducer which gives closure under regular look-around, and has a decidable equivalence problem.

References

[1]
R. Alur. Nested words, 2016. URL https://www.cis.upenn.edu/~alur/nw.html.
[2]
R. Alur and P. Černý. Expressiveness of streaming string transducers. In FSTTCS, volume 8, pages 1--12, 2010.
[3]
R. Alur and P. Černý. Streaming transducers for algorithmic verification of single-pass list-processing programs. In POPL, pages 599--610, 2011.
[4]
R. Alur and L. D'Antoni. Streaming tree transducers. In ICALP (2), volume 7392 of LNCS, pages 42--53. Springer, 2012.
[5]
R. Alur and P. Madhusudan. Adding nesting structure to words. J. ACM, 56(3), 2009.
[6]
R. Alur, E. Filiot, and A. Trivedi. Regular transformations of infinite strings. In LICS, pages 65--74, 2012.
[7]
R. Bloem and J. Engelfriet. A comparison of tree transductions defined by monadic second order logic and by attribute grammars. J. Comput. Syst. Sci., 61(1):1--50, 2000.
[8]
M. Bojanczyk. Transducers with origin information. In ICALP, volume 8573 of LNCS, pages 26--37. Springer, 2014.
[9]
M. Chytil and V. Jákl. Serial composition of 2-way finite-state transducers and simple programs on strings. In ICALP, volume 52 of LNCS, pages 135--147. Springer, 1977.
[10]
H. Comon-Lundh, M. Dauchet, R. Gilleron, C. Löding, F. Jacquemard, D. Lugiez, S. Tison, and M. Tommasi. Tree Automata Techniques and Applications. online, Nov. 2007. URL http://www.grappa.univ-lille3.fr/tata/.
[11]
B. Courcelle. Monadic second-order definable graph transductions: a survey. Theoretical Computer Science, 126(1):53--75, 1994.
[12]
B. Courcelle and J. Engelfriet. Book: Graph structure and monadic second-order logic. A language-theoretic approach. Bulletin of the EATCS, 108: 179, 2012.
[13]
K. Culik and J. Karhumaki. The equivalence problem for single-valued two-way transducers (on NPDT0L languages) is decidable. SIAM J. on Computing, 16(2):221--230, 1987.
[14]
J. Engelfriet and H. J. Hoogeboom. MSO definable string transductions and two-way finite-state transducers. ACM Transactions on Computational Logic, 2(2):216--254, 2001.
[15]
J. Engelfriet and S. Maneth. Macro tree transducers, attribute grammars, and mso definable tree translations. Information and Computation, 154 (1):34--91, 1999.
[16]
J. Engelfriet and S. Maneth. Macro tree translations of linear size increase are MSO definable. SIAM J. of Computing, 32(4):950--1006, 2003.
[17]
E. Filiot. Logic-automata connections for transformations. In ICLA, volume 8923 of LNCS, pages 30--57. Springer, 2015.
[18]
E. Filiot, J.-F. Raskin, P.-A. Reynier, F. Servais, and J.-M. Talbot. Properties of visibly pushdown transducers. In MFCS, volume 6281 of LNCS, pages 355--367. Springer, 2010.
[19]
E. Filiot, O. Gauwin, P.-A. Reynier, and F. Servais. Streamability of nested word transductions. In FSTTCS, volume 13 of LIPIcs, pages 312--324, 2011.
[20]
E. Filiot, O. Gauwin, P.-A. Reynier, and F. Servais. From two-way to one-way finite state transducers. In LICS, pages 468--477. IEEE, 2013.
[21]
O. Gauwin, J. Niehren, and S. Tison. Queries on XML streams with bounded delay and concurrency. Information and Computation, 209(3): 409--442, 2011.
[22]
E. Gurari. The equivalence problem for deterministic two-way sequential transducers is decidable. SIAM J. on Computing, 11, 1982.
[23]
J. E. Hopcroft and J. D. Ullman. An approach to a unified theory of automata. BELLTJ: The Bell System Technical Journal, 46:1793--1829, 1967.
[24]
V. Kumar, P. Madhusudan, and M. Viswanathan. Visibly pushdown automata for streaming XML. In WWW, pages 1053--1062. ACM, 2007.
[25]
P. Madhusudan and M. Viswanathan. Query automata for nested words. In MFCS, volume 5734 of LNCS, pages 561--573. Springer, 2009.
[26]
F. Neven and T. Schwentick. Query automata over finite trees. Theoretical Computer Science, 275, 2002.
[27]
J. Niehren, L. Planque, J.-M. Talbot, and S. Tison. N-ary queries by tree automata. In DBLP, volume 3774 of LNCS, pages 217--231. Springer, 2005.
[28]
J. Pécuchet. Automates boustrophedon, semi-groupe de Birget et monoide inversif libre. RAIRO - ITA, 19(1):71--100, 1985.
[29]
F. Picalausa, F. Servais, and E. Zimányi. XEvolve: an XML schema evolution framework. In SAC, pages 1645--1650. ACM, 2011.
[30]
J. Raskin and F. Servais. Visibly pushdown transducers. In ICALP, volume 5126 of LNCS, pages 386--397. Springer, 2008. 1007/978-3-540-70583-3 32. URL http://dx.doi.org/10.1007/978-3-540-70583-3_32.
[31]
L. Segoufin and C. Sirangelo. Constant-memory validation of streaming XML documents against DTDs. In ICDT, volume 4353 of LNCS, pages 299--313. Springer, 2007.
[32]
H. Seidl, S. Maneth, and G. Kemper. Equivalence of deterministic top-down tree-to-string transducers is decidable. In FOCS, pages 943--962. IEEE, 2015.
[33]
J. C. Shepherdson. The reduction of two-way automata to one-way automata. IBM Journal of Research and Development, 3(2):198--200, 1959.
[34]
W. Thomas. Languages, automata and logic. In A. Salomaa and G. Rozenberg, editors, Handbook of Formal Languages, volume 3, Beyond Words. Springer, Berlin, 1997.

Cited By

View all

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences
LICS '16: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science
July 2016
901 pages
ISBN:9781450343916
DOI:10.1145/2933575
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 05 July 2016

Permissions

Request permissions for this article.

Check for updates

Author Tags

  1. Logic
  2. Pushdown automata
  3. Transductions

Qualifiers

  • Research-article
  • Research
  • Refereed limited

Funding Sources

Conference

LICS '16
Sponsor:

Acceptance Rates

Overall Acceptance Rate 215 of 622 submissions, 35%

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)4
  • Downloads (Last 6 weeks)1
Reflects downloads up to 10 Dec 2024

Other Metrics

Citations

Cited By

View all

View Options

Login options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media