{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T23:06:23Z","timestamp":1778108783258,"version":"3.51.4"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4-6","license":[{"start":{"date-parts":[[2012,7,1]],"date-time":"2012-07-01T00:00:00Z","timestamp":1341100800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Form. Asp. Comput."],"published-print":{"date-parts":[[2012,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The algebra of programming (AoP) is a discipline for programming from specifications using relation algebra. Specification vagueness and nondeterminism are captured by relations. (Final) implementations are functions. Probabilistic functions are half way between relations and functions: they express the propensity, or likelihood of ambiguous, multiple outputs. This paper puts forward a basis for a linear algebra of programming (LAoP) extending standard AoP towards probabilistic functions. Because of the quantitative essence of these functions, the allegory of binary relations which supports the AoP has to be extended. We show that, if one restricts to discrete probability spaces, categories of matrices provide adequate support for the extension, while preserving the pointfree reasoning style typical of the AoP.<\/jats:p>","DOI":"10.1007\/s00165-012-0240-9","type":"journal-article","created":{"date-parts":[[2012,6,28]],"date-time":"2012-06-28T08:35:50Z","timestamp":1340872550000},"page":"433-458","source":"Crossref","is-referenced-by-count":18,"title":["Towards a linear algebra of programming"],"prefix":"10.1145","volume":"24","author":[{"given":"Jos\u00e9 N.","family":"Oliveira","sequence":"first","affiliation":[{"name":"High Assurance Software Lab\/INESC TEC and University of Minho, Braga, Portugal"}]}],"member":"320","reference":[{"key":"e_1_2_1_2_1_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511810800","volume-title":"Matrix algebra. In: Econometric exercises, vol 1","author":"Abadir KM","year":"2005"},{"key":"e_1_2_1_2_2_2","doi-asserted-by":"crossref","unstructured":"Andova S McIver A D\u2019Argenio PR Cuijpers PJL Markovski J Morgan C N\u00fa\u00f1ez M (eds) (2009) Proceedings first workshop on quantitative formal methods: theory and applications. In: EPTCS vol 13","DOI":"10.4204\/EPTCS.13.0"},{"key":"e_1_2_1_2_3_2","unstructured":"Backhouse RC (2004) Mathematics of program construction. University of Nottingham. Draft of book in preparation 608 p"},{"key":"e_1_2_1_2_4_2","volume-title":"Algebra of programming. Series in Computer Science","author":"Bird R","year":"1997"},{"key":"e_1_2_1_2_5_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00122683"},{"key":"e_1_2_1_2_6_2","unstructured":"Baroni M Zamparelli R (2010) Nouns are vectors adjectives are matrices: representing adjective-noun constructions in semantic space. In: Association for Computational Linguistics Proceedings EMNLP \u201910 Morristown NJ USA pp 1183\u20131193"},{"key":"e_1_2_1_2_7_2","volume-title":"Regular algebra and finite machines","author":"Conway JH","year":"1971"},{"issue":"1","key":"e_1_2_1_2_8_2","first-page":"345","article-title":"Mathematical foundations for a compositional distributed model of meaning","volume":"36","author":"Coecke B","year":"2010","journal-title":"Linguist Anal"},{"key":"e_1_2_1_2_9_2","doi-asserted-by":"crossref","unstructured":"Distefano S Longo F Scarpa M (2010) Availability assessment of HA standby redundant clusters. In: 29th IEEE international symposium on reliable distributed systems","DOI":"10.1109\/SRDS.2010.37"},{"key":"e_1_2_1_2_10_2","doi-asserted-by":"publisher","DOI":"10.1017\/S0956796805005721"},{"key":"e_1_2_1_2_11_2","doi-asserted-by":"publisher","DOI":"10.5555\/558662"},{"key":"e_1_2_1_2_12_2","volume-title":"In: Mathematical library, vol 39","author":"Freyd PJ","year":"1990"},{"key":"e_1_2_1_2_13_2","doi-asserted-by":"crossref","unstructured":"Gibbons J Hinze R (2011) Just do it: simple monadic equational reasoning. In: Proceedings of the 16th ACM SIGPLAN international conference on Functional programming ICFP\u201911 New York NY USA 2011. ACM New York pp 2\u201314","DOI":"10.1145\/2034773.2034777"},{"key":"e_1_2_1_2_14_2","doi-asserted-by":"crossref","unstructured":"Gibbons J Hutton G Altenkirch T (2001) When is a function a fold or an unfold? Electron Notes Theor Comput Sci 44(1)","DOI":"10.1016\/S1571-0661(04)80906-X"},{"key":"e_1_2_1_2_15_2","unstructured":"Gibbons J (1997) Conditionals in distributive categories. Technical Report CMS-TR-97-01 School of Computing and Mathematical Sciences Oxford Brookes University"},{"key":"e_1_2_1_2_16_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00165-010-0157-0"},{"key":"e_1_2_1_2_17_2","unstructured":"Hoogendijk P (1997) A generic theory of data types. PhD thesis University of Eindhoven The Netherlands"},{"key":"e_1_2_1_2_18_2","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0255(99)00017-1"},{"key":"e_1_2_1_2_19_2","unstructured":"Kemeny JG Snell JL (1960) Finite Markov chains. Springer Berlin (1976 originally printed by Van Nostrand Princeton)"},{"key":"e_1_2_1_2_20_2","doi-asserted-by":"crossref","unstructured":"Latouche G Ramaswami V (1999) Introduction to matrix analytic methods in stochastic modeling. ASA-SIAM","DOI":"10.1137\/1.9780898719734"},{"key":"e_1_2_1_2_21_2","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(91)90030-6"},{"key":"e_1_2_1_2_22_2","volume-title":"Conceptual mathematics: a first introduction to categories","author":"Lawvere B","year":"1997"},{"key":"e_1_2_1_2_23_2","volume-title":"In: Graduate texts in mathematics, vol 5","author":"MacLane S","year":"1998"},{"key":"e_1_2_1_2_24_2","unstructured":"Macedo H (2012) Matrices as arrows\u2014why categories of matrices matter. PhD thesis University of Minho (submitted)"},{"key":"e_1_2_1_2_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF00370681"},{"key":"e_1_2_1_2_26_2","unstructured":"MacLane S Birkhoff G (1999) Algebra. AMS Chelsea"},{"key":"e_1_2_1_2_27_2","unstructured":"Mu SC Bird R (2001) Quantum functional programming 2001. 2nd Asian workshop on programming languages and systems KAIST Dajeaon Korea December 17\u201318"},{"key":"e_1_2_1_2_28_2","doi-asserted-by":"crossref","unstructured":"McIver A Cohen E Morgan C (2006) Using probabilistic Kleene algebra for protocol verification. In: Schmidt R (ed) Relations and Kleene algebra in computer science. LNCS vol 4136. Springer Berlin pp 296\u2013310","DOI":"10.1007\/11828563_20"},{"key":"e_1_2_1_2_29_2","volume-title":"In: Monographs in computer science","author":"McIver A","year":"2005"},{"key":"e_1_2_1_2_30_2","doi-asserted-by":"crossref","unstructured":"Macedo HD Oliveira JN (2010) Matrices as Arrows! A biproduct approach to typed linear algebra. In: MPC\u201910. LNCS vol 6120. Springer Berlin pp 271\u2013287","DOI":"10.1007\/978-3-642-13321-3_16"},{"key":"e_1_2_1_2_31_2","unstructured":"Macedo HD Oliveira JN (2011) Do the middle letters of \u201cOLAP\u201d stand for linear algebra (\u201cLA\u201d)? Technical Report TR- HASLab:04:2011 INESC TEC and University of Minho Gualtar Campus Braga"},{"key":"e_1_2_1_2_32_2","doi-asserted-by":"crossref","unstructured":"Macedo HD Oliveira JN (2011) Towards linear algebras of components. In: FACS 2010. LNCS vol 6921. Springer Berlin pp 300\u2013303","DOI":"10.1007\/978-3-642-27269-1_20"},{"key":"e_1_2_1_2_33_2","doi-asserted-by":"publisher","DOI":"10.5555\/95423"},{"key":"e_1_2_1_2_34_2","unstructured":"Oliveira JN (2011) A look at the (linear) algebra of probabilistic functions 2011. Contribution to the QAIS Start-up Workshop celebrating IBM-Portugal Scientific Prize 2010 Braga 17th October"},{"key":"e_1_2_1_2_35_2","doi-asserted-by":"crossref","unstructured":"Pratt V (1992) Origins of the calculus of binary relations. In: Proceedings of the 7th annual IEEE symposium on logic in computer science Santa Cruz CA IEEE Comp. Soc pp 248\u2013254","DOI":"10.1109\/LICS.1992.185537"},{"key":"e_1_2_1_2_36_2","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195367898.001.0001","volume-title":"The Monty Hall problem: the remarkable story of math\u2019s most contentious brain teaser","author":"Rosenhouse J","year":"2009"},{"key":"e_1_2_1_2_37_2","volume-title":"Matrix algebra and its applications to statistics and econometrics","author":"Rao CR","year":"1998"},{"key":"e_1_2_1_2_38_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.ic.2010.09.007"},{"key":"e_1_2_1_2_39_2","volume-title":"Relational mathematics. Number 132 in Encyclopedia of Mathematics and its Applications","author":"Schmidt G","year":"2010"},{"key":"e_1_2_1_2_40_2","unstructured":"SQIG-Group (2011) LAP: linear algebra of bounded resources programs. IT & Tech. Univ. Lisbon"},{"key":"e_1_2_1_2_41_2","unstructured":"Sokolova A (2005) Coalgebraic analysis of probabilistic systems. Ph.D. dissertation Tech. Univ. Eindhoven Eindhoven The Netherlands"},{"key":"e_1_2_1_2_42_2","unstructured":"Sernadas A Ramos J Mateus P (2008) Linear algebra techniques for deciding the correctness of probabilistic programs with bounded resources. Technical report SQIG-IT and IST-TU Lisbon 1049-001 Lisboa Portugal 2008. Short paper presented at LPAR 2008 Doha Qatar. November 22\u201327"},{"key":"e_1_2_1_2_43_2","doi-asserted-by":"crossref","unstructured":"Takai T Furusawa H (2006) Monodic tree Kleene algebra. In: Schmidt R (ed) Relations and Kleene algebra in computer science. Lecture notes in computer science vol 4136. Springer Berlin pp 402\u2013416","DOI":"10.1007\/11828563_27"},{"key":"e_1_2_1_2_44_2","doi-asserted-by":"crossref","unstructured":"Trcka N (2009) Strong weak and branching bisimulation for transition systems and Markov reward chains: a unifying matrix approach. In: Proc. first workshop on quantitative formal methods: theory and applications EPTCS vol 13. pp 55\u201365","DOI":"10.4204\/EPTCS.13.5"},{"key":"e_1_2_1_2_45_2","unstructured":"Voas J McGraw G (1997) Software fault injection: innoculating programs against errors. Wiley New York 416 p"},{"key":"e_1_2_1_2_46_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.fss.2008.12.008"}],"container-title":["Formal Aspects of Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00165-012-0240-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00165-012-0240-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1007\/s00165-012-0240-9","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,4,26]],"date-time":"2024-04-26T05:21:27Z","timestamp":1714108887000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1007\/s00165-012-0240-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,7]]},"references-count":46,"journal-issue":{"issue":"4-6","published-print":{"date-parts":[[2012,7]]}},"alternative-id":["10.1007\/s00165-012-0240-9"],"URL":"https:\/\/doi.org\/10.1007\/s00165-012-0240-9","relation":{},"ISSN":["0934-5043","1433-299X"],"issn-type":[{"value":"0934-5043","type":"print"},{"value":"1433-299X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2012,7]]}}}