{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T04:40:11Z","timestamp":1748752811120,"version":"3.41.0"},"reference-count":43,"publisher":"World Scientific Pub Co Pte Ltd","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Patt. Recogn. Artif. Intell."],"published-print":{"date-parts":[[2016,5]]},"abstract":"<jats:p>In this paper a platform is presented, that given a stochastic context-free grammar (SCFG), automatically outputs the description of the parser in synthesizable hardware description language (HDL) which can be downloaded in an Field Programmable Gate Arrays (FPGA) board. Initially, according to our methodology the SCFG is augmented with attributes which store the probability values and can be evaluated through corresponding stack actions. The architecture of the produced system is based on a proposed extension of Earley\u2019s parallel algorithm, which given an input string, generates the parse trees in the form of an AND-Or parse tree. This AND-or parse tree is then traversed using a proposed tree traversal technique in order to execute the corresponding actions in the correct order, so as to compute the necessary probabilities. The platform is suitable for embedded systems applications where a natural language interface is required or in pattern recognition tasks. The parser generated by the presented platform has been tested for various SCFGs and compared to software approaches. The performance comparison is one to two orders of magnitude in favor of the presented hardware, compared to previous software approaches, depending on the application, the input string length and the number of produced trees.<\/jats:p>","DOI":"10.1142\/s0218001416500087","type":"journal-article","created":{"date-parts":[[2016,1,14]],"date-time":"2016-01-14T17:03:37Z","timestamp":1452791017000},"page":"1650008","source":"Crossref","is-referenced-by-count":3,"title":["Parallel Hardware Stochastic Context-Free Parsers"],"prefix":"10.1142","volume":"30","author":[{"given":"Christos","family":"Pavlatos","sequence":"first","affiliation":[{"name":"Hellenic Air Force Academy, Dekeleia Air Force Base, Athens, Greece"}]},{"given":"Alexandros C.","family":"Dimopoulos","sequence":"additional","affiliation":[{"name":"Harokopio University of Athens, 9 Omirou Street 177 78 Tavros, Greece"}]},{"given":"George","family":"Papakonstantinou","sequence":"additional","affiliation":[{"name":"National Technical University of Athens, Heroon Polytechniou 9,15780 Zografou, Greece"}]}],"member":"219","published-online":{"date-parts":[[2016,4,12]]},"reference":[{"key":"S0218001416500087BIB001","volume-title":"Compilers: Principles, Techniques, and Tools","author":"Aho A. V.","year":"2006","edition":"2"},{"key":"S0218001416500087BIB002","series-title":"Series in Automatic Computation","volume-title":"The Theory of Parsing, Translation, and Compiling","author":"Aho A. V.","year":"1972"},{"key":"S0218001416500087BIB003","doi-asserted-by":"publisher","DOI":"10.1016\/j.nbt.2010.02.012"},{"key":"S0218001416500087BIB004","doi-asserted-by":"publisher","DOI":"10.1261\/rna.215407"},{"key":"S0218001416500087BIB005","first-page":"305","volume-title":"A Handbook of Natural Language Processing: Techniques and Applications for the Processing of Language as Text","author":"Andre E.","year":"2000"},{"key":"S0218001416500087BIB006","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1998.2772"},{"key":"S0218001416500087BIB007","doi-asserted-by":"publisher","DOI":"10.1109\/T-C.1973.223746"},{"key":"S0218001416500087BIB008","first-page":"803","volume":"86","author":"Bordim J.","year":"2003","journal-title":"IEICE Trans. Inform. Syst."},{"key":"S0218001416500087BIB009","doi-asserted-by":"publisher","DOI":"10.1142\/9789812775320_0004"},{"key":"S0218001416500087BIB010","doi-asserted-by":"publisher","DOI":"10.1016\/0031-3203(86)90003-8"},{"key":"S0218001416500087BIB011","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.1984.4767522"},{"key":"S0218001416500087BIB012","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.1956.1056813"},{"key":"S0218001416500087BIB014","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/3345.001.0001","volume-title":"A Grammatical View of Logic Programming","author":"Deransart P.","year":"1993"},{"key":"S0218001416500087BIB015","doi-asserted-by":"publisher","DOI":"10.1016\/j.cl.2009.09.003"},{"key":"S0218001416500087BIB016","doi-asserted-by":"publisher","DOI":"10.1145\/362007.362035"},{"volume-title":"Syntactic Pattern Recognition and Applications","year":"1982","author":"Fu K. S.","key":"S0218001416500087BIB017"},{"key":"S0218001416500087BIB018","doi-asserted-by":"publisher","DOI":"10.4304\/jnw.9.3.769-776"},{"key":"S0218001416500087BIB019","doi-asserted-by":"publisher","DOI":"10.1145\/357103.357112"},{"volume-title":"Introduction to Formal Language Theory","year":"1978","author":"Harrison M. A.","key":"S0218001416500087BIB020"},{"key":"S0218001416500087BIB021","doi-asserted-by":"publisher","DOI":"10.1109\/12.90253"},{"key":"S0218001416500087BIB022","first-page":"315","volume":"17","author":"Jelinek F.","year":"1991","journal-title":"Comput. Linguist."},{"key":"S0218001416500087BIB023","doi-asserted-by":"publisher","DOI":"10.1016\/j.patrec.2004.09.056"},{"key":"S0218001416500087BIB025","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(83)90026-9"},{"key":"S0218001416500087BIB026","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/15.6.446"},{"key":"S0218001416500087BIB027","doi-asserted-by":"publisher","DOI":"10.1016\/0885-2308(90)90022-X"},{"key":"S0218001416500087BIB028","doi-asserted-by":"publisher","DOI":"10.1142\/S021800140600482X"},{"key":"S0218001416500087BIB029","doi-asserted-by":"publisher","DOI":"10.1145\/1839480.1839484"},{"key":"S0218001416500087BIB030","doi-asserted-by":"publisher","DOI":"10.1016\/j.comnet.2006.01.004"},{"key":"S0218001416500087BIB031","doi-asserted-by":"publisher","DOI":"10.1145\/210376.197409"},{"key":"S0218001416500087BIB032","doi-asserted-by":"publisher","DOI":"10.1016\/0010-4809(81)90033-1"},{"key":"S0218001416500087BIB033","doi-asserted-by":"publisher","DOI":"10.1093\/comjnl\/29.3.241"},{"issue":"9","key":"S0218001416500087BIB034","first-page":"382","volume":"28","author":"Papakonstantinou G.","year":"1986","journal-title":"Angewandte Informatik"},{"key":"S0218001416500087BIB035","first-page":"196","volume":"35","author":"Pavlatos C.","year":"2009","journal-title":"Comput. Lang. Syst. Struct."},{"key":"S0218001416500087BIB037","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-74161-1_33"},{"key":"S0218001416500087BIB040","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(96)00023-3"},{"issue":"2","key":"S0218001416500087BIB042","first-page":"165","volume":"21","author":"Stolcke A.","year":"1995","journal-title":"Comput. Linguist."},{"key":"S0218001416500087BIB043","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4615-4034-2_1"},{"key":"S0218001416500087BIB044","doi-asserted-by":"publisher","DOI":"10.1109\/34.56207"},{"key":"S0218001416500087BIB045","doi-asserted-by":"publisher","DOI":"10.1109\/TSMC.1980.4308414"},{"key":"S0218001416500087BIB046","doi-asserted-by":"publisher","DOI":"10.1142\/S021821309500019X"},{"key":"S0218001416500087BIB049","doi-asserted-by":"publisher","DOI":"10.1016\/0146-664X(81)90062-9"},{"key":"S0218001416500087BIB051","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2010.05.005"},{"key":"S0218001416500087BIB052","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(67)80007-X"}],"container-title":["International Journal of Pattern Recognition and Artificial Intelligence"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0218001416500087","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,1]],"date-time":"2025-06-01T04:01:57Z","timestamp":1748750517000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0218001416500087"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,4,12]]},"references-count":43,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2016,4,12]]},"published-print":{"date-parts":[[2016,5]]}},"alternative-id":["10.1142\/S0218001416500087"],"URL":"https:\/\/doi.org\/10.1142\/s0218001416500087","relation":{},"ISSN":["0218-0014","1793-6381"],"issn-type":[{"type":"print","value":"0218-0014"},{"type":"electronic","value":"1793-6381"}],"subject":[],"published":{"date-parts":[[2016,4,12]]}}}