{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,1]],"date-time":"2026-02-01T19:43:43Z","timestamp":1769975023706,"version":"3.49.0"},"reference-count":4,"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":[[2008,6]]},"abstract":"<jats:p> Conjunctive grammars, introduced by Okhotin, extend context-free grammars by an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Okhotin posed nine open problems concerning those grammars. One of them was a question, whether a conjunctive grammars over a unary alphabet generate only regular languages. We give a negative answer, contrary to the conjectured positive one, by constructing a conjunctive grammar for the language {a<jats:sup>4<jats:sup>n<\/jats:sup><\/jats:sup> : n \u2208 \u2115}. We also generalize this result: for every set of natural numbers L we show that {a<jats:sup>n<\/jats:sup> : n \u2208 L} is a conjunctive unary language, whenever the set of representations in base-k system of elements of L is regular, for arbitrary k. <\/jats:p>","DOI":"10.1142\/s012905410800584x","type":"journal-article","created":{"date-parts":[[2008,6,3]],"date-time":"2008-06-03T06:27:20Z","timestamp":1212474440000},"page":"597-615","source":"Crossref","is-referenced-by-count":42,"title":["CONJUNCTIVE GRAMMARS GENERATE NON-REGULAR UNARY LANGUAGES"],"prefix":"10.1142","volume":"19","author":[{"given":"ARTUR","family":"JE\u017b","sequence":"first","affiliation":[{"name":"Institute of Computer Science, University of Wroclaw, ul. Joliot-Curie 15, Wroclaw, 53-407, Poland"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","first-page":"519","volume":"6","author":"Okhotin A.","journal-title":"Journal of Automata, Languages and Combinatorics"},{"key":"rf2","first-page":"145","volume":"79","author":"Okhotin A.","journal-title":"Formal Language Theory Column. Bulletin of the EATCS."},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2004.03.006"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1020213411126"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S012905410800584X","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T20:33:26Z","timestamp":1565123606000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S012905410800584X"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,6]]},"references-count":4,"journal-issue":{"issue":"03","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2008,6]]}},"alternative-id":["10.1142\/S012905410800584X"],"URL":"https:\/\/doi.org\/10.1142\/s012905410800584x","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,6]]}}}