Top

Published in:

2017 | OriginalPaper | Chapter

Copyful Streaming String Transducers

Authors : Emmanuel Filiot, Pierre-Alain Reynier

Published in: Reachability Problems

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Copyless streaming string transducers (copyless SST) have been introduced by R. Alur and P. Černý in 2010 as a one-way deterministic automata model to define transductions of finite strings. Copyless SST extend deterministic finite state automata with a set of variables in which to store intermediate output strings, and those variables can be combined and updated all along the run, in a linear manner, i.e., no variable content can be copied on transitions. It is known that copyless SST capture exactly the class of MSO-definable string-to-string transductions, and are as expressive as deterministic two-way transducers. They enjoy good algorithmic properties. Most notably, they have decidable equivalence problem (in PSpace).

On the other hand, HDT0L systems have been introduced for a while, the most prominent result being the decidability of the equivalence problem. In this paper, we propose a semantics of HDT0L systems in terms of transductions, and use it to study the class of deterministic copyful SST. Our contributions are as follows:

(i)

HDT0L systems and total deterministic copyful SST have the same expressive power,

(ii)

the equivalence problem for deterministic copyful SST and the equivalence problem for HDT0L systems are inter-reducible, in linear time. As a consequence, equivalence of deterministic SST is decidable,

(iii)

the functionality of non-deterministic copyful SST is decidable,

(iv)

determining whether a deterministic copyful SST can be transformed into an equivalent deterministic copyless SST is decidable in polynomial time.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter An Abstract Machine for Asynchronous Programs with Closures and Priority Queues

next chapter Model Checking CTL over Restricted Classes of Automatic Structures

Alur, A., Černý, P.: Streaming transducers for algorithmic verification of single-pass list-processing programs. In: POPL, pp. 599–610 (2011)

Alur, R., Černý, P.: Expressiveness of streaming string transducers. In: FSTTCS, vol. 8, pp. 1–12 (2010)

Alur, R., D’Antoni, L.: Streaming tree transducers. CoRR, abs/1104.2599 (2011)

Alur, R., D’Antoni, L.: Streaming tree transducers. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) ICALP 2012. LNCS, vol. 7392, pp. 42–53. Springer, Heidelberg (2012). doi:10.1007/978-3-642-31585-5_8 CrossRef

Alur, R., D’Antoni, L., Deshmukh, J.V., Raghothaman, M., Yuan, Y.: Regular functions and cost register automata. In: 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, pp. 13–22. IEEE Computer Society (2013)

Alur, R., Deshmukh, J.V.: Nondeterministic streaming string transducers. In: Aceto, L., Henzinger, M., Sgall, J. (eds.) ICALP 2011. LNCS, vol. 6756, pp. 1–20. Springer, Heidelberg (2011). doi:10.1007/978-3-642-22012-8_1 CrossRef

Alur, R., Filiot, E., Trivedi, A.: Regular transformations of infinite strings. In: LICS, pp. 65–74. IEEE (2012)

Benedikt, M., Duff, T., Sharad, A., Worrell, J.: Polynomial automata: zeroness and applications. In: Proceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2017. ACM (2017, to appear)

Culik, K., Karhumäki, J.: The equivalence of finite valued transducers (on HDT0L languages) is decidable. Theor. Comput. Sci. 47(3), 71–84 (1986)MathSciNetCrossRefMATH

10.

Dartois, L., Filiot, E., Reynier, P.-A., Talbot, J.-M.: Two-way visibly pushdown automata and transducers. In: Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2016, pp. 217–226. ACM (2016)

11.

Dartois, L., Jecker, I., Reynier, P.-A.: Aperiodic string transducers. In: Brlek, S., Reutenauer, C. (eds.) DLT 2016. LNCS, vol. 9840, pp. 125–137. Springer, Heidelberg (2016). doi:10.1007/978-3-662-53132-7_11 CrossRef

12.

Engelfriet, J., Hoogeboom, H.J.: MSO definable string transductions and two-way finite-state transducers. ACM Trans. Comput. Logic 2, 216–254 (2001)MathSciNetCrossRefMATH

13.

Engelfriet, J., Maneth, S.: Macro tree transducers, attribute grammars, and MSO definable tree translations. Inf. Comput. 154(1), 34–91 (1999)MathSciNetCrossRefMATH

14.

Engelfriet, J., Maneth, S.: The equivalence problem for deterministic MSO tree transducers is decidable. Inf. Process. Lett. 100(5), 206–212 (2006)MathSciNetCrossRefMATH

15.

Filiot, E., Krishna, S.N., Trivedi, A.: First-order definable string transformations. In: 34th International Conference on Foundation of Software Technology and Theoretical Computer Science, FSTTCS 2014. LIPIcs, vol. 29, pp. 147–159. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2014)

16.

Filiot, E., Reynier, P.-A.: Transducers, logic and algebra for functions of finite words. SIGLOG News 3(3), 4–19 (2016)

17.

Griffiths, T.V.: The unsolvability of the equivalence problem for lambda-free nondeterministic generalized machines. J. ACM 15(3), 409–413 (1968)CrossRefMATH

18.

Honkala, J.: A short solution for the HDT0L sequence equivalence problem. Theor. Comput. Sci. 244(1–2), 267–270 (2000)MathSciNetCrossRefMATH

19.

Lindenmayer, A.: Mathematical models for cellular interaction in development. J. Theoret. Biol. 18, 280–315 (1968)CrossRef

20.

Mandel, A., Simon, I.: On finite semigroups of matrices. Theor. Comput. Sci. 5(2), 101–111 (1977)MathSciNetCrossRefMATH

21.

Seidl, H., Maneth, S., Kemper, G.: Equivalence of deterministic top-down tree-to-string transducers is decidable. In: IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pp. 943–962. IEEE Computer Society (2015)

Title: Copyful Streaming String Transducers
Authors: Emmanuel Filiot
Pierre-Alain Reynier
Publisher: Springer International Publishing
Book: Reachability Problems
Print ISBN: 978-3-319-67088-1

Electronic ISBN: 978-3-319-67089-8

Copyright Year: 2017
DOI: https://doi.org/10.1007/978-3-319-67089-8_6

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner