×
Janoušek, Jan; Melichar, Bořivoj

On regular tree languages and deterministic pushdown automata. (English) Zbl 1186.68260

Acta Inf. 46, No. 7, 533-547 (2009).
Summary: The theory of formal string languages and of formal tree languages are both important parts of the theory of formal languages. Regular tree languages are recognized by finite tree automata. Trees in their postfix notation can be seen as strings. This paper presents a simple transformation from any given (bottom-up) finite tree automaton recognizing a regular tree language to a deterministic pushdown automaton accepting the same tree language in postfix notation. The resulting deterministic pushdown automaton can be implemented easily by an existing parser generator because it is constructed for an \(LR(0)\) grammar, and its size directly corresponds to the size of the deterministic finite tree automaton. The class of regular tree languages in postfix notation is a proper subclass of deterministic context-free string languages. Moreover, the class of tree languages which are in their postfix notation deterministic context-free string languages is a proper superclass of the class of regular tree languages.

Cited in 5 Documents

MSC:

68Q45 Formal languages and automata

Keywords:

string languages; finite tree automata

Software:

YakYak; YACC; Bison
PDF BibTeX XML Cite
\textit{J. Janoušek} and \textit{B. Melichar}, Acta Inf. 46, No. 7, 533--547 (2009; Zbl 1186.68260)
Full Text: DOI

References:

