Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Computing the boolean product of two n × n boolean matrices using o(N2) mechanical operations

Lingas, Andrzej LU and Persson, Mia LU (2020) In International Journal of Unconventional Computing 15(3). p.225-236
Abstract

We study the problem of determining the Boolean product of two n × n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n2 ) operations are sufficient to compute the product in this model.

Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Boolean matrix multiplication, Boolean matrix-vector multiplication, Mechanical computing, Time complexity
in
International Journal of Unconventional Computing
volume
15
issue
3
pages
12 pages
publisher
Old City Publishing
external identifiers
  • scopus:85090024222
ISSN
1548-7199
language
English
LU publication?
yes
id
8b48549a-5ccc-4c57-8ad6-e4ec61ee2339
alternative location
https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-15-number-3-2020/ijuc-15-3-p-225-236/
date added to LUP
2020-09-25 08:18:46
date last changed
2022-04-19 01:00:29
@article{8b48549a-5ccc-4c57-8ad6-e4ec61ee2339,
  abstract     = {{<p>We study the problem of determining the Boolean product of two n × n Boolean matrices in an unconventional computational model allowing for mechanical operations. We show that O(n<sup>2</sup> ) operations are sufficient to compute the product in this model.</p>}},
  author       = {{Lingas, Andrzej and Persson, Mia}},
  issn         = {{1548-7199}},
  keywords     = {{Boolean matrix multiplication; Boolean matrix-vector multiplication; Mechanical computing; Time complexity}},
  language     = {{eng}},
  month        = {{01}},
  number       = {{3}},
  pages        = {{225--236}},
  publisher    = {{Old City Publishing}},
  series       = {{International Journal of Unconventional Computing}},
  title        = {{Computing the boolean product of two n × n boolean matrices using o(N<sup>2</sup>) mechanical operations}},
  url          = {{https://www.oldcitypublishing.com/journals/ijuc-home/ijuc-issue-contents/ijuc-volume-15-number-3-2020/ijuc-15-3-p-225-236/}},
  volume       = {{15}},
  year         = {{2020}},
}