TAILIEUCHUNG - Thuật toán mới xác định độ trễ giải mã của ngôn ngữ chính quy

Bài báo đề xuất một giải thuật mới xác định độ trễ giải mã của ngôn ngữ chính quy được đón nhận với ôtômat hữu hạn A. Giải thuật có độ phức tạp O(n3) với n là số cung và trạng thái của A. nội dung chi tiết. | TÔp chẵ Tin hồc v iãu khiºn hồc, , (2012), 141-152 THU T TO N MẻI X C ÀNH ậ TR GI I M CếA NGặN NGÚ CH NH QUY 0 xq r xq1 D xq x 0 xr r x2 D rex xq r 3 1 Trữớng Ôi hồc Sữ phÔm Kÿ thuêt Nam ành 2 Trữớng Ôi hồc Sữ phÔm Kÿ thuêt Hững Yản 3 Trữớng Ôi hồc BĂch khoa H Nởi Túm t t. f i Ăo 1ã xuĐt mởt giÊi thuêt mợi xĂ 1ành 1ở trạ giÊi m ừ ngổn ngỳ hẵnh quy 1ữủ 1oĂn nhên ði ổtổm t hỳu hÔn AF qiÊi thuêt õ 1ở phự tÔp thới gi n l O(n3 )D ð 1õ n l số ung v trÔng thĂi ừ AF Abstract. sn this p perD we propose new lgorithm determining de iphering del y of regul r l ngu geD whi h re ognizes y finite utom ton AF he lgorithm h s time omplexity O(n3 )D where n is the num er of st tes nd edges of AF 1. GIẻI THI U rong Ă ph²p giÊi m thổng thữớngD khi xƠu Ưn giÊi m 1ữủ 1ồ tứ trĂi qu phÊiD thới 1iºm phĂt hiằn thĐy mởt tứ m trong xƠu v thới 1iºm tĐt Ê Ă tứ m trong xƠu 1ữủ xĂ 1ành mởt Ă h hư hưn l khĂ nh uF uhoÊng thới gi n trạ n y 1ữủ hẳnh thự hõ ơng khĂi niằm 1ở trạ giÊi mÂD khĂi niằm n y xuĐt hiằn rĐt sợm trong lỵ thuyát mÂD nhữ trong Ă ổng trẳnh ừ qil ert nd woore @IWSWA @xem W AD ừ vevenshtein @IWTRA @xem IH AF ợi khĂi niằm 1ở trạ giÊi m thẳ lợp m prefix l lợp m õ 1ở trạ giÊi m ơng HD tứ 1õ 1ở trạ giÊi m 1ữủ sỷ dửng trong lỵ thuyát m nhữ l mởt tiảu huân qu n trồng 1º phƠn loÔi m v l mởt th m số phÊn Ănh 1ở khõ trong quĂ trẳnh giÊi mÂF 0ối vợi Ă ựng dửngD viằ xĂ 1ành hẵnh xĂ 1ở trạ giÊi m ừ mởt ngổn ngỳD ho ph²p Ă hữỡng trẳnh mêt m tông hiằu quÊ thới gi n v loÔi ọ 1ữủ th o tĂ qu y lui trong quĂ trẳnh giÊi mÂF ho v i trỏ qu n trồng ừ 1ở trạ giÊi mÂD nhiãu tĂ giÊ 1 qu n tƠm nghiản ựuD mởt loÔt Ă ổng trẳnh nhữ ừ w rkov @IWTPA @xem IP AD hÔtzen erger @IWTTA @xem II AD ghoffrut @IWUWA @xem IQ AD u vF t iger @IWVTA @xem S AD tF hevolder @IWWRA @xem Q AD t vros uonst ntinidis @PHHPA @xem V AD F F ruyE F F x m @PHHPA @xem IR AD hF vF n

• Cơ sở dữ liệu
• Xác định độ trễ giải mã
• Độ trễ giải mã
• Ngôn ngữ chính quy
• ôtômat hữu hạn A
• Giải thuật mở rộng ôtômat
• Ôtômat lưỡng cực