[1] Aho A.V., Ullman J.D.: The Theory of Parsing, Translation and Compiling, vol. 1: Parsing, vol. 2: Compiling. Prentice Hall, New York (1972) · Zbl 0264.68032
[2] Aho A.V., Sethi R., Ullman J.D.: Compilers: Principles, Techniques, and Tools. Addison Wesley, Reading, Mass (1986) · Zbl 1155.68020
[3] Alblas, H., Melichar, B. (eds): Attribute Grammars, Applications and Systems. LNCS 545. Springer, Berlin (1991) · Zbl 0875.00087
[4] Alur, R.: Marrying words and trees. In: 26th ACM symposium on principles of database systems, pp. 233–242. ACM, New York (2007) · Zbl 1167.68379
[5] Alur, R., Madhusudan, P.: Visibly pushdown languages. In: 36th ACM symposium on theory of computing, pp. 202–211. ACM, New York (2004) · Zbl 1192.68396
[6] Arbology www pages: Available on: http://www.arbology.org . Aug (2009)
[7] Aycock J., Horspool N., Janoušek J., Melichar B.: Even faster generalized LR parsing. Acta Inform. 37(9), 633–651 (2001) · Zbl 0973.68107
[8] Bison-GNU parser generator: Available on: http://www.gnu.org/software/bison/ . May (2008)
[9] Chase, D.: An improvement to bottom up tree pattern matching. In: Proceedings of 14th annual ACM symposium on principles of programming languages, pp. 168–177 (1987)
[10] Cleophas, L.: Tree algorithms. Two taxonomies and a toolkit. Ph.D. thesis, Technische Universiteit Eindhoven, Eindhoven (2008)
[11] Comon, H., Dauchet, M., Gilleron, R., Löding, C., Jacquemard, F., Lugiez, D., Tison, S., Tommasi, M.: Tree Automata Techniques and Applications. Available on: http://www.grappa.univ-lille3.fr/tata (2007). Release 12 Oct 2007
[12] Crochemore, M., Hancart, Ch.: Automata for matching patterns. In: Linear Modeling: Backgroung and Application. Handbook of Formal Languages, vol. 2, pp. 399–462. Springer, Berlin, Heidelberg (1997)
[13] Crochemore M., Rytter W.: Jewels of Stringology. World Scientific, New Jersey (1994) · Zbl 1078.68151
[14] Deransart, P., Jourdan, M. (eds): Attribute Grammars and Their Applications. LNCS 461. Springer, Berlin (1990) · Zbl 0741.68007
[15] Engelfriet, J.: Tree Automata and Tree Grammars. Lecture Notes. DAIMI FN-IO, University of Aarhus, Denmark (1975)
[16] Ferdinand Ch., Seidl H., Wilhelm R.: Tree automata for code selection. Acta Inform. 31(8), 741–760 (1994) · Zbl 0820.68031
[17] Fleuri, T., Janoušek, J., Melichar, B.: Subtree matching by deterministic pushdown automata. In: Proceedings of WAPL’09 Conference, Mragowo (2009)
[18] Fraser Ch.W., Hanson D.A., Proebsting T.A.: Engineering a simple, efficient code generator generator. ACM Lett. Program. Lang. Sys. 1, 3, 213–226 (1992)
[19] Fraser Ch.W., Henry R.R., Proebsting T.A.: BURG: fast optimal instruction selection and tree parsing. ACM SIGPLAN Notices 27, 68–76 (1992)
[20] Gecseg F.: Tree Automata. Akademiai Kiado, Budapest (1984)
[21] Gecseg, F., Steinby, M.: Tree languages. In: Beyond Words. Handbook of Formal Languages, vol. 3, pp. 1–68. Springer, Berlin, Heidelberg (1997)
[22] Glanville, R.S., Graham, S.L.: A new approach to compiler code generation. In: Proceedings of 5th ACM Symposium on Principles of Programming Languages, pp. 231–240 (1978)
[23] Hemerik C., Katoen J.P.: Bottom-up tree acceptors. Sci. Comput. Program. 13(1), 51–72 (1989) · Zbl 0687.68044
[24] Hoffmann C.M., O’Donnell M.J.: Pattern matching in trees. J. ACM 29(1), 68–95 (1982) · Zbl 0477.68067
[25] Hopcroft J.E., Motwani R., Ullman J.D.: Introduction to Automata Theory, Languages, and Computation. 2nd edn. Addison-Wesley, New York (2001) · Zbl 0980.68066
[26] Janoušek, J.: String suffix automata and subtree pushdown automata. In: Proceedings of the Prague Stringology Conference 2009, pp. 160–172. Czech Technical University in Prague, Prague (2009)
[27] Janoušek, J., Melichar, B.: Subtree and tree pattern pushdown automata for trees in prefix notation. Submitted for publication (2009)
[28] Johnson, S.: Yacc-yet another compiler compiler. Tech. Rep. TR 32, AT & T, Bell Laboratories, New Jersey (1975)
[29] Kamimura T., Slutzki G.: Parallel and two-way automata on directed ordered acyclic graphs. Inform. Control 49(1), 10–51 (1981) · Zbl 0482.68051
[30] Klarlund, N., Damgaard, N., Schwartzbach, M.I.: YakYak: parsing with logical side constraints. In: Developments in Language Theory, Foundations, Applications, and Perspectives, pp. 286–301. World Scientific, New Jersey (2000) · Zbl 0996.68076
[31] Kron, H.: Tree templates and subtree transformational grammars. Ph.D. thesis, University of California, Santa Cruz (1975)
[32] London Stringology Days 2009 Conference presentations: Available on: http://www.dcs.kcl.ac.uk/events/LSD&LAW09/ (2009). King’s College London, Feb 2009
[33] Madhavan M., Shankar P., Siddhartha R., Ramakrishna U.: Extending Graham–Glanville techniques for optimal code generation. ACM Trans. Program. Lang. Sys. 22(6), 973–1001 (2000) · Zbl 05459304
[34] Melichar, B., Holub, J., Polcar, J.: Text Searching Algorithms. Available on: http://stringology.org/athens/ (2005). Release Nov 2005
[35] Melichar, B., Janoušek, J.: Repeats in Trees by Subtree and Tree Pattern Pushdown Automata. Draft (2009)
[36] Shankar P., Gantait A., Yuvaraj A., Madhavan M.: A new algorithm for linear regular tree pattern matching. Theor. Comput. Sci. 242(1–2), 125–142 (2000) · Zbl 0944.68096
[37] Sikkel, K., Salomaa, A. (eds.): Word, language, grammar. In: Handbook of Formal Languages, vol. 1. Springer, Berlin, Heidelberg (1997)
[38] Sikkel K., Salomaa A. (eds): Handbook of Formal Languages. Springer, Berlin, Heidelberg (1997b) · Zbl 0866.68057
[39] van Best, J.P.: Tree-walking automata and monadic second order logic. M.Sc. thesis, Leiden University (1998)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.