AP09_2.vp 1 Introduction Tree pattern matching is one of the fundamental prob- lems with many applications, and is often declared to be anal- ogous to the problem of string pattern matching [3, 5, 17]. String pattern matching is the problem of finding all occur- rences of string patterns and their positions in a given text. A model of computation for string pattern matching is the finite automaton [8]. One of the basic approaches used for string pattern matching is represented by finite automata which are constructed for string patterns, which means that the patterns are preprocessed. Given a text of size n, such finite automata typically perform the search phase in time linear to n (see [8, 9, 19] for a survey). Tree pattern matching is the problem of finding all occur- rences and their positions of matches of tree patterns in a subject tree. Although many tree pattern matching methods have been described [4, 5, 6, 10, 11, 13, 14, 16, 17, 18, 20, 21], most of them fail to provide a search phase in linear time (based on the size of the subject tree) or have huge memory requirements. This paper presents the first attempt to perform tree pat- tern matching by a unified and systematic approach using pushdown automata. We present the first, basic, non-deter- ministic model of a pushdown automaton performing tree pattern matching. The goal of this research is to provide a method for determinising the non-deterministic model of the proposed pushdown automaton, which will make linear time (based on the size of the subject tree) pattern match- ing possible. 2 Basic notions 2.1 Ranked alphabet, tree, prefix notation, tree pattern We define notions on trees similarly as they are defined in [1, 5, 7, 15, 17]. We denote the set of natural numbers by �. A ranked alpha- bet is a finite, non-empty set of symbols, each of which has a unique, non-negative arity (or rank). Given a ranked alphabet �, the arity of a symbol a �� is denoted Arity (a). The set of symbols of arity p is denoted by � p . Elements of arity 0, 1, 2, …, p are respectively called nullary, unary, binary, …, p-ary symbols. We assume that � contains at least one constant. In the examples we use numbers at the end of identifiers for a short declaration of symbols with arity. For instance, a2 is a short declaration of a binary symbol a. Based on the concepts of graph theory (see [1]), a labeled, ordered, ranked tree over a ranked alphabet � can be defined as follows: An ordered di- rected graph G is a pair (N, R), where N is a set of nodes and R is a set of linearly ordered lists of edges, such that each ele- ment of R is of the form (( , ), ( , ), , ( , ))f g f g f g n1 2 � , where f g g g Nn, , , ,1 2 � � , n � 0. This element would indicate that, for node f, there are n edges leaving f, the first entering node g1, the second entering node g2, and so forth. A sequence of nodes ( , , , )f f f n0 1 � , n � 1, is a path of length n from node f0 to node fn, if there is an edge which leaves node fi�1 and enters node fi for1 � �i n . A cycle is a path ( , , , )f f f n0 1 � , where f f n0 � . An ordered Directed Acyclic Graph (DAG) is an ordered directed graph that has no cycle. Labeling of an ordered graph G A R� ( , ) is a mapping of A into a set of labels. In the examples we use af for a short declaration of node f labeled by symbol a. A labeled, ordered, ranked tree t over a ranked alphabet � is an ordered DAG t N R� ( , ) with a special node called the root, such that (1) r has in-degree 0, (2) all other nodes of t have in-degree 1, (3) there is just one path from root r to every f N� , where f r� , (4) every node f N� is labeled by a symbol a �� and out-de- gree of af is Arity (a), (5) nodes labeled by nullary symbols are called leaves. The prefix notation pref (t) of a labeled, ordered, ranked tree t is obtained by applying the following Step recursively, begin- ning at the root of t: 28 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 49 No. 2–3/2009 On Tree Pattern Matching by Pushdown Automata T. Flouri Tree pattern matching is an important operation in Computer Science on which a number of tasks such as mechanical theorem proving, term-rewriting, symbolic computation and non-procedural programming languages are based on. Work has begun on a systematic ap- proach to the construction of tree pattern matchers by deterministic pushdown automata which read subject trees in prefix notation. The method is analogous to the construction of string pattern matchers: for given patterns, a non-deterministic pushdown automaton is created and then it is determinised. In this first paper, we present the proposed non-deterministic pushdown automaton which will serve as a basis for the determinisation process, and prove its correctness. Keywords: tree, tree pattern, pushdown automaton, tree pattern matching. Step: Let this application of Step to be node af. If af is a leaf, list af and halt. If af is not a leaf, let its direct descendants be a a af f f n1 2 , , ,� . Then list af and subsequently apply Step to a a af f f n1 2 , , ,� in that order. We note that in many papers on the theory of tree lan- guages, such as [5, 7, 15, 17], labeled ordered ranked trees are defined with the use of ordered ranked ground terms. Ground terms can be regarded as labeled, ordered, ranked trees in prefix notation. Therefore, the notions ground term, tree and tree in prefix notation are used interchangeably in these papers. Example 1. Consider a ranked alphabet � � { , , }a a a2 1 0 . Con- sider a tree t1 over � t a a a a a a a R1 1 2 3 4 5 6 72 2 0 1 0 1 0� ({ , , , , , , }, ), where R is a set of the following ordered sequences of pairs: (( , ),( , ))a a a a2 2 2 11 2 1 6 , (( , ),( , ))a a a a2 0 2 12 3 2 4 , (( , ))a a1 04 5 , (( , ))a a1 06 7 . The prefix notation of tree t1 is pref t a a a a a a a( )1 2 2 0 1 0 1 0� . Trees can also be represented graphically and tree t1 is illustrated in Fig. 1. The height of a tree t, denoted by Height (t), is defined as the maximal length of a path from the root of t to a leaf of t. To define a tree pattern, we use a special nullary symbol S, where S ��, which serves as a placeholder for any subtree. A tree pattern is defined as a labeled, ordered, ranked tree over ranked alphabet � { }S . By analogy, a tree pattern in prefix notation is defined as a labeled, ordered, ranked tree over ranked alphabet � { }S in prefix notation. A pattern p with k � 0 occurrences of the symbol S matches a tree t at node n if there exist subtrees t t tk1 2, , ,� (not necessar- ily the same) of the tree t, such that the tree p , obtained from p by substituting the subtree ti for the i-th occurrence of S in p, i k� 1 2, , ,� , is equal to the subtree of t rooted at n. Example 2. Consider a tree t a a a a a a a R1 2 2 0 1 0 1 01 2 3 4 5 6 7� ({ , , , , , , }, ) from Example 1, which is illustrated in Fig. 1. Consider a tree pattern p1 over � { }S , p a S a S R1 8 9 10 112 1� ({ , , , }, ) , where is a set of the following ordered sequences of pairs: (( , ),( ))a S a a2 2 18 9 8 10 , (( , ))a S19 11 . The prefix notaion of tree pattern p1 is pref p a S a S( )1 2 1� . The tree pattern p1 is illustrated in Fig. 2 and has two occurrences in tree t1, matching at nodes a21 and a22 of t1. 2.2 Alphabet, language, context-free grammar, pushdown automaton Let an alphabet be a finite, nonempty set of symbols. A language over an alphabet � is a set of strings over �. The symbol �* denotes the set of all strings over �, including the empty string, which is denoted by �. Set � � is defined as � �� � * �{�}. Similarly for string x �� *, the symbol xm, m � 0 denotes the m-fold concatenation of x with x0 � �. Set x* is defined as x x mm* { : }� � 0 and x x� � *�{ } { : }� � �x mm 1 . A context-free grammar (CFG) is a 4-tuple G N T P S� ( , , , ), where N and T are finite, disjoint sets of nonterminal and ter- minal symbols, respectively. P is a finite set of rules A � �, where A N� , � � ( )*N T . S N� is the start symbol. A CFG G N T P S� ( , , , ) is said to be in Reversed Greibach Normal Form, if each rule from P is of the form A a� � , where a T� and � � N *. The relation is called derivation, if � � ���A , A N� , and � � �, , ( )*� N T , then rule A B� is in P. Symbols �, and * are used for the transitive, and the transitive and re- flexive closure of , respectively. A rightmost derivation rm is a relation � ��Ax x , where x T� *. The relation A A A � � � is called recursion. Right recursion is a A A � � . Hidden-left recursion is a A B A � � �, where B� ��� . The language generated by a CFG G, denoted by L(G), is the set of strings L G w S w w T* *( ) { : , }� � . A derivation tree is a labeled, ordered tree representing a syntactic structure of a string w, generated by the grammar G. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 29 Acta Polytechnica Vol. 49 No. 2–3/2009 Fig. 1: Tree t1 from Example 1 and its prefix notation Fig. 2: Tree pattern from Example 2 and its prefix notation Its root is labeled by the start symbol S and its leaves are la- beled by terminal symbols or empty strings. Each interior node of the tree is labeled by a non-terminal symbol A, and the children of such a node are labeled, from left to right, by symbols from the right-hand side � of a rule A P� �� . A derivation S w * corresponds to a derivation tree whose leaves, if read from left to right, are labeled with the string w. A CFG G is unambiguous if each string w L G� ( ) has just one derivation tree in the CFG G. A context-free language is a language generated by a CFG. An (extended) non-deterministic pushdown automaton (non- -deterministic PDA) is a seven-tuple M Q G q Z F� ( , , , , , , )� � 0 0 , where Q is a finite set of states, � is an input alphabet, G is a pushdown store alphabet, � is a mapping from Q G� �( { }) *� � , into a set of finite subsets of Q G� *, q Q0 � is an initial state, Z G0 � is the initial content of the pushdown store, and F Q� is the set of final (accepting) states. The triplet ( , , ) * *q w x Q G� � �� denotes the configu- ration of a pushdown automaton. In this paper, the top of the pushdown store x is always on the left-hand side. The initial configuration of a pushdown automaton is a triplet ( , , )q w Z0 0 for the input string w �� *. The relation ( , , )q aw �� �M p w Q A G Q A G( , , ) ( ) ( ) * * * *�� � � � � � � is a transition of a pushdown automaton M, if ( , ) ( , , )p q a� � �� . The k-th power, transitive closure, and transitive and reflexive closure of the relation �M is denoted �M k , �M � , �M * , respec- tively. A pushdown automaton M is deterministic (deterministic PDA), if it holds: (1) � �( , , )q a � 1 for all q Q� , a A� { }� , � �G *. (2) If � �( , , )q a � �0, � �( , , )q a � �0 and � �� then � is not a pre- fix of � and � is not a prefix of �. (3) If � �( , , )q a � �0, � � �( , , )q � �0, then � is not a prefix of � and � is not a prefix of �. The class of languages accepted by non-deterministic PDAs is exactly the class of context-free languages. Languages accepted by deterministic PDAs are called deterministic con- text-free languages. There exist context-free languages which are not deterministic, that is, for which no deterministic PDA can be constructed. A pushdown automaton is input-driven if each of its push- down operations is determined only by the input symbol. 2.3 LR(0) parsing Given a string w, an LR(0) parser for a CFG G N T P S� ( , , , ) reads the string w from left to right without any backtracking and is implemented by a deterministic PDA. A string � is a via- ble prefix G if � is a prefix of ��, and S A x x rm rm * � �� is a rightmost derivation in G; the string � is called the handle. We use the term complete viable prefix to refer to �� in its entirety. During parsing, each content of the pushdown store corre- sponds to a viable prefix. The standard LR(0) parser performs two kinds of transitions: (a) When the contents of the pushdown store correspond to a viable prefix containing an incomplete handle, the parser performs a shift, which reads one symbol a and pushes a symbol corresponding to a onto the pushdown store. (b) When the contents of the pushdown store correspond to a viable prefix ending by the handle �, the parser performs a reduction by rule A � �. The reduction pops � symbols from the top of the pushdown store and pushes a symbol corresponding to A onto the pushdown store. A CFG G is LR(0) if the two conditions for G: (1) S Aw w rm rm * � �� , (2) S B x y rm rm * � �� , imply that � �Ay B x� , that is � �� , A B� , and x y� . If the CFG G is not an LR(0) grammar, then the PDA con- structed as an LR(0) parser contains conflicts, which means the next transition to be performed cannot be determined ac- cording to the contents of the pushdown store only. For CFGs without hidden-left and right recursions, the number of consecutive reductions between the shifts of two adjacent symbols cannot be greater than a constant, and therefore the LR(0) parser for such a grammar can be opti- mized by precomputing all its reductions. Then, the opti- mized resulting LR(0) parser reads one symbol on each of its transitions [2]. A language L accepted by a pushdown automaton M is de- fined in two distinct ways: (1) Accepting by final state: L M( ) � { : ( , , )x q x Z� 0 0 � M q x G q F * * *( , , ) }.� � �� � � � � �� (2) Accepting by empty pushdown store: L M x q x Z�( ) { :( , , )� 0 0 � M q x q Q * *( , , ) }.� � � � � �� 3 A Deterministic Pushdown Automaton accepting trees in prefix notation The prefix notation of a tree can be generated by a gram- mar G N T P S� ( , , , ), having rules P of the following form: (1)S a� 0 (2)S a S� 1 (3)S a SS� 2 … (n)S a Sn n � � � 1 1 30 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 49 No. 2–3/2009 Since the grammar is LR(0), belonging to the subclass of context-free grammars named as deterministic context free grammars, the generated language belongs to the class of de- terministic context-free languages and can be recognised by a de- terministic pushdown automaton. In this section we present the deterministic pushdown au- tomaton M S S� �({ }, , { }, , , , )0 0 0� � , accepting arbitrary trees in prefix notation by empty pushdown store. The transitions of the automaton are in the form �( , , ) ( , )( )0 0x S S Arity x� , for each x ��. Have in mind that S 0 � �. The automaton, which is input-driven, is depicted in Fig. 3. This particular automa- ton will be the basic building block for our non-deterministic automaton, which will serve as a pattern matcher. Theorem 1. The automaton presented in section 3 accepts valid trees in prefix no- tation by empty pushdown store. Proof. There are three possible types of input to be given to the automaton: (1) A valid input, which represents the prefix notation of a tree. (2) An invalid input, in which there exists a prefix that repre- sents a valid prefix notation of a tree. (3) An invalid input which is the prefix of the prefix notation of some (unknown) tree. To show that the first type of (valid) input is accepted by our automaton by empty pushdown store, we use strong induction. Let P(n) be a predicate defined over all integers n. Predi- cate P(i) is true, if trees of height i are accepted by the pre- sented deterministic PDA. We define the base case and the inductive step in the following manner: (1) Base case: P(0) is true. (2) Inductive case: P P P n P n( ), ( ), , ( ) ( )0 1 1� � Since the initial pushdown store symbol is symbol S, state- ment (1) is true, as the only trees of height (0) are trees with only one node x having arity 0. The transition to be taken is � �( , , ) ( , )0 0x S � , removing the initial symbol S from the push- down store. Each tree of depth n can be represented as a root x of arity k, where each of its children nodes can be subtrees of height at most n � 1. According to the inductive case assumption (2), each of the subtree can be accepted by the automaton by empty pushdown store, removing the initial pushdown store symbol S. Since the root appends k � 1 symbols S on the pushdown store, the k subtrees remove k symbols S from the pushdown store, leaving it empty. As a result, we have proven that our automaton accepts valid input (prefix notations of trees) by empty pushdown store. In the second case (invalid input, in which there exists such a prefix that represents a valid prefix notation of a tree), the pushdown store will be emptied at the moment the prefix which represents a valid prefix notation is read. In the third case, which is apparent from the first case, the pushdown store will not be emptied. We have proved that the automaton accepts only valid in- put (prefix notations of trees) by empty pushdown store. � Corollary 1. Processing an arbitrary tree with the automaton intro- duced in Section 3 results in one symbol being removed from the top of the pushdown store. 4 Searching Non-Deterministic Pushdown Automaton In this section we present the Searching Non-Determinis- tic Pushdown Automaton (SNPDA), performing tree pattern matching. The structure of an SNPDA accepting all occurrences of the tree pattern for a given tree in prefix notation is described by Algorithm 4. We note that the SNPDA accepts the matched patterns by final state. The SNPDA is loosely based on the searching non-deter- ministic finite automaton, which is used for pattern matching in strings, as described in [19]. It is constructed by extending the deterministic pushdown automaton presented in Sec- tion 3 with states and transitions corresponding to the given tree pattern. We start by constructing the deterministic pushdown au- tomaton M q G q S F� ( , , , , , , )0 0� � presented in Section 3, where � is defined as �( , , ) {( , )}( )q x S q S Arity x0 0� for each x ��, F � �0 and G S� { }. The prefix notation of the pattern is read from left to right; for each node x (except the special nullary symbol S) at position i (the position of the first node is 1) , the following steps are carried out: 1. Create a new state qi. 2. In case i � 1 do step 3, otherwise do step 4. 3. Define a new transition �( , , ) {( , )}( )q x S q Si i Arity x � �1 . 4. Append a new transition: � �( , , ) ( , , ) {( , )}( )q x S q x S q S Arity x0 0 1� . In case the nullary symbol S is found at position i, the fol- lowing steps are carried out: 1. Create a new state qi. 2. Define a symbol #j , where #j G� . 3. Add the new symbol #j to the pushdown store symbol set G: G G j� {# }. © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 31 Acta Polytechnica Vol. 49 No. 2–3/2009 Fig. 3: Deterministic tree automaton 4. Define a new transition � �( , , ) {( , # )}q S q Si j� �1 0 . 5. Define a new transition � � �( , , # ) {( , )}q qj i0 � . The last created state (state qn) is set as final (that is, F qn� { }). Examples of PDAs constructed by Algorithm 1 for various patterns are shown in Fig. 4–6. Theorem 2. The SNPDA constructed by Algorithm 1 finds all occurrences of the tree pattern in a subject tree by final state. Proof. We provide a sketch of the proof. A tree pattern, for which the SNPDA M Q G q S F� ( , , , , , , )� � 0 is constructed, has either the form p x x xn� 1 2� (form 1), where x1 �� and x Si � � { } for i � 1, or the form p S� (form 2). The automaton is non-deterministic at state q0, due to the transitions �( , , ) {( , ),( , )}( ) ( )q x S q S q SArity x Arity x0 1 0 11 1� in the case of form 1, or due to the transition � �( , , ) {( , #)}q S q S0 0� conflicting with all other transitions in the case of form 2. Because of this property, the SNPDA can follow more than one paths at each input symbol. It can either cycle through state q0 or move to state q1 and on to qn, in case the input sym- bols match the pattern. At the point of a nullary S symbol in the pattern, an �-tran- sition leading to state q0 is taken, replacing the top of the pushdown store (which is a symbol S) with S j# , where j is dis- tinct for each S in the tree pattern. Using this method, we sim- ulate a new pushdown store on the top of the current pushdown store. Symbol #j denotes the end of the new, simu- lated pushdown store. From Corollary 1, we know that read- ing a tree by cycling through state q0 removes 1 S symbol from the pushdown store. As a result, the top of the pushdown store will be #j, which indicates that a tree (required by the respec- tive symbol S in the tree pattern) has been processed. The #j-transition can now be taken to resume pattern matching at the point after the respective symbol S in the pattern. While reading a tree by cycling at state q0, a new pattern can be de- tected since the automaton is non-determinstic. � Note that the SNPDA in Fig. 6 is input-driven and thus it can be determinised in the same way as finite automata. The deterministic version is illustrated in Fig. 7. 32 © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ Acta Polytechnica Vol. 49 No. 2–3/2009 input : x x x xn� 1 2� – prefix notation of a tree over a ranked alphabet � output : M – a non-deterministic pushdown automaton 1 Q � �0 2 G S� { } 3 � � �0 4 for i � �0 to n do Q Q qi� { } 5 F qn� { } 6 foreach y �� do �( , , ) ( , )( )q y S q S Arity y0 0� 7 j � 0 8 for i � 1 to n do 9 if x Si � then 10 j j� � 1 11 G G j� {# } 12 � �( , , ) ( , # )q S q Si j� �1 0 13 � � �( , , # ) ( , )q qj i0 � 14 else 15 �( , , ) ( , )( )q x S q Si i i Arity x i � �1 16 end 17 end 18 M Q G q S F� ( , , , , , , )� � 0 Algorithm 1: Construction of a searching nondeterministic push- down automaton Fig. 4: Non-deterministic searching automaton pushdown auto- maton for tree pattern p a a Sa� 2 1 0 Fig. 5: Non-deterministic searching automaton pushdown auto- maton for tree pattern p a SSa Sa� 3 2 0 Fig. 6: Non-deterministic searching automaton pushdown auto- maton for tree pattern p a a a a� 2 1 0 0 Fig. 7: Deterministic searching automaton pushdown automaton for tree pattern p a a a a� 2 1 0 0 5 Conclusion and future work In this paper we have presented an innovative method of tree pattern matching by pushdown automata. We have intro- duced a non-deterministic model of the searching pushdown automaton, which correctly accepts all occurrences of a pat- tern in a given tree presented in its prefix notation. Our goal is to perform determinisation of this automaton, which will lead to linear time (to the size of the subject tree) searching of patterns, as in the case of string pattern match- ing by deterministic finite automata. Work on the deter- minisation of this automaton has already begun and the first results were presented at the London Stringology Days confer- ence held at King’s College, London [12]. Acknowledgements The research described in this paper was supervised by Prof. Bořivoj Melichar, DrSc. of FEE CTU in Prague and supported by the Czech Ministry of Education, Youth and Sports under research program MSM 6840770014, and by the Czech Science Foundation as project No. 201/09/0807. References [1] Aho, A. V., Ullman, J. D.: The Theory of Parsing, Transla- tion and Compiling. Vol. 1: Parsing, Vol. 2: Compiling, New York: Prentice–Hall, 1972. [2] Aycock, J., Horspool, N., Janoušek, J., Melichar, B.: Even Faster Generalized LR Parsing, In: Acta Informatica, Berlin: Springer, Vol. 37 (2001), No. 9, p. 633–651. [3] Bille, P.: Pattern Matching in Trees and Strings. PhD thesis, FIT University of Copenhagen, Copenhagen, 2008. [4] Chase, D.: An Improvement to Bottom up Tree Pattern Matching, In: Proc. 14th Ann. ACM Symp. on Principles of Programming Languages, 1987, p. 168–177. [5] Cleophas, L.: Tree Algorithms. Two Taxonomies and a Toolkit. PhD thesis, Technische Universiteit Eindhoven, Eindhoven, 2008. [6] Cole, R., Hariharan, R., Indyk, P.: Tree Pattern Match- ing and Subset Matching in Deterministic o(nlog3n) Time. In: Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms, 1999, p. 245–254. [7] 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, release October, 12th 2007, 2007. [8] Crochemore, M., Hancart, Ch.: Automata for Matching Patterns, In: Vol 2: Linear Modeling: Backgroung and Ap- plication. Handbook of Formal Languages, Berlin, Heidel- berg: Springer, 1997, p. 399–462. [9] Crochemore, M., Rytter: Text Algorithms. Oxford Univer- sity Press, 1994. [10] Dubiner, M., Galil, Z., Magen, E.: Faster Tree Pattern Matching. In: Journal of ACM, Vol. 41 (1994), No. 2, p. 205 –213. [11] Ferdinand Ch., Seidl H., Wilhelm R.: Tree Automata for Code Selection, In: Acta Informatica, Berlin: Springer, Vol. 31 (1994), No. 8, p. 741–760. [12] Flouri, T., Melichar, B., Janoušek, J.: Tree Pattern Matching by Pushdown Automata. Abstract In: LSD 2009 Talks’ Abstracts, Department of Computer Science, King’s College, London, p. 5. [13] Fraser, Ch. W., Hanson, D. A., Proebsting, T. A.: Engi- neering a Simple, Efficient Code Generator, In: ACM Letters on Programming Languages and Systems, Vol. 1, 3 (1992), p. 213–226. [14] Fraser, Ch. W., Henry, R. R., Proebsting, T. A.: BURG: Fast Optimal Instruction Selection and Tree Parsing, In: ACM SIGPLAN Notices, Vol. 27 (1992), p. 68–76. [15] Gecseg, F, Steinby, M.: Tree Languages, In: Vol 3: Beyond Words. Handbook of Formal Languages. Berlin, Heidel- berg: Springer, 1997, p. 1–68. [16] Glanville, R. S., Graham, S. L.: A New Approach to Com- piler Code Generation, In: Proc. 5th ACM Symposium on Principles of Programming Languages, 1978, p. 231–240. [17] Hoffmann, C. M., O’Donnell, M. J.: Pattern Matching in Trees. In: Journal of the ACM, Vol. 29 (1982), No. 1, p. 68–95. [18] Madhavan, M., Shankar, P., Siddhartha, R., Rama- krishna, U.: Extending Graham–Glanville Techniques for Optimal Code Generation. In: ACM Transactions on Programming Languages and Systems. Vol. 22 (2000), No. 6, p. 973–1001. [19] Melichar, B., Holub, J., Polcar, J.: Text Searching Algo- rithms. Available on: http://stringology.org/athens/, release November 2005, 2005. [20] Ramesh, R., Ramakrishan, I. V.: Nonlinear Tree Pattern Matching. In: Journal of the ACM, Vol. 39 (1992), No. 2, p. 295–316. [21] Shankar, P., Gantait, A., Yuvaraj, A., Madhavan, M. A.: New Algorithm for Linear Regular Tree Pattern Match- ing. In: Theoretical Computer Science. Elsevier, Vol. 242 (2000), No. 1–2, p. 125–142. Tomáš Flouri e-mail: flourt1@fel.cvut.cz Department of Computer Science and Engineering Czech Technical University in Prague Faculty of Electrical Engineering Karlovo Nám. 13 121 35 Prague 2, Czech Republic © Czech Technical University Publishing House http://ctn.cvut.cz/ap/ 33 Acta Polytechnica Vol. 49 No. 2–3/2009 << /ASCII85EncodePages false /AllowTransparency false /AutoPositionEPSFiles true /AutoRotatePages /None /Binding /Left /CalGrayProfile (Dot Gain 20%) /CalRGBProfile (sRGB IEC61966-2.1) /CalCMYKProfile (U.S. Web Coated \050SWOP\051 v2) /sRGBProfile (sRGB IEC61966-2.1) /CannotEmbedFontPolicy /Error /CompatibilityLevel 1.4 /CompressObjects /Tags /CompressPages true /ConvertImagesToIndexed true /PassThroughJPEGImages true /CreateJobTicket false /DefaultRenderingIntent /Default /DetectBlends true /DetectCurves 0.0000 /ColorConversionStrategy /CMYK /DoThumbnails false /EmbedAllFonts true /EmbedOpenType false /ParseICCProfilesInComments true /EmbedJobOptions true /DSCReportingLevel 0 /EmitDSCWarnings false /EndPage -1 /ImageMemory 1048576 /LockDistillerParams false /MaxSubsetPct 100 /Optimize true /OPM 1 /ParseDSCComments true /ParseDSCCommentsForDocInfo true /PreserveCopyPage true /PreserveDICMYKValues true /PreserveEPSInfo true /PreserveFlatness true /PreserveHalftoneInfo false /PreserveOPIComments true /PreserveOverprintSettings true /StartPage 1 /SubsetFonts true /TransferFunctionInfo /Apply /UCRandBGInfo /Preserve /UsePrologue false /ColorSettingsFile () /AlwaysEmbed [ true ] /NeverEmbed [ true ] /AntiAliasColorImages false /CropColorImages true /ColorImageMinResolution 300 /ColorImageMinResolutionPolicy /OK /DownsampleColorImages true /ColorImageDownsampleType /Bicubic /ColorImageResolution 300 /ColorImageDepth -1 /ColorImageMinDownsampleDepth 1 /ColorImageDownsampleThreshold 1.50000 /EncodeColorImages true /ColorImageFilter /DCTEncode /AutoFilterColorImages true /ColorImageAutoFilterStrategy /JPEG /ColorACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /ColorImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000ColorACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000ColorImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasGrayImages false /CropGrayImages true /GrayImageMinResolution 300 /GrayImageMinResolutionPolicy /OK /DownsampleGrayImages true /GrayImageDownsampleType /Bicubic /GrayImageResolution 300 /GrayImageDepth -1 /GrayImageMinDownsampleDepth 2 /GrayImageDownsampleThreshold 1.50000 /EncodeGrayImages true /GrayImageFilter /DCTEncode /AutoFilterGrayImages true /GrayImageAutoFilterStrategy /JPEG /GrayACSImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /GrayImageDict << /QFactor 0.15 /HSamples [1 1 1 1] /VSamples [1 1 1 1] >> /JPEG2000GrayACSImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /JPEG2000GrayImageDict << /TileWidth 256 /TileHeight 256 /Quality 30 >> /AntiAliasMonoImages false /CropMonoImages true /MonoImageMinResolution 1200 /MonoImageMinResolutionPolicy /OK /DownsampleMonoImages true /MonoImageDownsampleType /Bicubic /MonoImageResolution 1200 /MonoImageDepth -1 /MonoImageDownsampleThreshold 1.50000 /EncodeMonoImages true /MonoImageFilter /CCITTFaxEncode /MonoImageDict << /K -1 >> /AllowPSXObjects false /CheckCompliance [ /None ] /PDFX1aCheck false /PDFX3Check false /PDFXCompliantPDFOnly false /PDFXNoTrimBoxError true /PDFXTrimBoxToMediaBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXSetBleedBoxToMediaBox true /PDFXBleedBoxToTrimBoxOffset [ 0.00000 0.00000 0.00000 0.00000 ] /PDFXOutputIntentProfile () /PDFXOutputConditionIdentifier () /PDFXOutputCondition () /PDFXRegistryName () /PDFXTrapped /False /CreateJDFFile false /Description << /ARA /BGR /CHS /CHT /CZE /DAN /DEU /ESP /ETI /FRA /GRE /HEB /HRV (Za stvaranje Adobe PDF dokumenata najpogodnijih za visokokvalitetni ispis prije tiskanja koristite ove postavke. Stvoreni PDF dokumenti mogu se otvoriti Acrobat i Adobe Reader 5.0 i kasnijim verzijama.) /HUN /ITA /JPN /KOR /LTH /LVI /NLD (Gebruik deze instellingen om Adobe PDF-documenten te maken die zijn geoptimaliseerd voor prepress-afdrukken van hoge kwaliteit. De gemaakte PDF-documenten kunnen worden geopend met Acrobat en Adobe Reader 5.0 en hoger.) /NOR /POL /PTB /RUM /RUS /SKY /SLV /SUO /SVE /TUR /UKR /ENU (Use these settings to create Adobe PDF documents best suited for high-quality prepress printing. Created PDF documents can be opened with Acrobat and Adobe Reader 5.0 and later.) >> /Namespace [ (Adobe) (Common) (1.0) ] /OtherNamespaces [ << /AsReaderSpreads false /CropImagesToFrames true /ErrorControl /WarnAndContinue /FlattenerIgnoreSpreadOverrides false /IncludeGuidesGrids false /IncludeNonPrinting false /IncludeSlug false /Namespace [ (Adobe) (InDesign) (4.0) ] /OmitPlacedBitmaps false /OmitPlacedEPS false /OmitPlacedPDF false /SimulateOverprint /Legacy >> << /AddBleedMarks false /AddColorBars false /AddCropMarks false /AddPageInfo false /AddRegMarks false /ConvertColors /ConvertToCMYK /DestinationProfileName () /DestinationProfileSelector /DocumentCMYK /Downsample16BitImages true /FlattenerPreset << /PresetSelector /MediumResolution >> /FormElements false /GenerateStructure false /IncludeBookmarks false /IncludeHyperlinks false /IncludeInteractive false /IncludeLayers false /IncludeProfiles false /MultimediaHandling /UseObjectSettings /Namespace [ (Adobe) (CreativeSuite) (2.0) ] /PDFXOutputIntentProfileSelector /DocumentCMYK /PreserveEditing true /UntaggedCMYKHandling /LeaveUntagged /UntaggedRGBHandling /UseDocumentProfile /UseDocumentBleed false >> ] >> setdistillerparams << /HWResolution [2400 2400] /PageSize [612.000 792.000] >> setpagedevice