ALGORITMA UNTUK MATCHING PADA SISTEM PENULISAN ULANG EKSPRESI

Slamet Santosa, Anton Setiawan Honggowibowo

Abstract


Matching process in tree is finding subtree in a given tree which to be replaced to variables those occur in pattern tree. It is an important problem that occurs as a crucial operation in functional and equational programming such as Term Rewriting System. We present an algorithm for matching process on such term in tree based on pattern matching. We linearize both given tree and pattern tree into string representation by using Euler technique and and apply prefix-sum to computers the rank of all linearized edge. And then we do matcing on string sequential.


Full Text:

PDF

References


N.Dershowitz, JP. Jouannaud, JW. Klop, “Mode Problems in Rewriting Technique”,, Research report of Computer Science, Report CS-R0332, 1993.

N.Dershowitz, JP. Jouannaud, “Rewriting System”, Handbook of Theoretical Computer Science, North-Holland, chapter 6, pages 243-320, 1990.

Joseph Jaja, “An Introduction to Parallel Algorithms”, Addison-Wesley Publicing Company, USA, 1992.

Herbert Schildt, “The Complete C Reference”, Osborne Mc. Graw-Hill 3d Edition, California, USA, 1995.

Z.Galil, “Optimal Parallel Algorithms for String Matching”, Jurnal Information and Control, pp. 144-157, 1985.




DOI: http://doi.org/10.12928/telkomnika.v3i2.1226

Refbacks

  • There are currently no refbacks.


Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

TELKOMNIKA Telecommunication, Computing, Electronics and Control
ISSN: 1693-6930, e-ISSN: 2302-9293
Universitas Ahmad Dahlan, 4th Campus
Jl. Ringroad Selatan, Kragilan, Tamanan, Banguntapan, Bantul, Yogyakarta, Indonesia 55191
Phone: +62 (274) 563515, 511830, 379418, 371120
Fax: +62 274 564604

View TELKOMNIKA Stats