{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2022,4,1]],"date-time":"2022-04-01T17:46:55Z","timestamp":1648835215301},"reference-count":4,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p> Simple grammar reduction is an important component in the implementation of Concatenation State Machines (a hardware version of stateless push-down automata designed for wire-speed network packet classification). We present a comparison and experimental analysis of the best-known algorithms for grammar reduction. There are two approaches to this problem: one processing compressed strings without decompression and another one which processes strings explicitly. It turns out that the second approach is more efficient in the considered practical scenario despite having worst-case exponential time complexity (while the first one is polynomial). The study has been conducted in the context of network packet classification, where simple grammars are used for representing the classification policies. <\/jats:p>","DOI":"10.1142\/s0129054107004930","type":"journal-article","created":{"date-parts":[[2007,7,30]],"date-time":"2007-07-30T11:29:46Z","timestamp":1185794986000},"page":"715-725","source":"Crossref","is-referenced-by-count":0,"title":["REDUCING SIMPLE GRAMMARS: EXPONENTIAL AGAINST HIGHLY-POLYNOMIAL TIME IN PRACTICE"],"prefix":"10.1142","volume":"18","author":[{"given":"C\u00c9DRIC","family":"BASTIEN","sequence":"first","affiliation":[{"name":"D\u00e9pt d'informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau PQ, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"JUREK","family":"CZYZOWICZ","sequence":"additional","affiliation":[{"name":"D\u00e9pt d'informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau PQ, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WOJCIECH","family":"FRACZAK","sequence":"additional","affiliation":[{"name":"IDT Canada Inc., Ottawa ON, Canada"},{"name":"D\u00e9pt d'informatique, Universit\u00e9 du Qu\u00e9bec en Outaouais, Gatineau PQ, Canada"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"WOJCIECH","family":"RYTTER","sequence":"additional","affiliation":[{"name":"Instytut Informatyki, Universytet Warszawski, Warsaw, Poland"},{"name":"Department of Mathematics and Informatics, Copernicus University, Torun, Poland"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-51859-2_8"},{"key":"rf5","volume-title":"Introduction to formal language theory","author":"Harrison M. A.","year":"1978"},{"key":"rf6","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(95)00064-X"},{"key":"rf8","first-page":"187","volume":"1","author":"Miyazaki Masamichi","journal-title":"Journal of Discrete Algorithms"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054107004930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:42:16Z","timestamp":1565138536000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054107004930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":4,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2007,8]]}},"alternative-id":["10.1142\/S0129054107004930"],"URL":"https:\/\/doi.org\/10.1142\/s0129054107004930","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]}}}