{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,30]],"date-time":"2025-10-30T06:56:12Z","timestamp":1761807372468},"reference-count":17,"publisher":"Cambridge University Press (CUP)","issue":"4","license":[{"start":{"date-parts":[[2007,8,1]],"date-time":"2007-08-01T00:00:00Z","timestamp":1185926400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Math. Struct. Comp. Sci."],"published-print":{"date-parts":[[2007,8]]},"abstract":"<jats:p>In this paper we discuss the following interesting question about accepting hybrid networks of evolutionary processors (AHNEP), which are a recently introduced bio-inspired computing model. The question is: how many processors are required in such a network to recognise a given language <jats:italic>L<\/jats:italic>? Two answers are proposed for the most general case, when <jats:italic>L<\/jats:italic> is a recursively enumerable language, and both answers improve on the previously known bounds. In the first case the network has a number of processors that is linearly bounded by the cardinality of the tape alphabet of a Turing machine recognising the given language <jats:italic>L<\/jats:italic>. In the second case we show that an AHNEP with a fixed underlying structure can accept any recursively enumerable language. The second construction has another useful property from a practical point of view as it includes a universal AHNEP as a subnetwork, and hence only a limited number of its parameters depend on the given language.<\/jats:p>","DOI":"10.1017\/s0960129507006202","type":"journal-article","created":{"date-parts":[[2007,8,2]],"date-time":"2007-08-02T09:34:17Z","timestamp":1186047257000},"page":"753-771","source":"Crossref","is-referenced-by-count":28,"title":["On the size complexity of universal accepting hybrid networks of evolutionary processors"],"prefix":"10.1017","volume":"17","author":[{"given":"FLORIN","family":"MANEA","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"CARLOS","family":"MARTIN-VIDE","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"VICTOR","family":"MITRANA","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"56","published-online":{"date-parts":[[2007,8,1]]},"reference":[{"key":"S0960129507006202_ref9","volume-title":"Computers and Intractability. A Guide to the Theory of NP-completeness","author":"Garey","year":"1979"},{"key":"S0960129507006202_ref8","first-page":"109","volume-title":"Proc. AAAI National Conf. on AI","author":"Fahlman","year":"1983"},{"key":"S0960129507006202_ref6","doi-asserted-by":"publisher","DOI":"10.1142\/9789812704979_0009"},{"key":"S0960129507006202_ref14","first-page":"401","article-title":"Hybrid networks of evolutionary processors. Proc. of GECCO 2003","volume":"2723","author":"Martin-Vide","year":"2003","journal-title":"Springer-Verlag Lecture Notes in Computer Science"},{"key":"S0960129507006202_ref5","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-62844-4_22"},{"key":"S0960129507006202_ref4","unstructured":"Csuhaj-Varj\u00fa E. , Dassow J. , Kelemen J. and P\u0103un G. (1993) Grammar Systems, Gordon and Breach."},{"key":"S0960129507006202_ref7","first-page":"31","volume-title":"Artificial Intelligence and Information-Control Systems of Robots'94","author":"Errico","year":"1994"},{"key":"S0960129507006202_ref16","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-56196-2"},{"key":"S0960129507006202_ref10","volume-title":"The Connection Machine","author":"Hillis","year":"1985"},{"key":"S0960129507006202_ref2","doi-asserted-by":"publisher","DOI":"10.1007\/s00236-003-0114-y"},{"key":"S0960129507006202_ref3","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.07.035"},{"key":"S0960129507006202_ref15","volume-title":"DNA Computing. New Computing Paradigms","author":"P\u00fb","year":"1998"},{"key":"S0960129507006202_ref12","doi-asserted-by":"publisher","DOI":"10.1016\/j.entcs.2005.09.024"},{"key":"S0960129507006202_ref1","doi-asserted-by":"crossref","unstructured":"Castellanos J. , Martin-Vide C. , Mitrana V. and Sempere J. (2001) Solving NP-complete problems with networks of evolutionary processors. In: Mira J. and Prieto A. (eds.) IWANN 2001. Springer-Verlag Lecture Notes in Computer Science 2084 621\u2013628.","DOI":"10.1007\/3-540-45720-8_74"},{"key":"S0960129507006202_ref17","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.89.14.6575"},{"key":"S0960129507006202_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/11493785_21"},{"key":"S0960129507006202_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-31834-7_22"}],"container-title":["Mathematical Structures in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0960129507006202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,1]],"date-time":"2019-04-01T15:00:02Z","timestamp":1554130802000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0960129507006202\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,8]]},"references-count":17,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2007,8]]}},"alternative-id":["S0960129507006202"],"URL":"https:\/\/doi.org\/10.1017\/s0960129507006202","relation":{},"ISSN":["0960-1295","1469-8072"],"issn-type":[{"value":"0960-1295","type":"print"},{"value":"1469-8072","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,8]]}}}