{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,28]],"date-time":"2025-08-28T12:38:41Z","timestamp":1756384721574},"reference-count":21,"publisher":"World Scientific Pub Co Pte Lt","issue":"08","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:p> Non-self-embedding grammars are a restriction of context-free grammars which does not allow to describe recursive structures and, hence, which characterizes only the class of regular languages. A double exponential gap in size from non-self-embedding grammars to deterministic finite automata is known. The same size gap is also known from constant-height pushdown automata and [Formula: see text]-limited automata to deterministic finite automata. Constant-height pushdown automata and [Formula: see text]-limited automata are compared with non-self-embedding grammars. It is proved that non-self-embedding grammars and constant-height pushdown automata are polynomially related in size. Furthermore, a polynomial size simulation by [Formula: see text]-limited automata is presented. However, the converse transformation is proved to cost exponential. Finally, a different simulation shows that also the conversion of deterministic constant-height pushdown automata into deterministic [Formula: see text]-limited automata costs polynomial. <\/jats:p>","DOI":"10.1142\/s0129054120420071","type":"journal-article","created":{"date-parts":[[2020,12,29]],"date-time":"2020-12-29T01:59:04Z","timestamp":1609207144000},"page":"1133-1157","source":"Crossref","is-referenced-by-count":5,"title":["Non-Self-Embedding Grammars, Constant-Height Pushdown Automata, and Limited Automata"],"prefix":"10.1142","volume":"31","author":[{"given":"Bruno","family":"Guillon","sequence":"first","affiliation":[{"name":"LIMOS, Universit\u00e9 Clermont-Auvergne, France"}]},{"given":"Giovanni","family":"Pighizzini","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano, Italy"}]},{"given":"Luca","family":"Prigioniero","sequence":"additional","affiliation":[{"name":"Dipartimento di Informatica, Universit\u00e0 degli Studi di Milano, Italy"}]}],"member":"219","published-online":{"date-parts":[[2020,12,28]]},"reference":[{"key":"S0129054120420071BIB001","series-title":"LNCS","first-page":"47","volume-title":"CIAA 2002","volume":"2608","author":"Anselmo M.","year":"2002"},{"key":"S0129054120420071BIB002","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1016\/j.ic.2014.03.002","volume":"237","author":"Bedn\u00e1rov\u00e1 Z.","year":"2014","journal-title":"Inf. Comput."},{"key":"S0129054120420071BIB003","doi-asserted-by":"crossref","first-page":"23","DOI":"10.1016\/j.tcs.2012.05.009","volume":"449","author":"Bedn\u00e1rov\u00e1 Z.","year":"2012","journal-title":"Theoretical Computer Science"},{"issue":"2","key":"S0129054120420071BIB004","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1016\/S0019-9958(59)90362-6","volume":"2","author":"Chomsky N.","year":"1959","journal-title":"Information and Control"},{"issue":"4","key":"S0129054120420071BIB005","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1016\/S0019-9958(59)80017-6","volume":"2","author":"Chomsky N.","year":"1959","journal-title":"Information and Control"},{"issue":"4","key":"S0129054120420071BIB006","doi-asserted-by":"crossref","first-page":"385","DOI":"10.1016\/j.ic.2010.01.002","volume":"208","author":"Geffert V.","year":"2010","journal-title":"Inf. Comput."},{"issue":"1","key":"S0129054120420071BIB007","doi-asserted-by":"crossref","first-page":"196","DOI":"10.1016\/S0019-9958(67)90513-X","volume":"11","author":"Hibbard T. N.","year":"1967","journal-title":"Information and Control"},{"key":"S0129054120420071BIB008","volume-title":"Introduction to automata theory, languages, and computation - (2. ed.)","author":"Hopcroft J. E.","year":"2001"},{"issue":"2","key":"S0129054120420071BIB009","doi-asserted-by":"crossref","first-page":"537","DOI":"10.1016\/j.jcss.2011.06.004","volume":"78","author":"Kapoutsis C. A.","year":"2012","journal-title":"J. Comput. Syst. Sci."},{"key":"S0129054120420071BIB010","doi-asserted-by":"crossref","first-page":"299","DOI":"10.1016\/0304-3975(83)90026-9","volume":"28","author":"Kelemenov\u00e1 A.","year":"1984","journal-title":"Theor. Comput. Sci."},{"key":"S0129054120420071BIB011","doi-asserted-by":"crossref","first-page":"259","DOI":"10.1016\/j.ic.2017.09.005","volume":"259","author":"Kutrib M.","year":"2018","journal-title":"Information and Computation"},{"key":"S0129054120420071BIB012","series-title":"LNCS","first-page":"153","volume-title":"DCFS 2015","volume":"9118","author":"Kutrib M.","year":"2015"},{"issue":"3","key":"S0129054120420071BIB013","first-page":"287","volume":"5","author":"Mereghetti C.","year":"2000","journal-title":"Journal of Automata, Languages and Combinatorics"},{"issue":"2","key":"S0129054120420071BIB014","doi-asserted-by":"crossref","first-page":"410","DOI":"10.1137\/0214031","volume":"14","author":"Ogden W. F.","year":"1985","journal-title":"SIAM J. Comput."},{"key":"S0129054120420071BIB015","doi-asserted-by":"publisher","DOI":"10.1142\/S0129054109006784"},{"issue":"7","key":"S0129054120420071BIB016","doi-asserted-by":"crossref","first-page":"897","DOI":"10.1142\/S0129054114400140","volume":"25","author":"Pighizzini G.","year":"2014","journal-title":"Int. J. Found. Comput. Sci."},{"key":"S0129054120420071BIB017","first-page":"197","volume-title":"Ninth Workshop on Non-Classical Models of Automata and Applications, NCMA 2017, Prague, Czech Republic, August 17-18, 2017","author":"Pighizzini G.","year":"2017"},{"key":"S0129054120420071BIB018","doi-asserted-by":"crossref","first-page":"60","DOI":"10.1016\/j.ic.2019.01.002","volume":"266","author":"Pighizzini G.","year":"2019","journal-title":"Inf. Comput."},{"issue":"2","key":"S0129054120420071BIB019","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1006\/jcss.2002.1855","volume":"65","author":"Pighizzini G.","year":"2002","journal-title":"J. Comput. Syst. Sci."},{"key":"S0129054120420071BIB020","first-page":"275","volume-title":"Proceedings of the 10th Annual ACM Symposium on Theory of Computing, May 1-3, 1978, San Diego, California, USA","author":"Sakoda W. J.","year":"1978"},{"key":"S0129054120420071BIB021","volume-title":"Computational Complexity","author":"Wagner K. W.","year":"1986"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054120420071","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,21]],"date-time":"2021-01-21T03:33:16Z","timestamp":1611199996000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054120420071"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,12]]},"references-count":21,"journal-issue":{"issue":"08","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["10.1142\/S0129054120420071"],"URL":"https:\/\/doi.org\/10.1142\/s0129054120420071","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,12]]}}}