D:\sbornik\...\A_Kocharyan.DVI


Mathematical Problems of Computer Science 28, 2007, 34{44.

OTAS - ï»ùëï»ñÇ Ñ³Ù»Ù³ïÙ³Ý ËݹÇñÝ»ñÇ ÉáõÍÙ³Ý Íñ³·ñ³ÛÇÝ ·áñÍÇù

²ñÙ»Ý ì. øáã³ñÛ³Ý

ÐÐ ¶²² ÆÝýáñÙ³ïÇϳÛÇ ¨ ³íïáÙ³ï³óÙ³Ý åñáµÉ»ÙÝ»ñÇ ÇÝëïÇïáõï
e-mail: armkoch@ipia.sci.am

²Ù÷á÷áõÙ

êï»ÕÍí³Í ¿ OTAS (Online Tessallation Automata Syntesator) Íñ³·ñ³ÛÇÝ ·áñÍÇùÁ, áñÁ
ï»ùëï»ñÇ Ñ³Ù»Ù³ïÙ³Ý ËݹÇñÝ»ñÇ úʲ ׳ݳã»ÉÇ »Ýó¹³ëÇ Ñ³Ù³ñ ëÇÝû½áõÙ ¿
ï»ùëï»ñÁ ѳٻٳïáÕ Íñ³·ñ³ÛÇÝ Ùá¹áõÉ:

ú·ï³·áñÍí³Í ·ñ³Ï³ÝáõÃÛáõÝ

[1] K.Inoue and A.Nakamura. Some properties of two-dimensional on-line tessellation ac-
ceptors. Information Sciences,vol.13, p.95-121, 1977.

[2] K.Inoue and A.Nakamura. A Survey of two-dimensional automata theory. In P roc. 5th
Int. M eeting of Young Computer Scientists.J Dasson and J.Kelemen (Eds.), p. 72-91. Lecture
Notes in Computer Science 381, Springer-Verlag, Berlin, 1990.

[3] D.Giammarresi and A.Restivo. Two-dimensional languages. In Handbook of F ormal
L aguage Theory, v.3, Springer-Verlag, N.Y.,1996.

[4] D.Giammarresi, A.Restivo, S.Siebert and W.Thomas. Monadic second order logic over
rectangular pictures and recognizability by tiling systems. Information and computation.
Vol.125, No. 1, p. 32-45, 1996.

[5] L. Boasson, P. Cegielski, I. Guessarian, Y. Matiyasevich. Window accumulated subse-
quence matching is linear. Annals of P ure and Applied L ogic Vol. 113(2001),pp.59-80.

[6] K. V. Shahbazyan, Yu. H. Shoukourian. The Finite-state Recognizability of sequences
of Integers.Transactions of the Institute for Informatic and Automation P roblems of NAS
R A. Vol 27,(2006), 151-173

[7] A. V. Kocharyan, K. V. Shahbazyan. On-line Tessellation automata as a text Matching
Problems Solver.Transactions of the Institute for Informatic and Automation P roblems of
NAS R A. Vol 27,(2006), 54-62.

[8] C.T. Djamegni and M. Tchuente. A New Dynamic Programming Algorithm on two
dimensional arrays. P arallel P rocessing L etters, 10(1)(2000) 15-27.

OTAS Program Tool for Text Matching Problems
A .V . K o c h a r ya n

Abstract

OTAS is a toolkit for solving any text matching problems from a ¯xed class. OTAS
synthesize online tessallation automata solving the problem.

3 4