Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Acta Informatica
Published in: Acta Informatica 5/2014

01-08-2014 | Original Article

Forward and backward application of symbolic tree transducers

Authors: Zoltán Fülöp, Heiko Vogler

Published in: Acta Informatica | Issue 5/2014

Log in

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

search-config
loading …

Abstract

We consider symbolic tree automata (sta) and symbolic regular tree grammars and their corresponding classes of tree languages: s-recognizable tree languages and s-regular tree languages. We prove that the following three classes are equal: the class of s-recognizable tree languages, the class of s-regular tree languages, and the class of images of classical recognizable tree languages under tree relabelings. Moreover, the sta and the recently introduced variable tree automata are incomparable with respect to their recognition power. Also, we consider symbolic tree transducers (stt) and prove the following theorems. The syntactic composition of two stt computes the composition of the tree transformations computed by each stt, provided that (1) the first one is deterministic or the second one is linear and (2) the first one is total or the second one is nondeleting. Backward application of an stt to any s-recognizable tree language yields an s-recognizable tree language. There is a linear stt of which the range is not an s-recognizable tree language. Forward application of simple and linear stt preserves s-recognizability. A restricted version of both the type checking problem of simple and linear stt, and the inverse type checking problem of arbitrary stt is decidable. Since we deal with trees over infinite alphabets, we require appropriate conditions on sta and stt such that all the proofs are constructive.
previous article General quantitative specification theories with modal transition systems
next article Controlled finite automata

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 "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

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
Footnotes
1
We mean that for every \(\varphi \in \Phi \) there is an explicit algorithm which, for every \( a\in U\) as input, computes \(\varphi (a)\).
 
Literature
1.
Alon, N., Milo, T., Neven, F., Suciu, D., Vianu, V.: XML with data values: typechecking revisited. J. Comput. Syst. Sci. 66(4), 688–727 (2003)
2.
Baker, B.S.: Composition of top-down and bottom-up tree transductions. Inform. Control 41(2), 186–213 (1979)CrossRefMATH
3.
4.
Brambilla, M., Ceri, S., Comai, S., Fraternali, P., Manolescu, I.: Specification and design of workflow-driven hypertexts. J. Web Eng. 2, 163–182 (2003)
5.
Bouajjani, A., Habermehl, P., Jurski, Y., Sighireanu, M.: Rewriting systems with data. In Proceedings of 16th International Symposium on Fundamentals of Computation Theory (FCT’07), volume 4639 of Lecture Notes in Comput. Sci., pp. 1–22. Springer (2007)
6.
Bouajjani, A., Habermehl, P., Mayr, R.: Automatic verification of recursive procedures with one integer parameter. Theoret. Comput. Sci. 295, 85–106 (2003)CrossRefMATHMathSciNet
7.
Brüggemann-Klein, A., Murata, M., Wood, D.: Regular tree and regular hedge languages over unranked alphabets: Version 1, April 2001. Technical Report HKUST-TCSC-2001-0. The Hongkong University of, Science and Technology (2001)
8.
9.
10.
11.
David, C., Libkin, L., Tan, T.: Efficient reasoning about trees via integer linear programming. ACM Trans. Database Syst. 37(3), 19 (2012)CrossRef
12.
13.
Engelfriet, J., Maneth, S.: A comparison of pebble tree transducers with macro tree transducers. Acta Inform. 39(9), 613–698 (2003)CrossRefMATHMathSciNet
14.
15.
Fülöp, Z., Vogler, H.: Syntax-Directed Semantics—Formal Models Based on Tree Transducers. Monogr. Theoret. Comput. Sci. EATCS Ser. Springer (1998)
16.
Grumberg, O., Kupferman, O., Sheinvald, S.: Variable automata over infinite alphabets. In: Martin-Vide, C., Dediu, A.-H., Fernau, H. (eds.) 4th International Conference on Languages and Automata (LATA 2010) volume 6031 Lecture Notes in Computer Science, pp. 561–572. Springer, NY (2010)
17.
Gécseg, F., Steinby, M.: Tree Automata. Akadémiai Kiadó, Budapest (1984)MATH
18.
Gécseg, F., Steinby, M.: Tree languages. In: Rozenberg, G., Salomaa, A. (eds.) Handbook of Formal Languages, volume 3, chapter 1, pp. 1–68. Springer, Berlin (1997)CrossRef
19.
Kaminski, M., Tan, T.: Tree automata over infinite alphabets. In: Avron, A., et al. (eds.) Trakhtenbrot/Festschrift volume 4800 of Lecture Notes in Conputer Science, pp. 386–423. Springer, Berlin (2008)
20.
Maneth, S., Berlea, A., Perst, T., Seidl, H.: XML type checking with macro tree transducers. In: Proceedings of 24th ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS 2005), pp. 283–294. ACM Press (2005)
21.
Mens, I.-E., Rahonis, G.: Variable tree automata over infinite ranked alphabets. In: Winkler, F. (ed.) 4th International Conference on Algebraic Informatics (CAI 2011), volume 6742 of Lecture Notes in Compter Science, pp. 247–260. Springer (2011)
22.
23.
Murata, M.: Forest-regular languages and tree-regular languages. Unpublished notes (1995)
24.
25.
Tan, T.: An automata model for trees with ordered data values. In: Proceedings of 27th Annual IEEE/ACM Symposium on Logic in Computer Science Pages (LICS), pp. 586–595 (2012)
26.
Thatcher, J.W.: Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. J. Comput. Syst. Sci. 1(4), 317–322 (1967)CrossRefMATHMathSciNet
27.
28.
Veanes, M., Bjorner, N.: Foundations of finite symbolic tree transducers. Bull. EATCS 105, 141–173 (2011)MATHMathSciNet
29.
Veanes, M., Bjorner, N.: Symbolic tree transducers. In: Proceedings of Perspectives of System Informatics (PSI 11), volume 7162 of LNCS, pp. 371–387. Springer (2011)
30.
Veanes, M., Hooimeijer, P., Livshits, B., Molnar, D., Bjorner, N.: Symbolic finite transducers: algorithms and applications. In: Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’12), pp. 137–150. ACM SIGPLAN (2012)
Metadata
Title
Forward and backward application of symbolic tree transducers
Authors
Zoltán Fülöp
Heiko Vogler
Publication date
01-08-2014
Publisher
Springer Berlin Heidelberg
Published in
Acta Informatica / Issue 5/2014
Print ISSN: 0001-5903
Electronic ISSN: 1432-0525
DOI
https://doi.org/10.1007/s00236-014-0197-7

Premium Partner

    Image Credits