{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T10:59:34Z","timestamp":1780743574686,"version":"3.54.1"},"reference-count":19,"publisher":"World Scientific Pub Co Pte Lt","issue":"05","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Int. J. Found. Comput. Sci."],"published-print":{"date-parts":[[2003,10]]},"abstract":"<jats:p> Given a function p : N \u2192 [0,1] of period n, we study the minimal size (number of states) of a one-way quantum finite automaton (Iqfa) inducing the stochastic event ap + b, for real constants a&gt;0, b\u22650, a+b\u22641. <\/jats:p><jats:p> First of all, we relate the estimation of the minimal size to the problem of finding a minimal difference cover for a suitable subset of Z<jats:sub>n<\/jats:sub>. <\/jats:p><jats:p> Then, by observing that the cardinality of a difference cover \u0394 for a set A \u2286 Z<jats:sub>n<\/jats:sub>, must satisfy [Formula: see text], we investigate the class of sets A admitting difference covers of cardinality exactly [Formula: see text]. <\/jats:p><jats:p> We relate this problem with the efficient construction of Golomb rulers and difference sets. We design an algorithm which outputs each of the Golomb rulers (if any) of a given set in pseudo-polynomial time. As a consequence, we obtain an efficient algorithm that construct minimal difference covers for a non-trivial class of sets. Moreover, by using projective geometry arguments, we give an algorithm that, for any n=q<jats:sup>2<\/jats:sup>+q+1 with q prime power, constructs difference sets for Z<jats:sub>n<\/jats:sub> in quadratic time. <\/jats:p>","DOI":"10.1142\/s0129054103002060","type":"journal-article","created":{"date-parts":[[2003,11,24]],"date-time":"2003-11-24T09:26:19Z","timestamp":1069665979000},"page":"871-888","source":"Crossref","is-referenced-by-count":15,"title":["GOLOMB RULERS AND DIFFERENCE SETS FOR SUCCINCT QUANTUM AUTOMATA"],"prefix":"10.1142","volume":"14","author":[{"given":"ALBERTO","family":"BERTONI","sequence":"first","affiliation":[{"name":"Dipartimento di Scienze dell' Informazione, Universit\u00e0 degli Studi di Milano, via Comelico 39, 20135 Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"CARLO","family":"MEREGHETTI","sequence":"additional","affiliation":[{"name":"Dipartimento di Scienze dell' Informazione, Universit\u00e0 degli Studi di Milano, via Comelico 39, 20135 Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"BEATRICE","family":"PALANO","sequence":"additional","affiliation":[{"name":"Dipartimento di Scienze dell' Informazione, Universit\u00e0 degli Studi di Milano, via Comelico 39, 20135 Milano, Italy"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"219","published-online":{"date-parts":[[2011,11,20]]},"reference":[{"key":"rf1","volume-title":"The design and analysis of computer algorithms","author":"AHO A. V.","year":"1974"},{"key":"rf4","doi-asserted-by":"publisher","DOI":"10.1137\/0117074"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1006\/inco.2000.2911"},{"key":"rf7","volume-title":"Design Theory","author":"BETH T.","year":"1986"},{"key":"rf8","doi-asserted-by":"publisher","DOI":"10.1109\/PROC.1977.10517"},{"key":"rf9","volume-title":"Characterizations of 1\u2013Way Quantum Finite Automata","author":"BRODSKY A.","year":"1999"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(00)00080-6"},{"key":"rf11","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(01)00356-0"},{"key":"rf12","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00073-1"},{"key":"rf13","volume-title":"Quantum Computing","author":"GRUSKA J.","year":"1999"},{"key":"rf14","first-page":"191","volume":"5","author":"GRUSKA J.","journal-title":"J. Automata, Languages and Combinatorics"},{"key":"rf16","doi-asserted-by":"publisher","DOI":"10.1109\/26.1464"},{"key":"rf17","first-page":"513","volume":"261","author":"LENSTRA A. K.","journal-title":"Mathematische Ann."},{"key":"rf19","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2002014"},{"key":"rf20","doi-asserted-by":"publisher","DOI":"10.1051\/ita:2001106"},{"key":"rf21","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(98)00191-1"},{"key":"rf22","doi-asserted-by":"crossref","first-page":"106","DOI":"10.1109\/TIT.1967.1053951","volume":"13","author":"ROBINSON J. P.","journal-title":"IEEE Trans. Inform. Theory"},{"key":"rf23","first-page":"337","volume":"43","author":"SINGER J.","journal-title":"Trans. Amer. Math. Soc."},{"key":"rf24","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-1906-1500747-6"}],"container-title":["International Journal of Foundations of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S0129054103002060","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,7]],"date-time":"2019-08-07T00:37:55Z","timestamp":1565138275000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S0129054103002060"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003,10]]},"references-count":19,"journal-issue":{"issue":"05","published-online":{"date-parts":[[2011,11,20]]},"published-print":{"date-parts":[[2003,10]]}},"alternative-id":["10.1142\/S0129054103002060"],"URL":"https:\/\/doi.org\/10.1142\/s0129054103002060","relation":{},"ISSN":["0129-0541","1793-6373"],"issn-type":[{"value":"0129-0541","type":"print"},{"value":"1793-6373","type":"electronic"}],"subject":[],"published":{"date-parts":[[2003,10]]}}}