Impossibility results for weak threshold networks
dc.contributor.author | Busch, Costas | en |
dc.contributor.author | Mavronicolas, Marios | en |
dc.creator | Busch, Costas | en |
dc.creator | Mavronicolas, Marios | en |
dc.date.accessioned | 2019-11-13T10:38:50Z | |
dc.date.available | 2019-11-13T10:38:50Z | |
dc.date.issued | 1997 | |
dc.identifier.uri | http://gnosis.library.ucy.ac.cy/handle/7/53666 | |
dc.description.abstract | It is shown that a weak threshold network (in particular, threshold network) of width w and depth d cannot be constructed from balancers of width p0, p1, . . . , pm-1, if w does not divide Pd, where P is the least common multiple of p0, p1, . . . , pm-1. This holds regardless of the size of the network, as long as it is finite, and it implies a lower bound of logp w on its depth. More strongly, a lower bound of logpmax w is shown on the length of every path from an input wire to any output wire that exhibits the threshold property, where pmax is the maximum among p0, p1, . . . , Pm-1. © 1997 Elsevier Science B.V. | en |
dc.source | Information Processing Letters | en |
dc.source.uri | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0006891830&partnerID=40&md5=a0ab25b0c751ea6eb143b7ce2bb7f29f | |
dc.subject | Distributed computing | en |
dc.subject | Parallel processing | en |
dc.subject | Impossibility results | en |
dc.title | Impossibility results for weak threshold networks | en |
dc.type | info:eu-repo/semantics/article | |
dc.description.volume | 63 | |
dc.description.issue | 2 | |
dc.description.startingpage | 85 | |
dc.description.endingpage | 90 | |
dc.author.faculty | 002 Σχολή Θετικών και Εφαρμοσμένων Επιστημών / Faculty of Pure and Applied Sciences | |
dc.author.department | Τμήμα Πληροφορικής / Department of Computer Science | |
dc.type.uhtype | Article | en |
dc.description.notes | <p>Cited By :3</p> | en |
dc.source.abbreviation | Inf.Process.Lett. | en |
dc.contributor.orcid | Busch, Costas [0000-0002-4381-4333] | |
dc.gnosis.orcid | 0000-0002-4381-4333 |
Files in this item
Files | Size | Format | View |
---|---|---|---|
There are no files associated with this item. |