{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:34:43Z","timestamp":1759638883380},"reference-count":0,"publisher":"World Scientific Pub Co Pte Lt","issue":"03","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[1990,9]]},"abstract":"<jats:p> We introduce BD (Breadth-Depth) grammars which extend context-free grammars by allowing breadth-first derivations. Their languages are recognized by Deque (double ended queue) automata having a single state. BD languages also include languages recognized by monostatic queue automata. <\/jats:p><jats:p> It is shown that the commutative image of BD languages is semilinear, that they have a periodicity (pumping) property, and can be homomorphically characterized as h(DAD\u2229R), where DAD is the Dyck-AntiDyck language, and R a regular set. <\/jats:p><jats:p> Non-autoinclusive BD grammars coincide in power with breadth-first grammars with regular right parts. <\/jats:p>","DOI":"10.1142\/s0129054190000163","type":"journal-article","created":{"date-parts":[[2004,11,29]],"date-time":"2004-11-29T02:14:37Z","timestamp":1101694477000},"page":"219-232","source":"Crossref","is-referenced-by-count":3,"title":["BREADTH AND DEPTH GRAMMARS AND DEQUE AUTOMATA"],"prefix":"10.1142","volume":"01","author":[{"given":"ALESSANDRA","family":"CHERUBINI","sequence":"first","affiliation":[{"name":"Dipartimento di Matematica, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy"}]},{"given":"CLAUDIO","family":"CITRINI","sequence":"additional","affiliation":[{"name":"Dipartimento di Matematica, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133 Milano, Italy"}]},{"given":"STEFANO CRESPI","family":"REGHIZZI","sequence":"additional","affiliation":[{"name":"Dipartimento di Elettronica, Politecnico di Milano Piazza Leonardo da Vinci 32, 20133 Milano, Italy"}]},{"given":"DINO","family":"MANDRIOLI","sequence":"additional","affiliation":[{"name":"Dipartimento di Elettronica, Politecnico di Milano Piazza Leonardo da Vinci 32, 20133 Milano, Italy"}]}],"member":"219","published-online":{"date-parts":[[2012,1,25]]},"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054190000163","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T14:07:28Z","timestamp":1565186848000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054190000163"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1990,9]]},"references-count":0,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2012,1,25]]},"published-print":{"date-parts":[[1990,9]]}},"alternative-id":["10.1142\/S0129054190000163"],"URL":"https:\/\/doi.org\/10.1142\/s0129054190000163","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[1990,9]]}}}