diff --git a/metadata/authors.toml b/metadata/authors.toml --- a/metadata/authors.toml +++ b/metadata/authors.toml @@ -1,7407 +1,7427 @@ [abdulaziz] name = "Mohammad Abdulaziz" [abdulaziz.emails] [abdulaziz.emails.abdulaziz_email] user = [ "mohammad", "abdulaziz", ] host = [ "in", "tum", "de", ] [abdulaziz.emails.abdulaziz_email1] user = [ "mohammad", "abdulaziz8", ] host = [ "gmail", "com", ] [abdulaziz.homepages] abdulaziz_homepage = "http://home.in.tum.de/~mansour/" [adelsberger] name = "Stephan Adelsberger" [adelsberger.emails] [adelsberger.emails.adelsberger_email] user = [ "stvienna", ] host = [ "gmail", "com", ] [adelsberger.homepages] adelsberger_homepage = "http://nm.wu.ac.at/nm/sadelsbe" [aehlig] name = "Klaus Aehlig" [aehlig.emails] [aehlig.homepages] aehlig_homepage = "http://www.linta.de/~aehlig/" [aissat] name = "Romain Aissat" [aissat.emails] [aissat.homepages] [amani] name = "Sidney Amani" [amani.emails] [amani.emails.amani_email] user = [ "sidney", "amani", ] host = [ "data61", "csiro", "au", ] [amani.homepages] [ammer] name = "Thomas Ammer" [ammer.emails] [ammer.emails.ammer_email] user = [ "thomas", "ammer", ] host = [ "tum", "de", ] [ammer.homepages] [andreka] name = "Hajnal Andreka" [andreka.emails] [andreka.homepages] andreka_homepage = "https://renyi.hu/en/researchers/hajnal-andreka" [andronick] name = "June Andronick" [andronick.emails] [andronick.homepages] [aransay] name = "Jesús Aransay" [aransay.emails] [aransay.emails.aransay_email] user = [ "jesus-maria", "aransay", ] host = [ "unirioja", "es", ] [aransay.homepages] aransay_homepage = "https://www.unirioja.es/cu/jearansa" [argyraki] name = "Angeliki Koutsoukou-Argyraki" [argyraki.emails] [argyraki.emails.argyraki_email] user = [ "ak2110", ] host = [ "cam", "ac", "uk", ] [argyraki.homepages] argyraki_homepage = "https://www.cl.cam.ac.uk/~ak2110/" argyraki_homepage2 = "https://www.cst.cam.ac.uk/people/ak2110" [armstrong] name = "Alasdair Armstrong" [armstrong.emails] [armstrong.homepages] [aspinall] name = "David Aspinall" [aspinall.emails] [aspinall.homepages] aspinall_homepage = "http://homepages.inf.ed.ac.uk/da/" [ausaf] name = "Fahad Ausaf" [ausaf.emails] [ausaf.homepages] ausaf_homepage = "http://kcl.academia.edu/FahadAusaf" [avigad] name = "Jeremy Avigad" [avigad.emails] [avigad.emails.avigad_email] user = [ "avigad", ] host = [ "cmu", "edu", ] [avigad.homepages] avigad_homepage = "http://www.andrew.cmu.edu/user/avigad/" [back] name = "Ralph-Johan Back" [back.emails] [back.homepages] back_homepage = "http://users.abo.fi/Ralph-Johan.Back/" [baksys] name = "Mantas Bakšys" [baksys.emails] [baksys.emails.baksys_email] user = [ "mb2412", ] host = [ "cam", "ac", "uk", ] [baksys.homepages] baksys_homepage = "https://github.com/MantasBaksys" [balbach] name = "Frank J. Balbach" [balbach.emails] [balbach.emails.balbach_email] user = [ "frank-balbach", ] host = [ "gmx", "de", ] [balbach.homepages] [ballarin] name = "Clemens Ballarin" [ballarin.emails] [ballarin.emails.ballarin_email] user = [ "ballarin", ] host = [ "in", "tum", "de", ] [ballarin.homepages] ballarin_homepage = "http://www21.in.tum.de/~ballarin/" [barsotti] name = "Damián Barsotti" [barsotti.emails] [barsotti.homepages] barsotti_homepage = "http://www.cs.famaf.unc.edu.ar/~damian/" [bauer] name = "Gertrud Bauer" [bauer.emails] [bauer.homepages] [bauereiss] name = "Thomas Bauereiss" [bauereiss.emails] [bauereiss.emails.bauereiss_email] user = [ "thomas", ] host = [ "bauereiss", "name", ] [bauereiss.homepages] [bayer] name = "Jonas Bayer" [bayer.emails] [bayer.emails.bayer_email] user = [ "jonas", "bayer999", ] host = [ "gmail", "com", ] [bayer.homepages] [becker] name = "Heiko Becker" [becker.emails] [becker.emails.becker_email] user = [ "hbecker", ] host = [ "mpi-sws", "org", ] [becker.homepages] [beeren] name = "Joel Beeren" [beeren.emails] [beeren.homepages] [bella] name = "Giampaolo Bella" [bella.emails] [bella.emails.bella_email] user = [ "giamp", ] host = [ "dmi", "unict", "it", ] [bella.homepages] bella_homepage = "http://www.dmi.unict.it/~giamp/" [bengtson] name = "Jesper Bengtson" [bengtson.emails] [bengtson.homepages] bengtson_homepage = "http://www.itu.dk/people/jebe" [bentkamp] name = "Alexander Bentkamp" [bentkamp.emails] [bentkamp.emails.bentkamp_email] user = [ "bentkamp", ] host = [ "gmail", "com", ] [bentkamp.emails.bentkamp_email1] user = [ "a", "bentkamp", ] host = [ "vu", "nl", ] [bentkamp.homepages] bentkamp_homepage = "https://www.cs.vu.nl/~abp290/" [benzmueller] name = "Christoph Benzmüller" [benzmueller.emails] [benzmueller.emails.benzmueller_email] user = [ "c", "benzmueller", ] host = [ "gmail", "com", ] [benzmueller.emails.benzmueller_email1] user = [ "c", "benzmueller", ] host = [ "fu-berlin", "de", ] [benzmueller.homepages] benzmueller_homepage = "http://christoph-benzmueller.de" benzmueller_homepage1 = "http://page.mi.fu-berlin.de/cbenzmueller/" [beresford] name = "Alastair R. Beresford" [beresford.emails] [beresford.emails.beresford_email] user = [ "arb33", ] host = [ "cam", "ac", "uk", ] [beresford.homepages] [berghofer] name = "Stefan Berghofer" [berghofer.emails] [berghofer.emails.berghofer_email] user = [ "berghofe", ] host = [ "in", "tum", "de", ] [berghofer.homepages] berghofer_homepage = "http://www.in.tum.de/~berghofe" [beringer] name = "Lennart Beringer" [beringer.emails] [beringer.emails.beringer_email] user = [ "lennart", "beringer", ] host = [ "ifi", "lmu", "de", ] [beringer.homepages] [bharadwaj] name = "Abhijith Bharadwaj" [bharadwaj.emails] [bharadwaj.homepages] [bhatt] name = "Bhargav Bhatt" [bhatt.emails] [bhatt.emails.bhatt_email] user = [ "bhargav", "bhatt", ] host = [ "inf", "ethz", "ch", ] [bhatt.homepages] [biendarra] name = "Julian Biendarra" [biendarra.emails] [biendarra.homepages] [bisping] name = "Benjamin Bisping" [bisping.emails] [bisping.emails.bisping_email] user = [ "benjamin", "bisping", ] host = [ "campus", "tu-berlin", "de", ] [bisping.homepages] [blanchette] name = "Jasmin Christian Blanchette" [blanchette.emails] [blanchette.emails.blanchette_email] user = [ "jasmin", "blanchette", ] host = [ "gmail", "com", ] [blanchette.emails.blanchette_email1] user = [ "j", "c", "blanchette", ] host = [ "vu", "nl", ] [blanchette.homepages] blanchette_homepage = "http://www21.in.tum.de/~blanchet" blanchette_homepage1 = "https://www.cs.vu.nl/~jbe248/" [blasum] name = "Holger Blasum" [blasum.emails] [blasum.emails.blasum_email] user = [ "holger", "blasum", ] host = [ "sysgo", "com", ] [blasum.homepages] [blumson] name = "Ben Blumson" [blumson.emails] [blumson.emails.blumson_email] user = [ "benblumson", ] host = [ "gmail", "com", ] [blumson.homepages] blumson_homepage = "https://philpeople.org/profiles/ben-blumson" [bockenek] name = "Joshua Bockenek" [bockenek.emails] [bockenek.homepages] [boehme] name = "Sascha Böhme" [boehme.emails] [boehme.emails.boehme_email] user = [ "boehmes", ] host = [ "in", "tum", "de", ] [boehme.homepages] boehme_homepage = "http://www21.in.tum.de/~boehmes/" [bohrer] name = "Rose Bohrer" [bohrer.emails] [bohrer.emails.bohrer_email] user = [ "rose", "bohrer", "cs", ] host = [ "gmail", "com", ] [bohrer.homepages] [bordg] name = "Anthony Bordg" [bordg.emails] [bordg.emails.bordg_email] user = [ "apdb3", ] host = [ "cam", "ac", "uk", ] [bordg.homepages] bordg_homepage = "https://sites.google.com/site/anthonybordg/" [borgstroem] name = "Johannes Borgström" [borgstroem.emails] [borgstroem.emails.borgstroem_email] user = [ "johannes", "borgstrom", ] host = [ "it", "uu", "se", ] [borgstroem.homepages] [bortin] name = "Maksym Bortin" [bortin.emails] [bortin.emails.bortin_email] user = [ "maksym", "bortin", ] host = [ "nicta", "com", "au", ] [bortin.emails.bortin_email1] user = [ "mbortin", ] host = [ "gmail", "com", ] [bortin.homepages] [bottesch] name = "Ralph Bottesch" [bottesch.emails] [bottesch.emails.bottesch_email] user = [ "ralph", "bottesch", ] host = [ "uibk", "ac", "at", ] [bottesch.homepages] bottesch_homepage = "http://cl-informatik.uibk.ac.at/users/bottesch/" [boulanger] name = "Frédéric Boulanger" [boulanger.emails] [boulanger.emails.boulanger_email] user = [ "frederic", "boulanger", ] host = [ "centralesupelec", "fr", ] [boulanger.homepages] [bourke] name = "Timothy Bourke" [bourke.emails] [bourke.emails.bourke_email] user = [ "tim", ] host = [ "tbrk", "org", ] [bourke.homepages] bourke_homepage = "http://www.tbrk.org" [boutry] name = "Pierre Boutry" [boutry.emails] [boutry.emails.boutry_email] user = [ "boutry", ] host = [ "unistra", "fr", ] [boutry.homepages] [boyton] name = "Andrew Boyton" [boyton.emails] [boyton.emails.boyton_email] user = [ "andrew", "boyton", ] host = [ "nicta", "com", "au", ] [boyton.homepages] [bracevac] name = "Oliver Bračevac" [bracevac.emails] [bracevac.emails.bracevac_email] user = [ "bracevac", ] host = [ "st", "informatik", "tu-darmstadt", "de", ] [bracevac.homepages] [brandt] name = "Felix Brandt" [brandt.emails] [brandt.homepages] brandt_homepage = "http://dss.in.tum.de/staff/brandt.html" [breitner] name = "Joachim Breitner" [breitner.emails] [breitner.emails.breitner_email] user = [ "mail", ] host = [ "joachim-breitner", "de", ] [breitner.emails.breitner_email1] user = [ "joachim", ] host = [ "cis", "upenn", "edu", ] [breitner.homepages] breitner_homepage = "http://pp.ipd.kit.edu/~breitner" [brien] name = "Nicolas Robinson-O'Brien" [brien.emails] [brien.homepages] [brinkop] name = "Hauke Brinkop" [brinkop.emails] [brinkop.emails.brinkop_email] user = [ "hauke", "brinkop", ] host = [ "googlemail", "com", ] [brinkop.homepages] [brodmann] name = "Paul-David Brodmann" [brodmann.emails] [brodmann.emails.brodmann_email] user = [ "p", "brodmann", ] host = [ "tu-berlin", "de", ] [brodmann.homepages] [brucker] name = "Achim D. Brucker" [brucker.emails] [brucker.emails.brucker_email] user = [ "a", "brucker", ] host = [ "exeter", "ac", "uk", ] [brucker.emails.brucker_email1] user = [ "brucker", ] host = [ "spamfence", "net", ] [brucker.emails.brucker_email2] user = [ "adbrucker", ] host = [ "0x5f", "org", ] [brucker.homepages] brucker_homepage = "https://www.brucker.ch/" [bruegger] name = "Lukas Brügger" [bruegger.emails] [bruegger.emails.bruegger_email] user = [ "lukas", "a", "bruegger", ] host = [ "gmail", "com", ] [bruegger.homepages] [brun] name = "Matthias Brun" [brun.emails] [brun.emails.brun_email] user = [ "matthias", "brun", ] host = [ "inf", "ethz", "ch", ] [brun.homepages] [brunner] name = "Julian Brunner" [brunner.emails] [brunner.emails.brunner_email] user = [ "brunnerj", ] host = [ "in", "tum", "de", ] [brunner.homepages] brunner_homepage = "http://www21.in.tum.de/~brunnerj/" [bulwahn] name = "Lukas Bulwahn" [bulwahn.emails] [bulwahn.emails.bulwahn_email] user = [ "lukas", "bulwahn", ] host = [ "gmail", "com", ] [bulwahn.homepages] [butler] name = "David Butler" [butler.emails] [butler.emails.butler_email] user = [ "dbutler", ] host = [ "turing", "ac", "uk", ] [butler.homepages] butler_homepage = "https://www.turing.ac.uk/people/doctoral-students/david-butler" [buyse] name = "Maxime Buyse" [buyse.emails] [buyse.emails.buyse_email] user = [ "maxime", "buyse", ] host = [ "polytechnique", "edu", ] [buyse.homepages] [caballero] name = "José Manuel Rodríguez Caballero" [caballero.emails] [caballero.emails.caballero_email] user = [ "jose", "manuel", "rodriguez", "caballero", ] host = [ "ut", "ee", ] [caballero.homepages] caballero_homepage = "https://josephcmac.github.io/" [caminati] name = "Marco B. Caminati" [caminati.emails] [caminati.homepages] [campo] name = "Alejandro del Campo" [campo.emails] [campo.emails.campo_email] user = [ "alejandro", "del-campo", ] host = [ "alum", "unirioja", "es", ] [campo.homepages] [chaieb] name = "Amine Chaieb" [chaieb.emails] [chaieb.homepages] [chapman] name = "Peter Chapman" [chapman.emails] [chapman.emails.chapman_email] user = [ "pc", ] host = [ "cs", "st-andrews", "ac", "uk", ] [chapman.homepages] [chen] name = "L. Chen" [chen.emails] [chen.homepages] [chevalier] name = "Loïc Chevalier" [chevalier.emails] [chevalier.homepages] [christfort] name = "Axel Christfort" [christfort.emails] [christfort.emails.christfort_email] user = [ "axel", ] host = [ "di", "ku", "dk", ] [christfort.homepages] [clouston] name = "Ranald Clouston" [clouston.emails] [clouston.emails.clouston_email] user = [ "ranald", "clouston", ] host = [ "cs", "au", "dk", ] [clouston.homepages] [cock] name = "David Cock" [cock.emails] [cock.emails.cock_email] user = [ "david", "cock", ] host = [ "nicta", "com", "au", ] [cock.homepages] [coghetto] name = "Roland Coghetto" [coghetto.emails] [coghetto.emails.coghetto_email] user = [ "roland_coghetto", ] host = [ "hotmail", "com", ] [coghetto.homepages] [coglio] name = "Alessandro Coglio" [coglio.emails] [coglio.emails.coglio_email] user = [ "coglio", ] host = [ "kestrel", "edu", ] [coglio.homepages] coglio_homepage = "http://www.kestrel.edu/~coglio" [cohen] name = "Ernie Cohen" [cohen.emails] [cohen.emails.cohen_email] user = [ "ecohen", ] host = [ "amazon", "com", ] [cohen.homepages] [cordwell] name = "Katherine Kosaian" [cordwell.emails] [cordwell.emails.cordwell_email] user = [ "kcordwel", ] host = [ "cs", "cmu", "edu", ] [cordwell.homepages] cordwell_homepage = "https://www.cs.cmu.edu/~kcordwel/" [cousin] name = "Marie Cousin" [cousin.emails] [cousin.emails.cousin_email] user = [ "marie", "cousin", ] host = [ "grenoble-inp", "org", ] [cousin.homepages] [cremer] name = "Nils Cremer" [cremer.emails] [cremer.emails.cremer_email] user = [ "nils", "cremer", ] host = [ "tum", "de", ] [cremer.homepages] [crighton] name = "Aaron Crighton" [crighton.emails] [crighton.emails.crighton_email] user = [ "crightoa", ] host = [ "mcmaster", "ca", ] [crighton.homepages] [dalvit] name = "Christian Dalvit" [dalvit.emails] [dalvit.emails.dalvit_email] user = [ "chris", "dalvit", ] host = [ "gmail", "com", ] [dalvit.homepages] [danilkin] name = "Anton Danilkin" [danilkin.emails] [danilkin.emails.danilkin_email] user = [ "anton", "danilkin", ] host = [ "ens", "psl", "eu", ] [danilkin.homepages] [dardinier] name = "Thibault Dardinier" [dardinier.emails] [dardinier.emails.dardinier_email] user = [ "thibault", "dardinier", ] host = [ "inf", "ethz", "ch", ] [dardinier.homepages] dardinier_homepage = "https://dardinier.me/" [david] name = "Marco David" [david.emails] [david.emails.david_email] user = [ "marco", "david", ] host = [ "hotmail", "de", ] [david.homepages] [debois] name = "Søren Debois" [debois.emails] [debois.homepages] [debrat] name = "Henri Debrat" [debrat.emails] [debrat.emails.debrat_email] user = [ "henri", "debrat", ] host = [ "loria", "fr", ] [debrat.homepages] [decova] name = "Sára Decova" [decova.emails] [decova.homepages] [delemazure] name = "Théo Delemazure" [delemazure.emails] [delemazure.homepages] delemazure_homepage = "https://theo.delemazure.fr/" [demeulemeester] name = "Tom Demeulemeester" [demeulemeester.emails] [demeulemeester.homepages] demeulemeester_homepage = "https://www.kuleuven.be/wieiswie/en/person/00131528" [derrick] name = "John Derrick" [derrick.emails] [derrick.emails.derrick_email] user = [ "j", "derrick", ] host = [ "sheffield", "ac", "uk", ] [derrick.homepages] [desharnais] name = "Martin Desharnais" [desharnais.emails] [desharnais.emails.desharnais_email] user = [ "martin", "desharnais", ] host = [ "unibw", "de", ] [desharnais.emails.desharnais_email1] user = [ "desharnais", ] host = [ "mpi-inf", "mpg", "de", ] [desharnais.homepages] desharnais_homepage = "https://martin.desharnais.me" [diaz] name = "Javier Díaz" [diaz.emails] [diaz.emails.diaz_email] user = [ "javier", "diaz", "manzi", ] host = [ "gmail", "com", ] [diaz.homepages] [diekmann] name = "Cornelius Diekmann" [diekmann.emails] [diekmann.emails.diekmann_email] user = [ "diekmann", ] host = [ "net", "in", "tum", "de", ] [diekmann.homepages] diekmann_homepage = "http://net.in.tum.de/~diekmann" [dirix] name = "Stefan Dirix" [dirix.emails] [dirix.homepages] [dittmann] name = "Christoph Dittmann" [dittmann.emails] [dittmann.emails.dittmann_email] user = [ "isabelle", ] host = [ "christoph-d", "de", ] [dittmann.homepages] dittmann_homepage = "http://logic.las.tu-berlin.de/Members/Dittmann/" [divason] name = "Jose Divasón" [divason.emails] [divason.emails.divason_email] user = [ "jose", "divason", ] host = [ "unirioja", "es", ] [divason.homepages] divason_homepage = "https://www.unirioja.es/cu/jodivaso/" [doczkal] name = "Christian Doczkal" [doczkal.emails] [doczkal.emails.doczkal_email] user = [ "doczkal", ] host = [ "ps", "uni-saarland", "de", ] [doczkal.homepages] [dongol] name = "Brijesh Dongol" [dongol.emails] [dongol.emails.dongol_email] user = [ "brijesh", "dongol", ] host = [ "brunel", "ac", "uk", ] [dongol.homepages] [doty] name = "Matthew Doty" [doty.emails] [doty.emails.doty_email] user = [ "matt", ] host = [ "w-d", "org", ] [doty.homepages] [dubut] name = "Jérémy Dubut" [dubut.emails] [dubut.emails.dubut_email] user = [ "dubut", ] host = [ "nii", "ac", "jp", ] [dubut.emails.dubut_email1] user = [ "jeremy", "dubut", ] host = [ "aist", "go", "jp", ] [dubut.homepages] dubut_homepage = "http://group-mmm.org/~dubut/" [dunaev] name = "Georgy Dunaev" [dunaev.emails] [dunaev.emails.dunaev_email] user = [ "georgedunaev", ] host = [ "gmail", "com", ] [dunaev.homepages] [dyckhoff] name = "Roy Dyckhoff" [dyckhoff.emails] [dyckhoff.homepages] dyckhoff_homepage = "https://rd.host.cs.st-andrews.ac.uk" [eberl] name = "Manuel Eberl" orcid = "0000-0002-4263-6571" [eberl.emails] [eberl.emails.eberl_email] user = [ "manuel", ] host = [ "pruvisto", "org", ] [eberl.emails.eberl_email1] user = [ "manuel", "eberl", ] host = [ "tum", "de", ] [eberl.emails.eberl_email2] user = [ "manuel", "eberl", ] host = [ "uibk", "ac", "at", ] [eberl.homepages] eberl_homepage = "https://pruvisto.org/" eberl_homepage2 = "https://www.in.tum.de/~eberlm" [echenim] name = "Mnacho Echenim" [echenim.emails] [echenim.emails.echenim_email] user = [ "mnacho", "echenim", ] host = [ "univ-grenoble-alpes", "fr", ] [echenim.homepages] echenim_homepage = "https://lig-membres.imag.fr/mechenim/" [edmonds] name = "Chelsea Edmonds" [edmonds.emails] [edmonds.emails.edmonds_email] user = [ "cle47", ] host = [ "cam", "ac", "uk", ] [edmonds.homepages] edmonds_homepage = "https://www.cst.cam.ac.uk/people/cle47" [engelhardt] name = "Kai Engelhardt" [engelhardt.emails] [engelhardt.homepages] [eriksson] name = "Lars-Henrik Eriksson" [eriksson.emails] [eriksson.emails.eriksson_email] user = [ "lhe", ] host = [ "it", "uu", "se", ] [eriksson.homepages] [esparza] name = "Javier Esparza" [esparza.emails] [esparza.homepages] esparza_homepage = "https://www7.in.tum.de/~esparza/" [essmann] name = "Robin Eßmann" [essmann.emails] [essmann.emails.essmann_email] user = [ "robin", "essmann", ] host = [ "tum", "de", ] [essmann.homepages] [felgenhauer] name = "Bertram Felgenhauer" [felgenhauer.emails] [felgenhauer.emails.felgenhauer_email] user = [ "bertram", "felgenhauer", ] host = [ "uibk", "ac", "at", ] [felgenhauer.emails.felgenhauer_email1] user = [ "int-e", ] host = [ "gmx", "de", ] [felgenhauer.homepages] [feliachi] name = "Abderrahmane Feliachi" [feliachi.emails] [feliachi.emails.feliachi_email] user = [ "abderrahmane", "feliachi", ] host = [ "lri", "fr", ] [feliachi.homepages] [fell] name = "Julian Fell" [fell.emails] [fell.emails.fell_email] user = [ "julian", "fell", ] host = [ "uq", "net", "au", ] [fell.homepages] [fernandez] name = "Matthew Fernandez" [fernandez.emails] [fernandez.homepages] [fiedler] name = "Ben Fiedler" [fiedler.emails] [fiedler.emails.fiedler_email] user = [ "ben", "fiedler", ] host = [ "inf", "ethz", "ch", ] [fiedler.homepages] [fleuriot] name = "Jacques D. Fleuriot" [fleuriot.emails] [fleuriot.emails.fleuriot_email] user = [ "Jacques", "Fleuriot", ] host = [ "ed", "ac", "uk", ] [fleuriot.emails.fleuriot_email1] user = [ "jdf", ] host = [ "ed", "ac", "uk", ] [fleuriot.homepages] fleuriot_homepage = "https://www.inf.ed.ac.uk/people/staff/Jacques_Fleuriot.html" [fleury] name = "Mathias Fleury" [fleury.emails] [fleury.emails.fleury_email] user = [ "fleury", ] host = [ "mpi-inf", "mpg", "de", ] [fleury.emails.fleury_email1] user = [ "mathias", "fleury", ] host = [ "jku", "at", ] [fleury.homepages] fleury_homepage = "http://fmv.jku.at/fleury" [foster] name = "Michael Foster" [foster.emails] [foster.emails.foster_email] user = [ "m", "foster", ] host = [ "sheffield", "ac", "uk", ] [foster.homepages] [fosterj] name = "J. Nathan Foster" [fosterj.emails] [fosterj.homepages] fosterj_homepage = "http://www.cs.cornell.edu/~jnfoster/" [fosters] name = "Simon Foster" [fosters.emails] [fosters.emails.fosters_email] user = [ "simon", "foster", ] host = [ "york", "ac", "uk", ] [fosters.homepages] fosters_homepage = "https://www-users.cs.york.ac.uk/~simonf/" [fouillard] name = "Valentin Fouillard" [fouillard.emails] [fouillard.emails.fouillard_email] user = [ "valentin", "fouillard", ] host = [ "limsi", "fr", ] [fouillard.homepages] [friedrich] name = "Stefan Friedrich" [friedrich.emails] [friedrich.homepages] [from] name = "Asta Halkjær From" [from.emails] [from.emails.from_email] user = [ "ahfrom", ] host = [ "dtu", "dk", ] [from.homepages] from_homepage = "https://people.compute.dtu.dk/ahfrom/" [fuenmayor] name = "David Fuenmayor" [fuenmayor.emails] [fuenmayor.emails.fuenmayor_email] user = [ "davfuenmayor", ] host = [ "gmail", "com", ] [fuenmayor.homepages] [furusawa] name = "Hitoshi Furusawa" [furusawa.emails] [furusawa.homepages] furusawa_homepage = "http://www.sci.kagoshima-u.ac.jp/~furusawa/" [gammie] name = "Peter Gammie" [gammie.emails] [gammie.emails.gammie_email] user = [ "peteg42", ] host = [ "gmail", "com", ] [gammie.homepages] gammie_homepage = "http://peteg.org" [gao] name = "Xin Gao" [gao.emails] [gao.homepages] [gaudel] name = "Marie-Claude Gaudel" [gaudel.emails] [gaudel.emails.gaudel_email] user = [ "mcg", ] host = [ "lri", "fr", ] [gaudel.homepages] [gay] name = "Richard Gay" [gay.emails] [gay.emails.gay_email] user = [ "gay", ] host = [ "mais", "informatik", "tu-darmstadt", "de", ] [gay.homepages] [georgescu] name = "George Georgescu" [georgescu.emails] [georgescu.homepages] [gheri] name = "Lorenzo Gheri" [gheri.emails] [gheri.emails.gheri_email] user = [ "lor", "gheri", ] host = [ "gmail", "com", ] [gheri.homepages] [ghourabi] name = "Fadoua Ghourabi" [ghourabi.emails] [ghourabi.emails.ghourabi_email] user = [ "fadouaghourabi", ] host = [ "gmail", "com", ] [ghourabi.homepages] [gioiosa] name = "Gianpaolo Gioiosa" [gioiosa.emails] [gioiosa.homepages] [glabbeek] name = "Rob van Glabbeek" [glabbeek.emails] [glabbeek.homepages] glabbeek_homepage = "http://theory.stanford.edu/~rvg/" [gomes] name = "Victor B. F. Gomes" [gomes.emails] [gomes.emails.gomes_email] user = [ "victor", "gomes", ] host = [ "cl", "cam", "ac", "uk", ] [gomes.emails.gomes_email2] user = [ "victorborgesfg", ] host = [ "gmail", "com", ] [gomes.emails.gomes_email4] user = [ "vborgesferreiragomes1", ] host = [ "sheffield", "ac", "uk", ] [gomes.homepages] gomes_homepage = "http://www.dcs.shef.ac.uk/~victor" [gonzalez] name = "Edgar Gonzàlez" orcid = "0000-0002-9169-0769" [gonzalez.emails] [gonzalez.emails.gonzalez_email] user = [ "edgargip", ] host = [ "google", "com", ] [gonzalez.homepages] [gore] name = "Rajeev Gore" [gore.emails] [gore.emails.gore_email] user = [ "rajeev", "gore", ] host = [ "anu", "edu", "au", ] [gore.homepages] [gouezel] name = "Sebastien Gouezel" [gouezel.emails] [gouezel.emails.gouezel_email] user = [ "sebastien", "gouezel", ] host = [ "univ-rennes1", "fr", ] [gouezel.homepages] gouezel_homepage = "http://www.math.sciences.univ-nantes.fr/~gouezel/" [grechuk] name = "Bogdan Grechuk" [grechuk.emails] [grechuk.emails.grechuk_email] user = [ "grechukbogdan", ] host = [ "yandex", "ru", ] [grechuk.homepages] [grewe] name = "Sylvia Grewe" [grewe.emails] [grewe.emails.grewe_email] user = [ "grewe", ] host = [ "cs", "tu-darmstadt", "de", ] [grewe.homepages] [griebel] name = "Simon Griebel" [griebel.emails] [griebel.emails.griebel_email] user = [ "s", "griebel", ] host = [ "tum", "de", ] [griebel.homepages] [grov] name = "Gudmund Grov" [grov.emails] [grov.emails.grov_email] user = [ "ggrov", ] host = [ "inf", "ed", "ac", "uk", ] [grov.homepages] grov_homepage = "http://homepages.inf.ed.ac.uk/ggrov" [guerraoui] name = "Rachid Guerraoui" [guerraoui.emails] [guerraoui.emails.guerraoui_email] user = [ "rachid", "guerraoui", ] host = [ "epfl", "ch", ] [guerraoui.homepages] [guiol] name = "Hervé Guiol" [guiol.emails] [guiol.emails.guiol_email] user = [ "herve", "guiol", ] host = [ "univ-grenoble-alpes", "fr", ] [guiol.homepages] [gunther] name = "Emmanuel Gunther" [gunther.emails] [gunther.emails.gunther_email] user = [ "gunther", ] host = [ "famaf", "unc", "edu", "ar", ] [gunther.homepages] [gutkovas] name = "Ramunas Gutkovas" [gutkovas.emails] [gutkovas.emails.gutkovas_email] user = [ "ramunas", "gutkovas", ] host = [ "it", "uu", "se", ] [gutkovas.homepages] [guttmann] name = "Walter Guttmann" [guttmann.emails] [guttmann.emails.guttmann_email] user = [ "walter", "guttmann", ] host = [ "canterbury", "ac", "nz", ] [guttmann.homepages] guttmann_homepage = "https://www.cosc.canterbury.ac.nz/walter.guttmann/" [guzman] name = "Laura P. Gamboa Guzman" [guzman.emails] [guzman.emails.guzman_email] user = [ "lpgamboa", ] host = [ "iastate", "edu", ] [guzman.homepages] guzman_homepage = "https://sites.google.com/view/lpgamboa/home" [haftmann] name = "Florian Haftmann" [haftmann.emails] [haftmann.emails.haftmann_email] user = [ "florian", "haftmann", ] host = [ "informatik", "tu-muenchen", "de", ] [haftmann.homepages] haftmann_homepage = "http://isabelle.in.tum.de/~haftmann" [haslbeck] name = "Max W. Haslbeck" [haslbeck.emails] [haslbeck.emails.haslbeck_email] user = [ "maximilian", "haslbeck", ] host = [ "uibk", "ac", "at", ] [haslbeck.emails.haslbeck_email1] user = [ "haslbecm", ] host = [ "in", "tum", "de", ] [haslbeck.emails.haslbeck_email2] user = [ "max", "haslbeck", ] host = [ "gmx", "de", ] [haslbeck.homepages] haslbeck_homepage = "http://cl-informatik.uibk.ac.at/users/mhaslbeck/" [haslbeckm] name = "Maximilian P. L. Haslbeck" [haslbeckm.emails] [haslbeckm.emails.haslbeckm_email] user = [ "haslbema", ] host = [ "in", "tum", "de", ] [haslbeckm.homepages] haslbeckm_homepage = "http://in.tum.de/~haslbema/" [havle] name = "Oto Havle" [havle.emails] [havle.emails.havle_email] user = [ "oha", ] host = [ "sysgo", "com", ] [havle.homepages] [hayes] name = "Ian J. Hayes" [hayes.emails] [hayes.emails.hayes_email] user = [ "ian", "hayes", ] host = [ "itee", "uq", "edu", "au", ] [hayes.homepages] [he] name = "Yijun He" [he.emails] [he.emails.he_email] user = [ "yh403", ] host = [ "cam", "ac", "uk", ] [he.homepages] [heimes] name = "Lukas Heimes" [heimes.emails] [heimes.emails.heimes_email] user = [ "heimesl", ] host = [ "student", "ethz", "ch", ] [heimes.homepages] [helke] name = "Steffen Helke" [helke.emails] [helke.emails.helke_email] user = [ "helke", ] host = [ "cs", "tu-berlin", "de", ] [helke.homepages] [hellauer] name = "Fabian Hellauer" [hellauer.emails] [hellauer.emails.hellauer_email] user = [ "hellauer", ] host = [ "in", "tum", "de", ] [hellauer.homepages] [heller] name = "Armin Heller" [heller.emails] [heller.homepages] [henrio] name = "Ludovic Henrio" [henrio.emails] [henrio.emails.henrio_email] user = [ "Ludovic", "Henrio", ] host = [ "sophia", "inria", "fr", ] [henrio.homepages] [herzberg] name = "Michael Herzberg" [herzberg.emails] [herzberg.emails.herzberg_email] user = [ "mail", ] host = [ "michael-herzberg", "de", ] [herzberg.homepages] herzberg_homepage = "http://www.dcs.shef.ac.uk/cgi-bin/makeperson?M.Herzberg" [hess] name = "Andreas V. Hess" [hess.emails] [hess.emails.hess_email] user = [ "avhe", ] host = [ "dtu", "dk", ] [hess.emails.hess_email1] user = [ "andreasvhess", ] host = [ "gmail", "com", ] [hess.homepages] [hetzl] name = "Stefan Hetzl" [hetzl.emails] [hetzl.emails.hetzl_email] user = [ "hetzl", ] host = [ "logic", "at", ] [hetzl.homepages] hetzl_homepage = "http://www.logic.at/people/hetzl/" [hibon] name = "Quentin Hibon" [hibon.emails] [hibon.emails.hibon_email] user = [ "qh225", ] host = [ "cl", "cam", "ac", "uk", ] [hibon.homepages] [higgins] name = "Edward Higgins" [higgins.emails] [higgins.homepages] [hirata] name = "Michikazu Hirata" [hirata.emails] [hirata.emails.hirata_email] user = [ "hirata", "m", "ac", ] host = [ "m", "titech", "ac", "jp", ] [hirata.homepages] [hoefner] name = "Peter Höfner" [hoefner.emails] [hoefner.emails.hoefner_email] user = [ "peter", ] host = [ "hoefner-online", "de", ] [hoefner.homepages] hoefner_homepage = "http://www.hoefner-online.de/" [hoelzl] name = "Johannes Hölzl" [hoelzl.emails] [hoelzl.emails.hoelzl_email] user = [ "hoelzl", ] host = [ "in", "tum", "de", ] [hoelzl.homepages] hoelzl_homepage = "http://home.in.tum.de/~hoelzl" [hofmann] name = "Martin Hofmann" [hofmann.emails] [hofmann.homepages] hofmann_homepage = "http://www.tcs.informatik.uni-muenchen.de/~mhofmann" [hofmeier] name = "Paul Hofmeier" [hofmeier.emails] [hofmeier.emails.hofmeier_email] user = [ "paul", "hofmeier", ] host = [ "tum", "de", ] [hofmeier.homepages] [holub] name = "Štěpán Holub" [holub.emails] [holub.emails.holub_email] user = [ "holub", ] host = [ "karlin", "mff", "cuni", "cz", ] [holub.homepages] holub_homepage = "https://www2.karlin.mff.cuni.cz/~holub/" [hosking] name = "Tony Hosking" [hosking.emails] [hosking.homepages] hosking_homepage = "https://www.cs.purdue.edu/homes/hosking/" [hou] name = "Zhe Hou" [hou.emails] [hou.emails.hou_email] user = [ "zhe", "hou", ] host = [ "ntu", "edu", "sg", ] [hou.homepages] [hu] name = "Shuwei Hu" [hu.emails] [hu.emails.hu_email] user = [ "shuwei", "hu", ] host = [ "tum", "de", ] [hu.homepages] [huffman] name = "Brian Huffman" [huffman.emails] [huffman.emails.huffman_email] user = [ "huffman", ] host = [ "in", "tum", "de", ] [huffman.emails.huffman_email1] user = [ "brianh", ] host = [ "cs", "pdx", "edu", ] [huffman.homepages] huffman_homepage = "http://cs.pdx.edu/~brianh/" [hupel] name = "Lars Hupel" [hupel.emails] [hupel.emails.hupel_email] user = [ "lars", ] host = [ "hupel", "info", ] [hupel.homepages] hupel_homepage = "https://lars.hupel.info/" [ijbema] name = "Mark Ijbema" [ijbema.emails] [ijbema.emails.ijbema_email] user = [ "ijbema", ] host = [ "fmf", "nl", ] [ijbema.homepages] [immler] name = "Fabian Immler" [immler.emails] [immler.emails.immler_email] user = [ "immler", ] host = [ "in", "tum", "de", ] [immler.emails.immler_email1] user = [ "fimmler", ] host = [ "cs", "cmu", "edu", ] [immler.homepages] immler_homepage = "https://home.in.tum.de/~immler/" [israel] name = "Jonas Israel" [israel.emails] [israel.homepages] israel_homepage = "https://www.algo.tu-berlin.de/menue/people/jonas_israel/" [ito] name = "Yosuke Ito" [ito.emails] [ito.emails.ito_email] user = [ "glacier345", ] host = [ "gmail", "com", ] [ito.homepages] [iwama] name = "Fumiya Iwama" [iwama.emails] [iwama.emails.iwama_email] user = [ "d1623001", ] host = [ "s", "konan-u", "ac", "jp", ] [iwama.homepages] [jacobsen] name = "Frederik Krogsdal Jacobsen" [jacobsen.emails] [jacobsen.emails.jacobsen_email] user = [ "fkjac", ] host = [ "dtu", "dk", ] [jacobsen.homepages] jacobsen_homepage = "http://people.compute.dtu.dk/fkjac/" [jaskelioff] name = "Mauro Jaskelioff" [jaskelioff.emails] [jaskelioff.homepages] jaskelioff_homepage = "http://www.fceia.unr.edu.ar/~mauro/" [jaskolka] name = "Jason Jaskolka" [jaskolka.emails] [jaskolka.emails.jaskolka_email] user = [ "jason", "jaskolka", ] host = [ "carleton", "ca", ] [jaskolka.homepages] jaskolka_homepage = "https://carleton.ca/jaskolka/" [jensen] name = "Alexander Birch Jensen" [jensen.emails] [jensen.emails.jensen_email] user = [ "aleje", ] host = [ "dtu", "dk", ] [jensen.homepages] jensen_homepage = "https://people.compute.dtu.dk/aleje/" [jiang] name = "Nan Jiang" [jiang.emails] [jiang.emails.jiang_email] user = [ "nanjiang", ] host = [ "whu", "edu", "cn", ] [jiang.homepages] [jiangd] name = "Dongchen Jiang" [jiangd.emails] [jiangd.emails.jiangd_email] user = [ "dongchenjiang", ] host = [ "googlemail", "com", ] [jiangd.homepages] [joosten] name = "Sebastiaan J. C. Joosten" [joosten.emails] [joosten.emails.joosten_email] user = [ "sebastiaan", "joosten", ] host = [ "uibk", "ac", "at", ] [joosten.emails.joosten_email1] user = [ "sjcjoosten", ] host = [ "gmail", "com", ] [joosten.emails.joosten_email2] user = [ "s", "j", "c", "joosten", ] host = [ "utwente", "nl", ] [joosten.homepages] joosten_homepage = "https://sjcjoosten.nl/" [jungnickel] name = "Tim Jungnickel" [jungnickel.emails] [jungnickel.emails.jungnickel_email] user = [ "tim", "jungnickel", ] host = [ "tu-berlin", "de", ] [jungnickel.homepages] [kadzioka] name = "Maya Kądziołka" [kadzioka.emails] [kadzioka.emails.kadzioka_email] user = [ "afp", ] host = [ "compilercrim", "es", ] [kadzioka.homepages] [kaliszyk] name = "Cezary Kaliszyk" [kaliszyk.emails] [kaliszyk.emails.kaliszyk_email] user = [ "cezary", "kaliszyk", ] host = [ "uibk", "ac", "at", ] [kaliszyk.homepages] kaliszyk_homepage = "http://cl-informatik.uibk.ac.at/users/cek/" [kammueller] name = "Florian Kammüller" [kammueller.emails] [kammueller.emails.kammueller_email] user = [ "flokam", ] host = [ "cs", "tu-berlin", "de", ] [kammueller.emails.kammueller_email1] user = [ "florian", "kammuller", ] host = [ "gmail", "com", ] [kammueller.homepages] kammueller_homepage = "http://www.cs.mdx.ac.uk/people/florian-kammueller/" [kappelmann] name = "Kevin Kappelmann" [kappelmann.emails] [kappelmann.emails.kappelmann_email] user = [ "kevin", "kappelmann", ] host = [ "tum", "de", ] [kappelmann.homepages] kappelmann_homepage = "https://www21.in.tum.de/team/kappelmk/" [karayel] name = "Emin Karayel" orcid = "0000-0003-3290-5034" [karayel.emails] [karayel.emails.karayel_email] user = [ "me", ] host = [ "eminkarayel", "de", ] [karayel.homepages] karayel_homepage = "https://orcid.org/0000-0003-3290-5034" [kastermans] name = "Bart Kastermans" [kastermans.emails] [kastermans.homepages] kastermans_homepage = "http://kasterma.net" [katovsky] name = "Alexander Katovsky" [katovsky.emails] [katovsky.emails.katovsky_email] user = [ "apk32", ] host = [ "cam", "ac", "uk", ] [katovsky.emails.katovsky_email1] user = [ "alexander", "katovsky", ] host = [ "cantab", "net", ] [katovsky.homepages] [kaufmann] name = "Daniela Kaufmann" [kaufmann.emails] [kaufmann.homepages] kaufmann_homepage = "http://fmv.jku.at/kaufmann" [keefe] name = "Greg O'Keefe" [keefe.emails] [keefe.homepages] keefe_homepage = "http://users.rsise.anu.edu.au/~okeefe/" [keinholz] name = "Jonas Keinholz" [keinholz.emails] [keinholz.homepages] [kerber] name = "Manfred Kerber" [kerber.emails] [kerber.emails.kerber_email] user = [ "mnfrd", "krbr", ] host = [ "gmail", "com", ] [kerber.homepages] kerber_homepage = "http://www.cs.bham.ac.uk/~mmk" [keskin] name = "Ata Keskin" orcid = "0000-0002-8296-1766" [keskin.emails] [keskin.emails.keskin_email] user = [ "ata", "keskin", ] host = [ "tum", "de", ] [keskin.homepages] [ketland] name = "Jeffrey Ketland" [ketland.emails] [ketland.emails.ketland_email] user = [ "jeffreyketland", ] host = [ "gmail", "com", ] [ketland.homepages] [kim] name = "Sunpill Kim" orcid = "0000-0002-7767-4084" [kim.emails] [kim.homepages] [kirchner] name = "Daniel Kirchner" [kirchner.emails] [kirchner.emails.kirchner_email] user = [ "daniel", ] host = [ "ekpyron", "org", ] [kirchner.homepages] [klein] name = "Gerwin Klein" [klein.emails] [klein.emails.klein_email] user = [ "kleing", ] host = [ "unsw", "edu", "au", ] [klein.homepages] klein_homepage = "http://www.cse.unsw.edu.au/~kleing/" [klenze] name = "Tobias Klenze" [klenze.emails] [klenze.emails.klenze_email] user = [ "tobias", "klenze", ] host = [ "inf", "ethz", "ch", ] [klenze.homepages] [kleppmann] name = "Martin Kleppmann" [kleppmann.emails] [kleppmann.emails.kleppmann_email] user = [ "martin", "kleppmann", ] host = [ "cl", "cam", "ac", "uk", ] [kleppmann.homepages] [kobayashi] name = "Hidetsune Kobayashi" [kobayashi.emails] [kobayashi.homepages] [koerner] name = "Stefan Körner" [koerner.emails] [koerner.emails.koerner_email] user = [ "s_koer03", ] host = [ "uni-muenster", "de", ] [koerner.homepages] [kolanski] name = "Rafal Kolanski" [kolanski.emails] [kolanski.emails.kolanski_email] user = [ "rafal", "kolanski", ] host = [ "nicta", "com", "au", ] [kolanski.homepages] [koller] name = "Lukas Koller" [koller.emails] [koller.emails.koller_email] user = [ "lukas", "koller", ] host = [ "tum", "de", ] [koller.homepages] [krauss] name = "Alexander Krauss" [krauss.emails] [krauss.emails.krauss_email] user = [ "krauss", ] host = [ "in", "tum", "de", ] [krauss.homepages] krauss_homepage = "http://www.in.tum.de/~krauss" [kreuzer] name = "Katharina Kreuzer" [kreuzer.emails] [kreuzer.emails.kreuzer_email] user = [ "kreuzerk", ] host = [ "in", "tum", "de", ] [kreuzer.emails.kreuzer_email1] user = [ "k", "kreuzer", ] host = [ "tum", "de", ] [kreuzer.homepages] kreuzer_homepage = "https://www21.in.tum.de/team/kreuzer/" [kuncak] name = "Viktor Kuncak" [kuncak.emails] [kuncak.homepages] kuncak_homepage = "http://lara.epfl.ch/~kuncak/" [kuncar] name = "Ondřej Kunčar" [kuncar.emails] [kuncar.homepages] kuncar_homepage = "http://www21.in.tum.de/~kuncar/" [kurz] name = "Friedrich Kurz" [kurz.emails] [kurz.emails.kurz_email] user = [ "friedrich", "kurz", ] host = [ "tum", "de", ] [kurz.homepages] [lachnitt] name = "Hanna Lachnitt" [lachnitt.emails] [lachnitt.emails.lachnitt_email] user = [ "lachnitt", ] host = [ "stanford", "edu", ] [lachnitt.homepages] [lallemand] name = "Joseph Lallemand" [lallemand.emails] [lallemand.emails.lallemand_email] user = [ "joseph", "lallemand", ] host = [ "loria", "fr", ] [lallemand.homepages] [lammich] name = "Peter Lammich" [lammich.emails] [lammich.emails.lammich_email] user = [ "lammich", ] host = [ "in", "tum", "de", ] [lammich.emails.lammich_email1] user = [ "peter", "lammich", ] host = [ "uni-muenster", "de", ] [lammich.homepages] lammich_homepage = "http://www21.in.tum.de/~lammich" [lange] name = "Christoph Lange" [lange.emails] [lange.emails.lange_email] user = [ "math", "semantic", "web", ] host = [ "gmail", "com", ] [lange.homepages] [langenstein] name = "Bruno Langenstein" [langenstein.emails] [langenstein.emails.langenstein_email] user = [ "langenstein", ] host = [ "dfki", "de", ] [langenstein.homepages] [lattuada] name = "Andrea Lattuada" [lattuada.emails] [lattuada.homepages] lattuada_homepage = "https://andrea.lattuada.me" [lauermann] name = "Nils Lauermann" [lauermann.emails] [lauermann.emails.lauermann_email] user = [ "Nils", "Lauermann", ] host = [ "cl", "cam", "ac", "uk", ] [lauermann.homepages] [laursen] name = "Christian Pardillo-Laursen" [laursen.emails] [laursen.emails.laursen_email] user = [ "christian", "laursen", ] host = [ "york", "ac", "uk", ] [laursen.homepages] [lederer] name = "Patrick Lederer" [lederer.emails] [lederer.homepages] lederer_homepage = "https://www.cs.cit.tum.de/en/dss/members/patrick-lederer/" [lee] name = "Holden Lee" [lee.emails] [lee.emails.lee_email] user = [ "holdenl", ] host = [ "princeton", "edu", ] [lee.homepages] [leustean] name = "Laurentiu Leustean" [leustean.emails] [leustean.homepages] [lewis] name = "Corey Lewis" [lewis.emails] [lewis.emails.lewis_email] user = [ "corey", "lewis", ] host = [ "data61", "csiro", "au", ] [lewis.homepages] [li] name = "Wenda Li" [li.emails] [li.emails.li_email] user = [ "wl302", ] host = [ "cam", "ac", "uk", ] [li.emails.li_email1] user = [ "liwenda1990", ] host = [ "hotmail", "com", ] [li.homepages] li_homepage = "https://www.cl.cam.ac.uk/~wl302/" [lim] name = "Japheth Lim" [lim.emails] [lim.homepages] [lindenberg] name = "Christina Lindenberg" [lindenberg.emails] [lindenberg.homepages] [linker] name = "Sven Linker" [linker.emails] [linker.emails.linker_email] user = [ "s", "linker", ] host = [ "liverpool", "ac", "uk", ] [linker.homepages] [liu] name = "Junyi Liu" [liu.emails] [liu.homepages] [liut] name = "Tao Liu" [liut.emails] [liut.homepages] [liuy] name = "Yang Liu" [liuy.emails] [liuy.emails.liuy_email] user = [ "yangliu", ] host = [ "ntu", "edu", "sg", ] [liuy.homepages] [liy] name = "Yangjia Li" [liy.emails] [liy.homepages] [lochbihler] name = "Andreas Lochbihler" [lochbihler.emails] [lochbihler.emails.lochbihler_email] user = [ "andreas", "lochbihler", ] host = [ "digitalasset", "com", ] [lochbihler.emails.lochbihler_email1] user = [ "mail", ] host = [ "andreas-lochbihler", "de", ] [lochbihler.homepages] lochbihler_homepage = "http://www.andreas-lochbihler.de/" [lochmann] name = "Alexander Lochmann" [lochmann.emails] [lochmann.emails.lochmann_email] user = [ "alexander", "lochmann", ] host = [ "uibk", "ac", "at", ] [lochmann.homepages] [lohner] name = "Denis Lohner" [lohner.emails] [lohner.emails.lohner_email] user = [ "denis", "lohner", ] host = [ "kit", "edu", ] [lohner.homepages] lohner_homepage = "http://pp.ipd.kit.edu/person.php?id=88" [loibl] name = "Matthias Loibl" [loibl.emails] [loibl.homepages] [londono] name = "Alejandro Gómez-Londoño" [londono.emails] [londono.emails.londono_email] user = [ "alejandro", "gomez", ] host = [ "chalmers", "se", ] [londono.homepages] [losa] name = "Giuliano Losa" [losa.emails] [losa.emails.losa_email] user = [ "giuliano", "losa", ] host = [ "epfl", "ch", ] [losa.emails.losa_email1] user = [ "giuliano", ] host = [ "galois", "com", ] [losa.emails.losa_email2] user = [ "giuliano", ] host = [ "losa", "fr", ] [losa.homepages] [lutz] name = "Bianca Lutz" [lutz.emails] [lutz.emails.lutz_email] user = [ "sowilo", ] host = [ "cs", "tu-berlin", "de", ] [lutz.homepages] [lux] name = "Alexander Lux" [lux.emails] [lux.emails.lux_email] user = [ "lux", ] host = [ "mais", "informatik", "tu-darmstadt", "de", ] [lux.homepages] [madarasz] name = "Judit Madarasz" [madarasz.emails] [madarasz.homepages] madarasz_homepage = "https://users.renyi.hu/~madarasz/" [makarios] name = "T. J. M. Makarios" [makarios.emails] [makarios.emails.makarios_email] user = [ "tjm1983", ] host = [ "gmail", "com", ] [makarios.homepages] [maletzky] name = "Alexander Maletzky" [maletzky.emails] [maletzky.emails.maletzky_email] user = [ "alexander", "maletzky", ] host = [ "risc", "jku", "at", ] [maletzky.emails.maletzky_email1] user = [ "alexander", "maletzky", ] host = [ "risc-software", "at", ] [maletzky.homepages] maletzky_homepage = "https://risc.jku.at/m/alexander-maletzky/" [mansky] name = "Susannah Mansky" [mansky.emails] [mansky.emails.mansky_email] user = [ "sjohnsn2", ] host = [ "illinois", "edu", ] [mansky.emails.mansky_email1] user = [ "susannahej", ] host = [ "gmail", "com", ] [mansky.homepages] [mantel] name = "Heiko Mantel" [mantel.emails] [mantel.emails.mantel_email] user = [ "mantel", ] host = [ "mais", "informatik", "tu-darmstadt", "de", ] [mantel.homepages] [margetson] name = "James Margetson" [margetson.emails] [margetson.homepages] [maric] name = "Ognjen Marić" [maric.emails] [maric.emails.maric_email] user = [ "ogi", "afp", ] host = [ "mynosefroze", "com", ] [maric.homepages] [maricf] name = "Filip Marić" [maricf.emails] [maricf.emails.maricf_email] user = [ "filip", ] host = [ "matf", "bg", "ac", "rs", ] [maricf.homepages] maricf_homepage = "http://www.matf.bg.ac.rs/~filip" [marmsoler] name = "Diego Marmsoler" [marmsoler.emails] [marmsoler.emails.marmsoler_email] user = [ "diego", "marmsoler", ] host = [ "tum", "de", ] [marmsoler.emails.marmsoler_email1] user = [ "d", "marmsoler", ] host = [ "exeter", "ac", "uk", ] [marmsoler.homepages] marmsoler_homepage = "http://marmsoler.com" [matache] name = "Cristina Matache" [matache.emails] [matache.emails.matache_email] user = [ "cris", "matache", ] host = [ "gmail", "com", ] [matache.homepages] [mateo] name = "Adrián Doña Mateo" [mateo.emails] [mateo.emails.mateo_email] user = [ "adrian", "dona", ] host = [ "ed", "ac", "uk", ] [mateo.homepages] [matichuk] name = "Daniel Matichuk" [matichuk.emails] [matichuk.homepages] [matiyasevich] name = "Yuri Matiyasevich" [matiyasevich.emails] [matiyasevich.homepages] [maximova] name = "Alexandra Maximova" [maximova.emails] [maximova.emails.maximova_email] user = [ "amaximov", ] host = [ "student", "ethz", "ch", ] [maximova.homepages] [meis] name = "Rene Meis" [meis.emails] [meis.emails.meis_email] user = [ "rene", "meis", ] host = [ "uni-muenster", "de", ] [meis.emails.meis_email1] user = [ "rene", "meis", ] host = [ "uni-due", "de", ] [meis.homepages] [merz] name = "Stephan Merz" [merz.emails] [merz.emails.merz_email] user = [ "Stephan", "Merz", ] host = [ "loria", "fr", ] [merz.homepages] merz_homepage = "http://www.loria.fr/~merz" [messner] name = "Florian Messner" [messner.emails] [messner.emails.messner_email] user = [ "florian", "g", "messner", ] host = [ "uibk", "ac", "at", ] [messner.homepages] [mhalla] name = "Mehdi Mhalla" [mhalla.emails] [mhalla.emails.mhalla_email] user = [ "mhallam", ] host = [ "univ-grenoble-alpes", "fr", ] [mhalla.homepages] [michaelis] name = "Julius Michaelis" [michaelis.emails] [michaelis.emails.michaelis_email] user = [ "isabelleopenflow", ] host = [ "liftm", "de", ] [michaelis.emails.michaelis_email1] user = [ "maintainafpppt", ] host = [ "liftm", "de", ] [michaelis.emails.michaelis_email2] user = [ "bdd", ] host = [ "liftm", "de", ] [michaelis.emails.michaelis_email3] user = [ "afp", ] host = [ "liftm", "de", ] [michaelis.homepages] michaelis_homepage = "http://liftm.de/" [milehins] name = "Mihails Milehins" [milehins.emails] [milehins.emails.milehins_email] user = [ "mihailsmilehins", ] host = [ "gmail", "com", ] [milehins.homepages] [minamide] name = "Yasuhiko Minamide" [minamide.emails] [minamide.emails.minamide_email] user = [ "minamide", ] host = [ "is", "titech", "ac", "jp", ] [minamide.homepages] minamide_homepage = "https://sv.c.titech.ac.jp/minamide/index.en.html" [mitchell] name = "Neil Mitchell" [mitchell.emails] [mitchell.homepages] [mitsch] name = "Stefan Mitsch" [mitsch.emails] [mitsch.emails.mitsch_email] user = [ "smitsch", ] host = [ "cs", "cmu", "edu", ] [mitsch.homepages] [moedersheim] name = "Sebastian Mödersheim" [moedersheim.emails] [moedersheim.emails.moedersheim_email] user = [ "samo", ] host = [ "dtu", "dk", ] [moedersheim.homepages] moedersheim_homepage = "https://people.compute.dtu.dk/samo/" [moeller] name = "Bernhard Möller" [moeller.emails] [moeller.homepages] moeller_homepage = "https://www.informatik.uni-augsburg.de/en/chairs/dbis/pmi/staff/moeller/" [mori] name = "Coraline Mori" [mori.emails] [mori.emails.mori_email] user = [ "coraline", "mori", ] host = [ "grenoble-inp", "org", ] [mori.homepages] [muendler] name = "Niels Mündler" [muendler.emails] [muendler.emails.muendler_email] user = [ "n", "muendler", ] host = [ "tum", "de", ] [muendler.homepages] [mulligan] name = "Dominic P. Mulligan" [mulligan.emails] [mulligan.emails.mulligan_email] user = [ "dominic", "p", "mulligan", ] host = [ "googlemail", "com", ] [mulligan.emails.mulligan_email1] user = [ "Dominic", "Mulligan", ] host = [ "arm", "com", ] [mulligan.homepages] [munive] name = "Jonathan Julian Huerta y Munive" [munive.emails] [munive.emails.munive_email] user = [ "jjhuertaymunive1", ] host = [ "sheffield", "ac", "uk", ] [munive.emails.munive_email1] user = [ "jonjulian23", ] host = [ "gmail", "com", ] [munive.homepages] [murao] name = "H. Murao" [murao.emails] [murao.homepages] [murray] name = "Toby Murray" [murray.emails] [murray.emails.murray_email] user = [ "toby", "murray", ] host = [ "unimelb", "edu", "au", ] [murray.homepages] murray_homepage = "https://people.eng.unimelb.edu.au/tobym/" [myreen] name = "Magnus O. Myreen" orcid = "0000-0002-9504-4107" [myreen.emails] [myreen.emails.myreen_email] user = [ "myreen", ] host = [ "chalmers", "se", ] [myreen.homepages] [nagashima] name = "Yutaka Nagashima" [nagashima.emails] [nagashima.emails.nagashima_email] user = [ "Yutaka", "Nagashima", ] host = [ "data61", "csiro", "au", ] [nagashima.homepages] [nagele] name = "Julian Nagele" [nagele.emails] [nagele.emails.nagele_email] user = [ "julian", "nagele", ] host = [ "uibk", "ac", "at", ] [nagele.homepages] [naraschewski] name = "Wolfgang Naraschewski" [naraschewski.emails] [naraschewski.homepages] [nedzelsky] name = "Michael Nedzelsky" [nedzelsky.emails] [nedzelsky.emails.nedzelsky_email] user = [ "MichaelNedzelsky", ] host = [ "yandex", "ru", ] [nedzelsky.homepages] [nemeti] name = "István Németi" [nemeti.emails] [nemeti.homepages] nemeti_homepage = "http://www.renyi.hu/~nemeti/" [nemouchi] name = "Yakoub Nemouchi" [nemouchi.emails] [nemouchi.emails.nemouchi_email] user = [ "nemouchi", ] host = [ "lri", "fr", ] [nemouchi.emails.nemouchi_email1] user = [ "yakoub", "nemouchi", ] host = [ "york", "ac", "uk", ] [nemouchi.homepages] [nestmann] name = "Uwe Nestmann" [nestmann.emails] [nestmann.homepages] nestmann_homepage = "https://www.mtv.tu-berlin.de/nestmann/" [neumann] name = "René Neumann" [neumann.emails] [neumann.emails.neumann_email] user = [ "rene", "neumann", ] host = [ "in", "tum", "de", ] [neumann.homepages] [nielsen] name = "Finn Nielsen" [nielsen.emails] [nielsen.emails.nielsen_email] user = [ "finn", "nielsen", ] host = [ "uni-muenster", "de", ] [nielsen.homepages] [nikiforov] name = "Denis Nikiforov" [nikiforov.emails] [nikiforov.emails.nikiforov_email] user = [ "denis", "nikif", ] host = [ "gmail", "com", ] [nikiforov.homepages] [nipkow] name = "Tobias Nipkow" orcid = "0000-0003-0730-515X" [nipkow.emails] [nipkow.emails.nipkow_email] user = [ "nipkow", ] host = [ "in", "tum", "de", ] [nipkow.homepages] nipkow_homepage = "https://www.in.tum.de/~nipkow/" [nishihara] name = "Toshiaki Nishihara" [nishihara.emails] [nishihara.homepages] [noce] name = "Pasquale Noce" [noce.emails] [noce.emails.noce_email] user = [ "pasquale", "noce", "lavoro", ] host = [ "gmail", "com", ] [noce.homepages] [nordhoff] name = "Benedikt Nordhoff" [nordhoff.emails] [nordhoff.emails.nordhoff_email] user = [ "b", "n", ] host = [ "wwu", "de", ] [nordhoff.emails.nordhoff_email1] user = [ "b_nord01", ] host = [ "uni-muenster", "de", ] [nordhoff.homepages] [noschinski] name = "Lars Noschinski" [noschinski.emails] [noschinski.emails.noschinski_email] user = [ "noschinl", ] host = [ "gmail", "com", ] [noschinski.homepages] noschinski_homepage = "http://www21.in.tum.de/~noschinl/" [obua] name = "Steven Obua" [obua.emails] [obua.emails.obua_email] user = [ "steven", ] host = [ "recursivemind", "com", ] [obua.homepages] [ogawa] name = "Mizuhito Ogawa" [ogawa.emails] [ogawa.homepages] [oldenburg] name = "Lennart Oldenburg" [oldenburg.emails] [oldenburg.homepages] [olm] name = "Markus Müller-Olm" [olm.emails] [olm.homepages] olm_homepage = "http://cs.uni-muenster.de/u/mmo/" [oosterhuis] name = "Roelof Oosterhuis" [oosterhuis.emails] [oosterhuis.emails.oosterhuis_email] user = [ "roelofoosterhuis", ] host = [ "gmail", "com", ] [oosterhuis.homepages] [oostrom] name = "Vincent van Oostrom" [oostrom.emails] [oostrom.homepages] [ortner] name = "Veronika Ortner" [ortner.emails] [ortner.homepages] [overbeek] name = "Roy Overbeek" [overbeek.emails] [overbeek.emails.overbeek_email] user = [ "Roy", "Overbeek", ] host = [ "cwi", "nl", ] [overbeek.homepages] [pagano] name = "Miguel Pagano" [pagano.emails] [pagano.emails.pagano_email] user = [ "miguel", "pagano", ] host = [ "unc", "edu", "ar", ] [pagano.homepages] pagano_homepage = "https://cs.famaf.unc.edu.ar/~mpagano/" [pal] name = "Abhik Pal" [pal.emails] [pal.homepages] [paleo] name = "Bruno Woltzenlogel Paleo" [paleo.emails] [paleo.homepages] paleo_homepage = "http://www.logic.at/staff/bruno/" [palmer] name = "Jake Palmer" [palmer.emails] [palmer.emails.palmer_email] user = [ "jake", "palmer", ] host = [ "ed", "ac", "uk", ] [palmer.homepages] [park] name = "Seung Hoon Park" orcid = "0000-0001-7165-6857" [park.emails] [park.emails.park_email] user = [ "seunghoon", "park", ] host = [ "cs", "ox", "ac", "uk", ] [park.homepages] park_homepage = "https://www.cs.ox.ac.uk/people/simon.park/" [parkinson] name = "Matthew Parkinson" [parkinson.emails] [parkinson.homepages] parkinson_homepage = "http://research.microsoft.com/people/mattpark/" [parrow] name = "Joachim Parrow" [parrow.emails] [parrow.emails.parrow_email] user = [ "joachim", "parrow", ] host = [ "it", "uu", "se", ] [parrow.homepages] [parsert] name = "Julian Parsert" [parsert.emails] [parsert.emails.parsert_email] user = [ "julian", "parsert", ] host = [ "gmail", "com", ] [parsert.emails.parsert_email1] user = [ "julian", "parsert", ] host = [ "uibk", "ac", "at", ] [parsert.homepages] parsert_homepage = "http://www.parsert.com/" [paulson] name = "Lawrence C. Paulson" [paulson.emails] [paulson.emails.paulson_email] user = [ "lp15", ] host = [ "cam", "ac", "uk", ] [paulson.homepages] paulson_homepage = "https://www.cl.cam.ac.uk/~lp15/" [peltier] name = "Nicolas Peltier" [peltier.emails] [peltier.emails.peltier_email] user = [ "Nicolas", "Peltier", ] host = [ "imag", "fr", ] [peltier.homepages] peltier_homepage = "http://membres-lig.imag.fr/peltier/" [peters] name = "Kirstin Peters" [peters.emails] [peters.emails.peters_email] user = [ "kirstin", "peters", ] host = [ "tu-berlin", "de", ] [peters.homepages] [petrovic] name = "Danijela Petrovic" [petrovic.emails] [petrovic.homepages] petrovic_homepage = "http://www.matf.bg.ac.rs/~danijela" [pierzchalski] name = "Edward Pierzchalski" [pierzchalski.emails] [pierzchalski.homepages] [platzer] name = "André Platzer" [platzer.emails] [platzer.emails.platzer_email] user = [ "aplatzer", ] host = [ "cs", "cmu", "edu", ] [platzer.homepages] platzer_homepage = "https://www.cs.cmu.edu/~aplatzer/" [pohjola] name = "Johannes Åman Pohjola" [pohjola.emails] [pohjola.emails.pohjola_email] user = [ "j", "amanpohjola", ] host = [ "unsw", "edu", "au", ] [pohjola.homepages] [pollak] name = "Florian Pollak" [pollak.emails] [pollak.emails.pollak_email] user = [ "florian", "pollak", ] host = [ "gmail", "com", ] [pollak.homepages] [popescu] name = "Andrei Popescu" [popescu.emails] [popescu.emails.popescu_email] user = [ "a", "popescu", ] host = [ "sheffield", "ac", "uk", ] [popescu.emails.popescu_email1] user = [ "uuomul", ] host = [ "yahoo", "com", ] [popescu.emails.popescu_email2] user = [ "a", "popescu", ] host = [ "mdx", "ac", "uk", ] [popescu.homepages] popescu_homepage = "https://www.andreipopescu.uk" [porter] name = "Benjamin Porter" [porter.emails] [porter.homepages] [prathamesh] name = "T.V.H. Prathamesh" [prathamesh.emails] [prathamesh.emails.prathamesh_email] user = [ "prathamesh", ] host = [ "imsc", "res", "in", ] [prathamesh.homepages] [preoteasa] name = "Viorel Preoteasa" [preoteasa.emails] [preoteasa.emails.preoteasa_email] user = [ "viorel", "preoteasa", ] host = [ "aalto", "fi", ] [preoteasa.homepages] preoteasa_homepage = "http://users.abo.fi/vpreotea/" [pusch] name = "Cornelia Pusch" [pusch.emails] [pusch.homepages] [qiu] name = "Qi Qiu" [qiu.emails] [qiu.emails.qiu_email] user = [ "qi", "qiu", ] host = [ "univ-lyon1", "fr", ] [qiu.homepages] [rabe] name = "Markus N. Rabe" [rabe.emails] [rabe.homepages] rabe_homepage = "http://www.react.uni-saarland.de/people/rabe.html" [raedle] name = "Jonas Rädle" [raedle.emails] [raedle.emails.raedle_email] user = [ "jonas", "raedle", ] host = [ "gmail", "com", ] [raedle.emails.raedle_email1] user = [ "jonas", "raedle", ] host = [ "tum", "de", ] [raedle.homepages] [raska] name = "Martin Raška" [raska.emails] [raska.homepages] [raszyk] name = "Martin Raszyk" [raszyk.emails] [raszyk.emails.raszyk_email] user = [ "martin", "raszyk", ] host = [ "inf", "ethz", "ch", ] [raszyk.emails.raszyk_email1] user = [ "m", "raszyk", ] host = [ "gmail", "com", ] [raszyk.homepages] [rau] name = "Martin Rau" [rau.emails] [rau.emails.rau_email] user = [ "martin", "rau", ] host = [ "tum", "de", ] [rau.emails.rau_email1] user = [ "mrtnrau", ] host = [ "googlemail", "com", ] [rau.homepages] [rauch] name = "Nicole Rauch" [rauch.emails] [rauch.emails.rauch_email] user = [ "rauch", ] host = [ "informatik", "uni-kl", "de", ] [rauch.homepages] [raumer] name = "Jakob von Raumer" [raumer.emails] [raumer.emails.raumer_email] user = [ "psxjv4", ] host = [ "nottingham", "ac", "uk", ] [raumer.homepages] [ravindran] name = "Binoy Ravindran" [ravindran.emails] [ravindran.homepages] [rawson] name = "Michael Rawson" [rawson.emails] [rawson.emails.rawson_email] user = [ "michaelrawson76", ] host = [ "gmail", "com", ] [rawson.emails.rawson_email1] user = [ "mr644", ] host = [ "cam", "ac", "uk", ] [rawson.homepages] [raya] name = "Rodrigo Raya" [raya.emails] [raya.emails.raya_email] user = [ "rodrigo", "raya", ] host = [ "epfl", "ch", ] [raya.homepages] raya_homepage = "https://people.epfl.ch/rodrigo.raya" [regensburger] name = "Franz Regensburger" [regensburger.emails] [regensburger.emails.regensburger_email] user = [ "Franz", "Regensburger", ] host = [ "thi", "de", ] [regensburger.homepages] regensburger_homepage = "https://www.thi.de/suche/mitarbeiter/prof-dr-rer-nat-franz-regensburger" [reiche] name = "Sebastian Reiche" [reiche.emails] [reiche.homepages] reiche_homepage = "https://www.linkedin.com/in/sebastian-reiche-0b2093178" [reiter] name = "Markus Reiter" [reiter.emails] [reiter.homepages] [reynaud] name = "Alban Reynaud" [reynaud.emails] [reynaud.homepages] [ribeiro] name = "Pedro Ribeiro" [ribeiro.emails] [ribeiro.homepages] [richter] name = "Stefan Richter" [richter.emails] [richter.emails.richter_email] user = [ "richter", ] host = [ "informatik", "rwth-aachen", "de", ] [richter.homepages] richter_homepage = "http://www-lti.informatik.rwth-aachen.de/~richter/" [rickmann] name = "Christina Rickmann" [rickmann.emails] [rickmann.emails.rickmann_email] user = [ "c", "rickmann", ] host = [ "tu-berlin", "de", ] [rickmann.homepages] [ridge] name = "Tom Ridge" [ridge.emails] [ridge.homepages] [rizaldi] name = "Albert Rizaldi" [rizaldi.emails] [rizaldi.emails.rizaldi_email] user = [ "albert", "rizaldi", ] host = [ "ntu", "edu", "sg", ] [rizaldi.homepages] [rizkallah] name = "Christine Rizkallah" [rizkallah.emails] [rizkallah.homepages] rizkallah_homepage = "https://www.mpi-inf.mpg.de/~crizkall/" [robillard] name = "Simon Robillard" [robillard.emails] [robillard.homepages] robillard_homepage = "https://simon-robillard.net/" [roessle] name = "Ian Roessle" [roessle.emails] [roessle.homepages] [romanos] name = "Ralph Romanos" [romanos.emails] [romanos.emails.romanos_email] user = [ "ralph", "romanos", ] host = [ "student", "ecp", "fr", ] [romanos.homepages] [rosskopf] name = "Simon Roßkopf" [rosskopf.emails] [rosskopf.emails.rosskopf_email] user = [ "rosskops", ] host = [ "in", "tum", "de", ] [rosskopf.homepages] rosskopf_homepage = "http://www21.in.tum.de/~rosskops" [rowat] name = "Colin Rowat" [rowat.emails] [rowat.emails.rowat_email] user = [ "c", "rowat", ] host = [ "bham", "ac", "uk", ] [rowat.homepages] [sabouret] name = "Nicolas Sabouret" [sabouret.emails] [sabouret.homepages] [sachtleben] name = "Robert Sachtleben" [sachtleben.emails] [sachtleben.emails.sachtleben_email] user = [ "rob_sac", ] host = [ "uni-bremen", "de", ] [sachtleben.homepages] [saile] name = "Christian Saile" [saile.emails] [saile.homepages] saile_homepage = "http://dss.in.tum.de/staff/christian-saile.html" [sanan] name = "David Sanan" [sanan.emails] [sanan.emails.sanan_email] user = [ "sanan", ] host = [ "ntu", "edu", "sg", ] [sanan.homepages] [sato] name = "Tetsuya Sato" [sato.emails] [sato.emails.sato_email] user = [ "tsato", ] host = [ "c", "titech", "ac", "jp", ] [sato.homepages] sato_homepage = "https://sites.google.com/view/tetsuyasato/" [sauer] name = "Jens Sauer" [sauer.emails] [sauer.emails.sauer_email] user = [ "sauer", ] host = [ "mais", "informatik", "tu-darmstadt", "de", ] [sauer.homepages] [schaeffeler] name = "Maximilian Schäffeler" [schaeffeler.emails] [schaeffeler.emails.schaeffeler_email] user = [ "schaeffm", ] host = [ "in", "tum", "de", ] [schaeffeler.homepages] [scharager] name = "Matias Scharager" [scharager.emails] [scharager.emails.scharager_email] user = [ "mscharag", ] host = [ "cs", "cmu", "edu", ] [scharager.homepages] [schimpf] name = "Alexander Schimpf" [schimpf.emails] [schimpf.emails.schimpf_email] user = [ "schimpfa", ] host = [ "informatik", "uni-freiburg", "de", ] [schimpf.homepages] [schirmer] name = "Norbert Schirmer" [schirmer.emails] [schirmer.emails.schirmer_email] user = [ "norbert", "schirmer", ] host = [ "web", "de", ] [schirmer.homepages] [schleicher] name = "Dierk Schleicher" [schleicher.emails] [schleicher.homepages] [schlichtkrull] name = "Anders Schlichtkrull" [schlichtkrull.emails] [schlichtkrull.emails.schlichtkrull_email] user = [ "andschl", ] host = [ "dtu", "dk", ] [schlichtkrull.homepages] schlichtkrull_homepage = "https://people.compute.dtu.dk/andschl/" [schmaltz] name = "Julien Schmaltz" [schmaltz.emails] [schmaltz.emails.schmaltz_email] user = [ "Julien", "Schmaltz", ] host = [ "ou", "nl", ] [schmaltz.homepages] [schmidinger] name = "Lukas Schmidinger" [schmidinger.emails] [schmidinger.homepages] [schmoetten] name = "Richard Schmoetten" [schmoetten.emails] [schmoetten.emails.schmoetten_email] user = [ "s1311325", ] host = [ "sms", "ed", "ac", "uk", ] [schmoetten.homepages] [schneider] name = "Joshua Schneider" [schneider.emails] [schneider.emails.schneider_email] user = [ "joshua", "schneider", ] host = [ "inf", "ethz", "ch", ] [schneider.homepages] [schoepe] name = "Daniel Schoepe" [schoepe.emails] [schoepe.emails.schoepe_email] user = [ "daniel", ] host = [ "schoepe", "org", ] [schoepe.homepages] [schoepf] name = "Jonas Schöpf" [schoepf.emails] [schoepf.emails.schoepf_email] user = [ "jonas", "schoepf", ] host = [ "uibk", "ac", "at", ] [schoepf.homepages] [scott] name = "Dana Scott" [scott.emails] [scott.homepages] scott_homepage = "http://www.cs.cmu.edu/~scott/" [sefidgar] name = "S. Reza Sefidgar" [sefidgar.emails] [sefidgar.emails.sefidgar_email] user = [ "reza", "sefidgar", ] host = [ "inf", "ethz", "ch", ] [sefidgar.homepages] [seidl] name = "Benedikt Seidl" [seidl.emails] [seidl.emails.seidl_email] user = [ "benedikt", "seidl", ] host = [ "tum", "de", ] [seidl.homepages] [seidler] name = "Henning Seidler" [seidler.emails] [seidler.emails.seidler_email] user = [ "henning", "seidler", ] host = [ "mailbox", "tu-berlin", "de", ] [seidler.homepages] [sewell] name = "Thomas Sewell" [sewell.emails] [sewell.homepages] [sickert] name = "Salomon Sickert" [sickert.emails] [sickert.emails.sickert_email] user = [ "s", "sickert", ] host = [ "tum", "de", ] [sickert.homepages] sickert_homepage = "https://www7.in.tum.de/~sickert" [siek] name = "Jeremy Siek" [siek.emails] [siek.emails.siek_email] user = [ "jsiek", ] host = [ "indiana", "edu", ] [siek.homepages] siek_homepage = "http://homes.soic.indiana.edu/jsiek/" [simic] name = "Danijela Simić" [simic.emails] [simic.emails.simic_email] user = [ "danijela", ] host = [ "matf", "bg", "ac", "rs", ] [simic.homepages] simic_homepage = "http://poincare.matf.bg.ac.rs/~danijela" [sison] name = "Robert Sison" [sison.emails] [sison.homepages] [smaus] name = "Jan-Georg Smaus" [smaus.emails] [smaus.homepages] smaus_homepage = "http://www.irit.fr/~Jan-Georg.Smaus" [smola] name = "Filip Smola" [smola.emails] [smola.emails.smola_email] user = [ "f", "smola", ] host = [ "sms", "ed", "ac", "uk", ] [smola.homepages] [snelting] name = "Gregor Snelting" [snelting.emails] [snelting.homepages] snelting_homepage = "http://pp.info.uni-karlsruhe.de/personhp/gregor_snelting.php" [somaini] name = "Ivano Somaini" [somaini.emails] [somaini.homepages] [somogyi] name = "Dániel Somogyi" [somogyi.emails] [somogyi.homepages] [spasic] name = "Mirko Spasić" [spasic.emails] [spasic.emails.spasic_email] user = [ "mirko", ] host = [ "matf", "bg", "ac", "rs", ] [spasic.homepages] [spichkova] name = "Maria Spichkova" [spichkova.emails] [spichkova.emails.spichkova_email] user = [ "maria", "spichkova", ] host = [ "rmit", "edu", "au", ] [spichkova.homepages] [spitz] name = "Maximilian Spitz" [spitz.emails] [spitz.emails.spitz_email] user = [ "maximilian", "spitz", ] host = [ "tum", "de", ] [spitz.homepages] [sprenger] name = "Christoph Sprenger" [sprenger.emails] [sprenger.emails.sprenger_email] user = [ "sprenger", ] host = [ "inf", "ethz", "ch", ] [sprenger.homepages] + +[springsklee] +name = "Valentin Springsklee" + +[springsklee.emails] + +[springsklee.emails.springsklee_email] +user = [ + "uidpn>", +] +host = [ + "student", + "kit", + "edu", +] + +[springsklee.homepages] + + + [staats] name = "Charles Staats" [staats.emails] [staats.emails.staats_email] user = [ "cstaats", ] host = [ "google", "com", ] [staats.emails.staats_email1] user = [ "charles", "staats", "iii", ] host = [ "gmail", "com", ] [staats.homepages] [stannett] name = "Mike Stannett" [stannett.emails] [stannett.emails.stannett_email] user = [ "m", "stannett", ] host = [ "sheffield", "ac", "uk", ] [stannett.homepages] [stark] name = "Eugene W. Stark" [stark.emails] [stark.emails.stark_email] user = [ "stark", ] host = [ "cs", "stonybrook", "edu", ] [stark.homepages] [starosta] name = "Štěpán Starosta" [starosta.emails] [starosta.emails.starosta_email] user = [ "stepan", "starosta", ] host = [ "fit", "cvut", "cz", ] [starosta.homepages] starosta_homepage = "https://users.fit.cvut.cz/~staroste/" [steen] name = "Alexander Steen" [steen.emails] [steen.homepages] [steinberg] name = "Matías Steinberg" [steinberg.emails] [steinberg.emails.steinberg_email] user = [ "matias", "steinberg", ] host = [ "mi", "unc", "edu", "ar", ] [steinberg.homepages] [stephan] name = "Werner Stephan" [stephan.emails] [stephan.emails.stephan_email] user = [ "stephan", ] host = [ "dfki", "de", ] [stephan.homepages] [sternagel] name = "Christian Sternagel" [sternagel.emails] [sternagel.emails.sternagel_email] user = [ "c", "sternagel", ] host = [ "gmail", "com", ] [sternagel.emails.sternagel_email1] user = [ "christian", "sternagel", ] host = [ "uibk", "ac", "at", ] [sternagel.homepages] sternagel_homepage = "http://cl-informatik.uibk.ac.at/users/griff/" [sternagelt] name = "Thomas Sternagel" [sternagelt.emails] [sternagelt.homepages] [stevens] name = "Lukas Stevens" [stevens.emails] [stevens.emails.stevens_email] user = [ "lukas", "stevens", ] host = [ "in", "tum", "de", ] [stevens.homepages] stevens_homepage = "https://www21.in.tum.de/team/stevensl" [stock] name = "Benedikt Stock" [stock.emails] [stock.emails.stock_email] user = [ "benedikt1999", ] host = [ "freenet", "de", ] [stock.homepages] [stoeckl] name = "Bernhard Stöckl" [stoeckl.emails] [stoeckl.emails.stoeckl_email] user = [ "stoeckl", ] host = [ "in", "tum", "de", ] [stoeckl.homepages] [stricker] name = "Christian Stricker" [stricker.emails] [stricker.homepages] stricker_homepage = "http://dss.in.tum.de/staff/christian-stricker.html" [strnisa] name = "Rok Strniša" [strnisa.emails] [strnisa.emails.strnisa_email] user = [ "rok", ] host = [ "strnisa", "com", ] [strnisa.homepages] strnisa_homepage = "http://rok.strnisa.com/lj/" [struth] name = "Georg Struth" [struth.emails] [struth.emails.struth_email] user = [ "g", "struth", ] host = [ "sheffield", "ac", "uk", ] [struth.homepages] struth_homepage = "http://staffwww.dcs.shef.ac.uk/people/G.Struth/" [stueber] name = "Anke Stüber" [stueber.emails] [stueber.emails.stueber_email] user = [ "anke", "stueber", ] host = [ "campus", "tu-berlin", "de", ] [stueber.homepages] [stuewe] name = "Daniel Stüwe" [stuewe.emails] [stuewe.homepages] [sudbrock] name = "Henning Sudbrock" [sudbrock.emails] [sudbrock.emails.sudbrock_email] user = [ "sudbrock", ] host = [ "mais", "informatik", "tu-darmstadt", "de", ] [sudbrock.homepages] [sudhof] name = "Henry Sudhof" [sudhof.emails] [sudhof.emails.sudhof_email] user = [ "hsudhof", ] host = [ "cs", "tu-berlin", "de", ] [sudhof.homepages] [sulejmani] name = "Ujkan Sulejmani" [sulejmani.emails] [sulejmani.emails.sulejmani_email] user = [ "ujkan", "sulejmani", ] host = [ "tum", "de", ] [sulejmani.emails.sulejmani_email1] user = [ "ujkan99", ] host = [ "gmail", "com", ] [sulejmani.homepages] [sutcliffe] name = "Geoff Sutcliffe" [sutcliffe.emails] [sutcliffe.homepages] [sylvestre] name = "Jeremy Sylvestre" [sylvestre.emails] [sylvestre.emails.sylvestre_email] user = [ "jeremy", "sylvestre", ] host = [ "ualberta", "ca", ] [sylvestre.emails.sylvestre_email1] user = [ "jsylvest", ] host = [ "ualberta", "ca", ] [sylvestre.homepages] sylvestre_homepage = "http://ualberta.ca/~jsylvest/" [szekely] name = "Gergely Szekely" [szekely.emails] [szekely.homepages] szekely_homepage = "https://users.renyi.hu/~turms/" [taha] name = "Safouan Taha" [taha.emails] [taha.emails.taha_email] user = [ "safouan", "taha", ] host = [ "lri", "fr", ] [taha.homepages] [tan] name = "Yong Kiam Tan" [tan.emails] [tan.emails.tan_email] user = [ "yongkiat", ] host = [ "cs", "cmu", "edu", ] [tan.homepages] tan_homepage = "https://www.cs.cmu.edu/~yongkiat/" [tanaka] name = "Miki Tanaka" [tanaka.emails] [tanaka.emails.tanaka_email] user = [ "miki", "tanaka", ] host = [ "unsw", "edu", "au", ] [tanaka.homepages] [tasch] name = "Markus Tasch" [tasch.emails] [tasch.emails.tasch_email] user = [ "tasch", ] host = [ "mais", "informatik", "tu-darmstadt", "de", ] [tasch.homepages] [taylor] name = "Ramsay G. Taylor" [taylor.emails] [taylor.emails.taylor_email] user = [ "r", "g", "taylor", ] host = [ "sheffield", "ac", "uk", ] [taylor.homepages] [terraf] name = "Pedro Sánchez Terraf" [terraf.emails] [terraf.emails.terraf_email] user = [ "psterraf", ] host = [ "unc", "edu", "ar", ] [terraf.homepages] terraf_homepage = "https://cs.famaf.unc.edu.ar/~pedro/home_en.html" [thiemann] name = "René Thiemann" [thiemann.emails] [thiemann.emails.thiemann_email] user = [ "rene", "thiemann", ] host = [ "uibk", "ac", "at", ] [thiemann.homepages] thiemann_homepage = "http://cl-informatik.uibk.ac.at/users/thiemann/" [thommes] name = "Joseph Thommes" [thommes.emails] [thommes.emails.thommes_email] user = [ "joseph-thommes", ] host = [ "gmx", "de", ] [thommes.homepages] [thomson] name = "Fox Thomson" [thomson.emails] [thomson.emails.thomson_email] user = [ "foxthomson0", ] host = [ "gmail", "com", ] [thomson.homepages] [tiu] name = "Alwen Tiu" [tiu.emails] [tiu.emails.tiu_email] user = [ "ATiu", ] host = [ "ntu", "edu", "sg", ] [tiu.homepages] tiu_homepage = "http://users.cecs.anu.edu.au/~tiu/" [toth] name = "Balazs Toth" [toth.emails] [toth.emails.toth_email] user = [ "balazs", "toth", ] host = [ "tum", "de", ] [toth.homepages] [tourret] name = "Sophie Tourret" [tourret.emails] [tourret.emails.tourret_email] user = [ "stourret", ] host = [ "mpi-inf", "mpg", "de", ] [tourret.homepages] tourret_homepage = "https://www.mpi-inf.mpg.de/departments/automation-of-logic/people/sophie-tourret/" [trachtenherz] name = "David Trachtenherz" [trachtenherz.emails] [trachtenherz.homepages] [traut] name = "Christoph Traut" [traut.emails] [traut.homepages] [traytel] name = "Dmitriy Traytel" [traytel.emails] [traytel.emails.traytel_email] user = [ "traytel", ] host = [ "in", "tum", "de", ] [traytel.emails.traytel_email1] user = [ "traytel", ] host = [ "inf", "ethz", "ch", ] [traytel.emails.traytel_email2] user = [ "traytel", ] host = [ "di", "ku", "dk", ] [traytel.homepages] traytel_homepage = "https://traytel.bitbucket.io/" [trelat] name = "Vincent Trélat" [trelat.emails] [trelat.emails.trelat_email] user = [ "vincent", "trelat", ] host = [ "depinfonancy", "net", ] [trelat.homepages] [tuerk] name = "Thomas Tuerk" [tuerk.emails] [tuerk.homepages] [tuong] name = "Frédéric Tuong" [tuong.emails] [tuong.emails.tuong_email] user = [ "tuong", ] host = [ "users", "gforge", "inria", "fr", ] [tuong.emails.tuong_email1] user = [ "ftuong", ] host = [ "lri", "fr", ] [tuong.homepages] tuong_homepage = "https://www.lri.fr/~ftuong/" [tuongj] name = "Joseph Tuong" [tuongj.emails] [tuongj.homepages] [tverdyshev] name = "Sergey Tverdyshev" [tverdyshev.emails] [tverdyshev.emails.tverdyshev_email] user = [ "stv", ] host = [ "sysgo", "com", ] [tverdyshev.homepages] [ullrich] name = "Sebastian Ullrich" [ullrich.emails] [ullrich.emails.ullrich_email] user = [ "sebasti", ] host = [ "nullri", "ch", ] [ullrich.homepages] [unruh] name = "Dominique Unruh" [unruh.emails] [unruh.emails.unruh_email] user = [ "unruh", ] host = [ "ut", "ee", ] [unruh.homepages] unruh_homepage = "https://www.ut.ee/~unruh/" [urban] name = "Christian Urban" [urban.emails] [urban.emails.urban_email] user = [ "christian", "urban", ] host = [ "kcl", "ac", "uk", ] [urban.homepages] urban_homepage = "https://nms.kcl.ac.uk/christian.urban/" [van] name = "Hai Nguyen Van" [van.emails] [van.emails.van_email] user = [ "hai", "nguyenvan", "phie", ] host = [ "gmail", "com", ] [van.homepages] [velykis] name = "Andrius Velykis" [velykis.emails] [velykis.homepages] velykis_homepage = "http://andrius.velykis.lt" [verbeek] name = "Freek Verbeek" [verbeek.emails] [verbeek.emails.verbeek_email] user = [ "Freek", "Verbeek", ] host = [ "ou", "nl", ] [verbeek.emails.verbeek_email1] user = [ "freek", ] host = [ "vt", "edu", ] [verbeek.homepages] [villadsen] name = "Jørgen Villadsen" [villadsen.emails] [villadsen.emails.villadsen_email] user = [ "jovi", ] host = [ "dtu", "dk", ] [villadsen.homepages] villadsen_homepage = "https://people.compute.dtu.dk/jovi/" [voisin] name = "Frederic Voisin" [voisin.emails] [voisin.homepages] [vytiniotis] name = "Dimitrios Vytiniotis" [vytiniotis.emails] [vytiniotis.homepages] vytiniotis_homepage = "http://research.microsoft.com/en-us/people/dimitris/" [wagner] name = "Max Wagner" [wagner.emails] [wagner.emails.wagner_email] user = [ "max", ] host = [ "trollbu", "de", ] [wagner.homepages] [waldmann] name = "Uwe Waldmann" [waldmann.emails] [waldmann.emails.waldmann_email] user = [ "waldmann", ] host = [ "mpi-inf", "mpg", "de", ] [waldmann.homepages] [wand] name = "Daniel Wand" [wand.emails] [wand.emails.wand_email] user = [ "dwand", ] host = [ "mpi-inf", "mpg", "de", ] [wand.homepages] [wang] name = "Shuling Wang" [wang.emails] [wang.homepages] [wassell] name = "Mark Wassell" [wassell.emails] [wassell.emails.wassell_email] user = [ "mpwassell", ] host = [ "gmail", "com", ] [wassell.homepages] [wasserrab] name = "Daniel Wasserrab" [wasserrab.emails] [wasserrab.homepages] wasserrab_homepage = "http://pp.info.uni-karlsruhe.de/personhp/daniel_wasserrab.php" [watt] name = "Conrad Watt" [watt.emails] [watt.emails.watt_email] user = [ "caw77", ] host = [ "cam", "ac", "uk", ] [watt.homepages] watt_homepage = "http://www.cl.cam.ac.uk/~caw77/" [weber] name = "Tjark Weber" [weber.emails] [weber.emails.weber_email] user = [ "tjark", "weber", ] host = [ "it", "uu", "se", ] [weber.homepages] weber_homepage = "http://user.it.uu.se/~tjawe125/" [weerwag] name = "Timmy Weerwag" [weerwag.emails] [weerwag.homepages] [weidner] name = "Arno Wilhelm-Weidner" [weidner.emails] [weidner.emails.weidner_email] user = [ "arno", "wilhelm-weidner", ] host = [ "tu-berlin", "de", ] [weidner.homepages] [wenninger] name = "Elias Wenninger" [wenninger.emails] [wenninger.homepages] [wenzel] name = "Makarius Wenzel" [wenzel.emails] [wenzel.emails.wenzel_email] user = [ "makarius", ] host = [ "sketis", "net", ] [wenzel.homepages] wenzel_homepage = "https://sketis.net" [whitley] name = "A Whitley" [whitley.emails] [whitley.emails.whitley_email] user = [ "awhitley", ] host = [ "gmail", "com", ] [whitley.homepages] [wickerson] name = "John Wickerson" [wickerson.emails] [wickerson.homepages] wickerson_homepage = "http://www.doc.ic.ac.uk/~jpw48" [willenbrink] name = "Sebastian Willenbrink" [willenbrink.emails] [willenbrink.emails.willenbrink_email] user = [ "sebastian", "willenbrink", ] host = [ "tum", "de", ] [willenbrink.homepages] [wimmer] name = "Simon Wimmer" [wimmer.emails] [wimmer.emails.wimmer_email] user = [ "simon", "wimmer", ] host = [ "tum", "de", ] [wimmer.homepages] wimmer_homepage = "http://home.in.tum.de/~wimmers/" [wirt] name = "Kai Wirt" [wirt.emails] [wirt.homepages] [wolff] name = "Burkhart Wolff" [wolff.emails] [wolff.emails.wolff_email] user = [ "burkhart", "wolff", ] host = [ "lri", "fr", ] [wolff.homepages] wolff_homepage = "https://www.lri.fr/~wolff/" [wu] name = "Chunhan Wu" [wu.emails] [wu.homepages] [xu] name = "Jian Xu" [xu.emails] [xu.homepages] [yamada] name = "Akihisa Yamada" [yamada.emails] [yamada.emails.yamada_email] user = [ "akihisa", "yamada", ] host = [ "uibk", "ac", "at", ] [yamada.emails.yamada_email1] user = [ "ayamada", ] host = [ "trs", "cm", "is", "nagoya-u", "ac", "jp", ] [yamada.emails.yamada_email2] user = [ "akihisa", "yamada", ] host = [ "aist", "go", "jp", ] [yamada.emails.yamada_email3] user = [ "akihisayamada", ] host = [ "nii", "ac", "jp", ] [yamada.homepages] yamada_homepage = "http://group-mmm.org/~ayamada/" [ye] name = "Lina Ye" [ye.emails] [ye.emails.ye_email] user = [ "lina", "ye", ] host = [ "lri", "fr", ] [ye.homepages] [ying] name = "Shenggang Ying" [ying.emails] [ying.homepages] [yingm] name = "Mingsheng Ying" [yingm.emails] [yingm.homepages] [yu] name = "Lei Yu" [yu.emails] [yu.emails.yu_email] user = [ "ly271", ] host = [ "cam", "ac", "uk", ] [yu.homepages] [zankl] name = "Harald Zankl" [zankl.emails] [zankl.emails.zankl_email] user = [ "Harald", "Zankl", ] host = [ "uibk", "ac", "at", ] [zankl.homepages] zankl_homepage = "http://cl-informatik.uibk.ac.at/users/hzankl" [zee] name = "Karen Zee" [zee.emails] [zee.emails.zee_email] user = [ "kkz", ] host = [ "mit", "edu", ] [zee.homepages] zee_homepage = "http://www.mit.edu/~kkz/" [zeller] name = "Peter Zeller" [zeller.emails] [zeller.emails.zeller_email] user = [ "p_zeller", ] host = [ "cs", "uni-kl", "de", ] [zeller.homepages] [zeyda] name = "Frank Zeyda" [zeyda.emails] [zeyda.emails.zeyda_email] user = [ "frank", "zeyda", ] host = [ "york", "ac", "uk", ] [zeyda.homepages] [zhan] name = "Bohua Zhan" [zhan.emails] [zhan.emails.zhan_email] user = [ "bzhan", ] host = [ "ios", "ac", "cn", ] [zhan.homepages] zhan_homepage = "http://lcs.ios.ac.cn/~bzhan/" [zhang] name = "Yu Zhang" [zhang.emails] [zhang.homepages] [zhangx] name = "Xingyuan Zhang" [zhangx.emails] [zhangx.homepages] [zhann] name = "Naijun Zhan" [zhann.emails] [zhann.homepages] diff --git a/metadata/entries/Refine_Imperative_HOL.toml b/metadata/entries/Refine_Imperative_HOL.toml --- a/metadata/entries/Refine_Imperative_HOL.toml +++ b/metadata/entries/Refine_Imperative_HOL.toml @@ -1,46 +1,48 @@ title = "The Imperative Refinement Framework" date = 2016-08-08 topics = [ "Computer science/Semantics and reasoning", "Computer science/Data structures", ] abstract = """ We present the Imperative Refinement Framework (IRF), a tool that supports a stepwise refinement based approach to imperative programs. This entry is based on the material we presented in [ITP-2015, CPP-2016]. It uses the Monadic Refinement Framework as a frontend for the specification of the abstract programs, and Imperative/HOL as a backend to generate executable imperative programs. The IRF comes with tool support to synthesize imperative programs from more abstract, functional ones, using efficient imperative implementations for the abstract data structures. This entry also includes the Imperative Isabelle Collection Framework (IICF), which provides a library of re-usable imperative collection data structures. Moreover, this entry contains a quickstart guide and a reference manual, which provide an introduction to using the IRF for Isabelle/HOL experts. It also provids a collection of (partly commented) practical examples, some highlights being Dijkstra's Algorithm, Nested-DFS, and a generic worklist algorithm with subsumption. Finally, this entry contains benchmark scripts that compare the runtime of some examples against reference implementations of the algorithms in Java and C++. [ITP-2015] Peter Lammich: Refinement to Imperative/HOL. ITP 2015: 253--269 [CPP-2016] Peter Lammich: Refinement based verification of imperative data structures. CPP 2016: 27--36""" license = "bsd" note = "" [authors] [authors.lammich] homepage = "lammich_homepage" [contributors] +[contributors.springsklee] + [notify] lammich = "lammich_email" [history] [extra] [related] diff --git a/metadata/entries/Separation_Logic_Imperative_HOL.toml b/metadata/entries/Separation_Logic_Imperative_HOL.toml --- a/metadata/entries/Separation_Logic_Imperative_HOL.toml +++ b/metadata/entries/Separation_Logic_Imperative_HOL.toml @@ -1,39 +1,41 @@ title = "A Separation Logic Framework for Imperative HOL" date = 2012-11-14 topics = [ "Computer science/Programming languages/Logics", ] abstract = """ We provide a framework for separation-logic based correctness proofs of Imperative HOL programs. Our framework comes with a set of proof methods to automate canonical tasks such as verification condition generation and frame inference. Moreover, we provide a set of examples that show the applicability of our framework. The examples include algorithms on lists, hash-tables, and union-find trees. We also provide abstract interfaces for lists, maps, and sets, that allow to develop generic imperative algorithms and use data-refinement techniques.
As we target Imperative HOL, our programs can be translated to efficiently executable code in various target languages, including ML, OCaml, Haskell, and Scala.""" license = "bsd" note = "" [authors] [authors.lammich] homepage = "lammich_homepage" [authors.meis] email = "meis_email1" [contributors] +[contributors.springsklee] + [notify] lammich = "lammich_email" [history] [extra] [related] diff --git a/thys/Automatic_Refinement/Parametricity/Param_HOL.thy b/thys/Automatic_Refinement/Parametricity/Param_HOL.thy --- a/thys/Automatic_Refinement/Parametricity/Param_HOL.thy +++ b/thys/Automatic_Refinement/Parametricity/Param_HOL.thy @@ -1,568 +1,575 @@ section \Parametricity Theorems for HOL\ theory Param_HOL imports Param_Tool begin subsection \Sets\ lemma param_empty[param]: "({},{})\\R\set_rel" by (auto simp: set_rel_def) lemma param_member[param]: "\single_valued R; single_valued (R\)\ \ ((\), (\)) \ R \ \R\set_rel \ bool_rel" unfolding set_rel_def by (blast dest: single_valuedD) lemma param_insert[param]: "(insert,insert)\R\\R\set_rel\\R\set_rel" by (auto simp: set_rel_def) lemma param_union[param]: "((\), (\)) \ \R\set_rel \ \R\set_rel \ \R\set_rel" by (auto simp: set_rel_def) lemma param_inter[param]: assumes "single_valued R" "single_valued (R\)" shows "((\), (\)) \ \R\set_rel \ \R\set_rel \ \R\set_rel" using assms unfolding set_rel_def by (blast dest: single_valuedD) lemma param_diff[param]: assumes "single_valued R" "single_valued (R\)" shows "((-), (-)) \ \R\set_rel \ \R\set_rel \ \R\set_rel" using assms unfolding set_rel_def by (blast dest: single_valuedD) lemma param_subseteq[param]: "\single_valued R; single_valued (R\)\ \ ((\), (\)) \ \R\set_rel \ \R\set_rel \ bool_rel" unfolding set_rel_def by (blast dest: single_valuedD) lemma param_subset[param]: "\single_valued R; single_valued (R\)\ \ ((\), (\)) \ \R\set_rel \ \R\set_rel \ bool_rel" unfolding set_rel_def by (blast dest: single_valuedD) lemma param_Ball[param]: "(Ball,Ball)\\Ra\set_rel\(Ra\Id)\Id" by (force simp: set_rel_alt dest: fun_relD) lemma param_Bex[param]: "(Bex,Bex)\\Ra\set_rel\(Ra\Id)\Id" by (fastforce simp: set_rel_def dest: fun_relD) lemma param_set[param]: "single_valued Ra \ (set,set)\\Ra\list_rel \ \Ra\set_rel" proof fix l l' assume A: "single_valued Ra" assume "(l,l')\\Ra\list_rel" thus "(set l, set l')\\Ra\set_rel" apply (induct) apply simp apply simp using A apply (parametricity) done qed lemma param_Collect[param]: "\Domain A = UNIV; Range A = UNIV\ \ (Collect,Collect)\(A\bool_rel) \ \A\set_rel" unfolding set_rel_def apply (clarsimp; safe) subgoal using fun_relD1 by fastforce subgoal using fun_relD2 by fastforce done lemma param_finite[param]: "\ single_valued R; single_valued (R\) \ \ (finite,finite) \ \R\set_rel \ bool_rel" using finite_set_rel_transfer finite_set_rel_transfer_back by blast - + +lemma param_card[param]: "\single_valued R; single_valued (R\)\ + \ (card, card) \ \R\set_rel \nat_rel" + apply (rule rel2pD) + apply (simp only: rel2p) + apply (rule card_transfer) + by (simp add: rel2p_bi_unique) + subsection \Standard HOL Constructs\ lemma param_if[param]: assumes "(c,c')\Id" assumes "\c;c'\ \ (t,t')\R" assumes "\\c;\c'\ \ (e,e')\R" shows "(If c t e, If c' t' e')\R" using assms by auto lemma param_Let[param]: "(Let,Let)\Ra \ (Ra\Rr) \ Rr" by (auto dest: fun_relD) subsection \Functions\ lemma param_id[param]: "(id,id)\R\R" unfolding id_def by parametricity lemma param_fun_comp[param]: "((o), (o)) \ (Ra\Rb) \ (Rc\Ra) \ Rc\Rb" unfolding comp_def[abs_def] by parametricity lemma param_fun_upd[param]: " ((=), (=)) \ Ra\Ra\Id \ (fun_upd,fun_upd) \ (Ra\Rb) \ Ra \ Rb \ Ra \ Rb" unfolding fun_upd_def[abs_def] by (parametricity) subsection \Boolean\ lemma rec_bool_is_case: "old.rec_bool = case_bool" by (rule ext)+ (auto split: bool.split) lemma param_bool[param]: "(True,True)\Id" "(False,False)\Id" "(conj,conj)\Id\Id\Id" "(disj,disj)\Id\Id\Id" "(Not,Not)\Id\Id" "(case_bool,case_bool)\R\R\Id\R" "(old.rec_bool,old.rec_bool)\R\R\Id\R" "((\), (\))\Id\Id\Id" "((\), (\))\Id\Id\Id" by (auto split: bool.split simp: rec_bool_is_case) lemma param_and_cong1: "\ (a,a')\bool_rel; \a; a'\ \ (b,b')\bool_rel \ \ (a\b,a'\b')\bool_rel" by blast lemma param_and_cong2: "\ (a,a')\bool_rel; \a; a'\ \ (b,b')\bool_rel \ \ (b\a,b'\a')\bool_rel" by blast subsection \Nat\ lemma param_nat1[param]: "(0, 0::nat) \ Id" "(Suc, Suc) \ Id \ Id" "(1, 1::nat) \ Id" "(numeral n::nat,numeral n::nat) \ Id" "((<), (<) ::nat \ _) \ Id \ Id \ Id" "((\), (\) ::nat \ _) \ Id \ Id \ Id" "((=), (=) ::nat \ _) \ Id \ Id \ Id" "((+) ::nat\_,(+))\Id\Id\Id" "((-) ::nat\_,(-))\Id\Id\Id" "((*) ::nat\_,(*))\Id\Id\Id" "((div) ::nat\_,(div))\Id\Id\Id" "((mod) ::nat\_,(mod))\Id\Id\Id" by auto lemma param_case_nat[param]: "(case_nat,case_nat)\Ra \ (Id \ Ra) \ Id \ Ra" apply (intro fun_relI) apply (auto split: nat.split dest: fun_relD) done lemma param_rec_nat[param]: "(rec_nat,rec_nat) \ R \ (Id \ R \ R) \ Id \ R" proof (intro fun_relI, goal_cases) case (1 s s' f f' n n') thus ?case apply (induct n' arbitrary: n s s') apply (fastforce simp: fun_rel_def)+ done qed subsection \Int\ lemma param_int[param]: "(0, 0::int) \ Id" "(1, 1::int) \ Id" "(numeral n::int,numeral n::int) \ Id" "((<), (<) ::int \ _) \ Id \ Id \ Id" "((\), (\) ::int \ _) \ Id \ Id \ Id" "((=), (=) ::int \ _) \ Id \ Id \ Id" "((+) ::int\_,(+))\Id\Id\Id" "((-) ::int\_,(-))\Id\Id\Id" "((*) ::int\_,(*))\Id\Id\Id" "((div) ::int\_,(div))\Id\Id\Id" "((mod) ::int\_,(mod))\Id\Id\Id" by auto subsection \Product\ lemma param_unit[param]: "((),())\unit_rel" by auto lemma rec_prod_is_case: "old.rec_prod = case_prod" by (rule ext)+ (auto split: bool.split) lemma param_prod[param]: "(Pair,Pair)\Ra \ Rb \ \Ra,Rb\prod_rel" "(case_prod,case_prod) \ (Ra \ Rb \ Rr) \ \Ra,Rb\prod_rel \ Rr" "(old.rec_prod,old.rec_prod) \ (Ra \ Rb \ Rr) \ \Ra,Rb\prod_rel \ Rr" "(fst,fst)\\Ra,Rb\prod_rel \ Ra" "(snd,snd)\\Ra,Rb\prod_rel \ Rb" by (auto dest: fun_relD split: prod.split simp: prod_rel_def rec_prod_is_case) lemma param_case_prod': "\ (p,p')\\Ra,Rb\prod_rel; \a b a' b'. \ p=(a,b); p'=(a',b'); (a,a')\Ra; (b,b')\Rb \ \ (f a b, f' a' b')\R \ \ (case_prod f p, case_prod f' p') \ R" by (auto split: prod.split) lemma param_case_prod'': (* TODO: Really needed? *) "\ \a b a' b'. \p=(a,b); p'=(a',b')\ \ (f a b,f' a' b')\R \ \ (case_prod f p, case_prod f' p')\R" by (auto split: prod.split) lemma param_map_prod[param]: "(map_prod, map_prod) \ (Ra\Rb) \ (Rc\Rd) \ \Ra,Rc\prod_rel \ \Rb,Rd\prod_rel" unfolding map_prod_def[abs_def] by parametricity lemma param_apfst[param]: "(apfst,apfst)\(Ra\Rb)\\Ra,Rc\prod_rel\\Rb,Rc\prod_rel" unfolding apfst_def[abs_def] by parametricity lemma param_apsnd[param]: "(apsnd,apsnd)\(Rb\Rc)\\Ra,Rb\prod_rel\\Ra,Rc\prod_rel" unfolding apsnd_def[abs_def] by parametricity lemma param_curry[param]: "(curry,curry) \ (\Ra,Rb\prod_rel \ Rc) \ Ra \ Rb \ Rc" unfolding curry_def by parametricity lemma param_uncurry[param]: "(uncurry,uncurry) \ (A\B\C) \ A\\<^sub>rB\C" unfolding uncurry_def[abs_def] by parametricity lemma param_prod_swap[param]: "(prod.swap, prod.swap)\A\\<^sub>rB \ B\\<^sub>rA" by auto context partial_function_definitions begin lemma assumes M: "monotone le_fun le_fun F" and M': "monotone le_fun le_fun F'" assumes ADM: "admissible (\a. \x xa. (x, xa) \ Rb \ (a x, fixp_fun F' xa) \ Ra)" assumes bot: "\x xa. (x, xa) \ Rb \ (lub {}, fixp_fun F' xa) \ Ra" assumes F: "(F,F')\(Rb\Ra)\Rb\Ra" assumes A: "(x,x')\Rb" shows "(fixp_fun F x, fixp_fun F' x')\Ra" using A apply (induct arbitrary: x x' rule: ccpo.fixp_induct[OF ccpo _ M]) apply (rule ADM) apply(simp add: fun_lub_def bot) apply (subst ccpo.fixp_unfold[OF ccpo M']) apply (parametricity add: F) done end subsection \Option\ lemma param_option[param]: "(None,None)\\R\option_rel" "(Some,Some)\R \ \R\option_rel" "(case_option,case_option)\Rr\(R \ Rr)\\R\option_rel \ Rr" "(rec_option,rec_option)\Rr\(R \ Rr)\\R\option_rel \ Rr" by (auto split: option.split simp: option_rel_def case_option_def[symmetric] dest: fun_relD) lemma param_map_option[param]: "(map_option, map_option) \ (A \ B) \ \A\option_rel \ \B\option_rel" apply (intro fun_relI) apply (auto elim!: option_relE dest: fun_relD) done lemma param_case_option': "\ (x,x')\\Rv\option_rel; \x=None; x'=None \ \ (fn,fn')\R; \v v'. \ x=Some v; x'=Some v'; (v,v')\Rv \ \ (fs v, fs' v')\R \ \ (case_option fn fs x, case_option fn' fs' x') \ R" by (auto split: option.split) lemma the_paramL: "\l\None; (l,r)\\R\option_rel\ \ (the l, the r)\R" apply (cases l) by (auto elim: option_relE) lemma the_paramR: "\r\None; (l,r)\\R\option_rel\ \ (the l, the r)\R" apply (cases l) by (auto elim: option_relE) lemma the_default_param[param]: "(the_default, the_default) \ R \ \R\option_rel \ R" unfolding the_default_def by parametricity subsection \Sum\ lemma rec_sum_is_case: "old.rec_sum = case_sum" by (rule ext)+ (auto split: sum.split) lemma param_sum[param]: "(Inl,Inl) \ Rl \ \Rl,Rr\sum_rel" "(Inr,Inr) \ Rr \ \Rl,Rr\sum_rel" "(case_sum,case_sum) \ (Rl \ R) \ (Rr \ R) \ \Rl,Rr\sum_rel \ R" "(old.rec_sum,old.rec_sum) \ (Rl \ R) \ (Rr \ R) \ \Rl,Rr\sum_rel \ R" by (fastforce split: sum.split dest: fun_relD simp: rec_sum_is_case)+ lemma param_case_sum': "\ (s,s')\\Rl,Rr\sum_rel; \l l'. \ s=Inl l; s'=Inl l'; (l,l')\Rl \ \ (fl l, fl' l')\R; \r r'. \ s=Inr r; s'=Inr r'; (r,r')\Rr \ \ (fr r, fr' r')\R \ \ (case_sum fl fr s, case_sum fl' fr' s')\R" by (auto split: sum.split) primrec is_Inl where "is_Inl (Inl _) = True" | "is_Inl (Inr _) = False" primrec is_Inr where "is_Inr (Inr _) = True" | "is_Inr (Inl _) = False" lemma is_Inl_param[param]: "(is_Inl,is_Inl) \ \Ra,Rb\sum_rel \ bool_rel" unfolding is_Inl_def by parametricity lemma is_Inr_param[param]: "(is_Inr,is_Inr) \ \Ra,Rb\sum_rel \ bool_rel" unfolding is_Inr_def by parametricity lemma sum_projl_param[param]: "\is_Inl s; (s',s)\\Ra,Rb\sum_rel\ \ (Sum_Type.sum.projl s',Sum_Type.sum.projl s) \ Ra" apply (cases s) apply (auto elim: sum_relE) done lemma sum_projr_param[param]: "\is_Inr s; (s',s)\\Ra,Rb\sum_rel\ \ (Sum_Type.sum.projr s',Sum_Type.sum.projr s) \ Rb" apply (cases s) apply (auto elim: sum_relE) done subsection \List\ lemma list_rel_append1: "(as @ bs, l) \ \R\list_rel \ (\cs ds. l = cs@ds \ (as,cs)\\R\list_rel \ (bs,ds)\\R\list_rel)" apply (simp add: list_rel_def list_all2_append1) apply auto apply (metis list_all2_lengthD) done lemma list_rel_append2: "(l,as @ bs) \ \R\list_rel \ (\cs ds. l = cs@ds \ (cs,as)\\R\list_rel \ (ds,bs)\\R\list_rel)" apply (simp add: list_rel_def list_all2_append2) apply auto apply (metis list_all2_lengthD) done lemma param_append[param]: "(append, append)\\R\list_rel \ \R\list_rel \ \R\list_rel" by (auto simp: list_rel_def list_all2_appendI) lemma param_list1[param]: "(Nil,Nil)\\R\list_rel" "(Cons,Cons)\R \ \R\list_rel \ \R\list_rel" "(case_list,case_list)\Rr\(R\\R\list_rel\Rr)\\R\list_rel\Rr" apply (force dest: fun_relD split: list.split)+ done lemma param_rec_list[param]: "(rec_list,rec_list) \ Ra \ (Rb \ \Rb\list_rel \ Ra \ Ra) \ \Rb\list_rel \ Ra" proof (intro fun_relI, goal_cases) case prems: (1 a a' f f' l l') from prems(3) show ?case using prems(1,2) apply (induct arbitrary: a a') apply simp apply (fastforce dest: fun_relD) done qed lemma param_case_list': "\ (l,l')\\Rb\list_rel; \l=[]; l'=[]\ \ (n,n')\Ra; \x xs x' xs'. \ l=x#xs; l'=x'#xs'; (x,x')\Rb; (xs,xs')\\Rb\list_rel \ \ (c x xs, c' x' xs')\Ra \ \ (case_list n c l, case_list n' c' l') \ Ra" by (auto split: list.split) lemma param_map[param]: "(map,map)\(R1\R2) \ \R1\list_rel \ \R2\list_rel" unfolding map_rec[abs_def] by (parametricity) lemma param_fold[param]: "(fold,fold)\(Re\Rs\Rs) \ \Re\list_rel \ Rs \ Rs" "(foldl,foldl)\(Rs\Re\Rs) \ Rs \ \Re\list_rel \ Rs" "(foldr,foldr)\(Re\Rs\Rs) \ \Re\list_rel \ Rs \ Rs" unfolding List.fold_def List.foldr_def List.foldl_def by (parametricity)+ lemma param_list_all[param]: "(list_all,list_all) \ (A\bool_rel) \ \A\list_rel \ bool_rel" by (fold rel2p_def) (simp add: rel2p List.list_all_transfer) context begin private primrec list_all2_alt :: "('a \ 'b \ bool) \ 'a list \ 'b list \ bool" where "list_all2_alt P [] ys \ (case ys of [] \ True | _ \ False)" | "list_all2_alt P (x#xs) ys \ (case ys of [] \ False | y#ys \ P x y \ list_all2_alt P xs ys)" private lemma list_all2_alt: "list_all2 P xs ys = list_all2_alt P xs ys" by (induction xs arbitrary: ys) (auto split: list.splits) lemma param_list_all2[param]: "(list_all2, list_all2) \ (A\B\bool_rel) \ \A\list_rel \ \B\list_rel \ bool_rel" unfolding list_all2_alt[abs_def] unfolding list_all2_alt_def[abs_def] by parametricity end lemma param_hd[param]: "l\[] \ (l',l)\\A\list_rel \ (hd l', hd l)\A" unfolding hd_def by (auto split: list.splits) lemma param_last[param]: assumes "y \ []" assumes "(x, y) \ \A\list_rel" shows "(last x, last y) \ A" using assms(2,1) by (induction rule: list_rel_induct) auto lemma param_rotate1[param]: "(rotate1, rotate1) \ \A\list_rel \ \A\list_rel" unfolding rotate1_def by parametricity schematic_goal param_take[param]: "(take,take)\(?R::(_\_) set)" unfolding take_def by (parametricity) schematic_goal param_drop[param]: "(drop,drop)\(?R::(_\_) set)" unfolding drop_def by (parametricity) schematic_goal param_length[param]: "(length,length)\(?R::(_\_) set)" unfolding size_list_overloaded_def size_list_def by (parametricity) fun list_eq :: "('a \ 'a \ bool) \ 'a list \ 'a list \ bool" where "list_eq eq [] [] \ True" | "list_eq eq (a#l) (a'#l') \ (if eq a a' then list_eq eq l l' else False)" | "list_eq _ _ _ \ False" lemma param_list_eq[param]: " (list_eq,list_eq) \ (R \ R \ Id) \ \R\list_rel \ \R\list_rel \ Id" proof (intro fun_relI, goal_cases) case prems: (1 eq eq' l1 l1' l2 l2') thus ?case apply - apply (induct eq' l1' l2' arbitrary: l1 l2 rule: list_eq.induct) apply (simp_all only: list_eq.simps | elim list_relE | parametricity)+ done qed lemma id_list_eq_aux[simp]: "(list_eq (=)) = (=)" proof (intro ext) fix l1 l2 :: "'a list" show "list_eq (=) l1 l2 = (l1 = l2)" apply (induct "(=) :: 'a \ _" l1 l2 rule: list_eq.induct) apply simp_all done qed lemma param_list_equals[param]: "\ ((=), (=)) \ R\R\Id \ \ ((=), (=)) \ \R\list_rel \ \R\list_rel \ Id" unfolding id_list_eq_aux[symmetric] by (parametricity) lemma param_tl[param]: "(tl,tl) \ \R\list_rel \ \R\list_rel" unfolding tl_def[abs_def] by (parametricity) primrec list_all_rec where "list_all_rec P [] \ True" | "list_all_rec P (a#l) \ P a \ list_all_rec P l" primrec list_ex_rec where "list_ex_rec P [] \ False" | "list_ex_rec P (a#l) \ P a \ list_ex_rec P l" lemma list_all_rec_eq: "(\x\set l. P x) = list_all_rec P l" by (induct l) auto lemma list_ex_rec_eq: "(\x\set l. P x) = list_ex_rec P l" by (induct l) auto lemma param_list_ball[param]: "\(P,P')\(Ra\Id); (l,l')\\Ra\ list_rel\ \ (\x\set l. P x, \x\set l'. P' x) \ Id" unfolding list_all_rec_eq unfolding list_all_rec_def by (parametricity) lemma param_list_bex[param]: "\(P,P')\(Ra\Id); (l,l')\\Ra\ list_rel\ \ (\x\set l. P x, \x\set l'. P' x) \ Id" unfolding list_ex_rec_eq[abs_def] unfolding list_ex_rec_def by (parametricity) lemma param_rev[param]: "(rev,rev) \ \R\list_rel \ \R\list_rel" unfolding rev_def by (parametricity) lemma param_foldli[param]: "(foldli, foldli) \ \Re\list_rel \ (Rs\Id) \ (Re\Rs\Rs) \ Rs \ Rs" unfolding foldli_def by parametricity lemma param_foldri[param]: "(foldri, foldri) \ \Re\list_rel \ (Rs\Id) \ (Re\Rs\Rs) \ Rs \ Rs" unfolding foldri_def[abs_def] by parametricity lemma param_nth[param]: assumes I: "i'nat_rel" assumes LR: "(l,l')\\R\list_rel" shows "(l!i,l'!i') \ R" using LR I IR by (induct arbitrary: i i' rule: list_rel_induct) (auto simp: nth.simps split: nat.split) lemma param_replicate[param]: "(replicate,replicate) \ nat_rel \ R \ \R\list_rel" unfolding replicate_def by parametricity term list_update lemma param_list_update[param]: "(list_update,list_update) \ \Ra\list_rel \ nat_rel \ Ra \ \Ra\list_rel" unfolding list_update_def[abs_def] by parametricity lemma param_zip[param]: "(zip, zip) \ \Ra\list_rel \ \Rb\list_rel \ \\Ra,Rb\prod_rel\list_rel" unfolding zip_def by parametricity lemma param_upt[param]: "(upt, upt) \ nat_rel \ nat_rel \ \nat_rel\list_rel" unfolding upt_def[abs_def] by parametricity lemma param_concat[param]: "(concat, concat) \ \\R\list_rel\list_rel \ \R\list_rel" unfolding concat_def[abs_def] by parametricity lemma param_all_interval_nat[param]: "(List.all_interval_nat, List.all_interval_nat) \ (nat_rel \ bool_rel) \ nat_rel \ nat_rel \ bool_rel" unfolding List.all_interval_nat_def[abs_def] apply parametricity apply simp done lemma param_dropWhile[param]: "(dropWhile, dropWhile) \ (a \ bool_rel) \ \a\list_rel \ \a\list_rel" unfolding dropWhile_def by parametricity lemma param_takeWhile[param]: "(takeWhile, takeWhile) \ (a \ bool_rel) \ \a\list_rel \ \a\list_rel" unfolding takeWhile_def by parametricity end diff --git a/thys/Automatic_Refinement/Parametricity/Relators.thy b/thys/Automatic_Refinement/Parametricity/Relators.thy --- a/thys/Automatic_Refinement/Parametricity/Relators.thy +++ b/thys/Automatic_Refinement/Parametricity/Relators.thy @@ -1,978 +1,992 @@ section \Relators\ theory Relators imports "../Lib/Refine_Lib" begin text \ We define the concept of relators. The relation between a concrete type and an abstract type is expressed by a relation of type \('c\'a) set\. For each composed type, say \'a list\, we can define a {\em relator}, that takes as argument a relation for the element type, and returns a relation for the list type. For most datatypes, there exists a {\em natural relator}. For algebraic datatypes, this is the relator that preserves the structure of the datatype, and changes the components. For example, \list_rel::('c\'a) set \ ('c list\'a list) set\ is the natural relator for lists. However, relators can also be used to change the representation, and thus relate an implementation with an abstract type. For example, the relator \list_set_rel::('c\'a) set \ ('c list\'a set) set\ relates lists with the set of their elements. In this theory, we define some basic notions for relators, and then define natural relators for all HOL-types, including the function type. For each relator, we also show a single-valuedness property, and initialize a solver for single-valued properties. \ subsection \Basic Definitions\ text \ For smoother handling of relator unification, we require relator arguments to be applied by a special operator, such that we avoid higher-order unification problems. We try to set up some syntax to make this more transparent, and give relators a type-like prefix-syntax. \ definition relAPP :: "(('c1\'a1) set \ _) \ ('c1\'a1) set \ _" where "relAPP f x \ f x" syntax "_rel_APP" :: "args \ 'a \ 'b" ("\_\_" [0,900] 900) translations "\x,xs\R" == "\xs\(CONST relAPP R x)" "\x\R" == "CONST relAPP R x" ML \ structure Refine_Relators_Thms = struct structure rel_comb_def_rules = Named_Thms ( val name = @{binding refine_rel_defs} val description = "Refinement Framework: " ^ "Relator definitions" ); end \ setup Refine_Relators_Thms.rel_comb_def_rules.setup subsection \Basic HOL Relators\ subsubsection \Function\ definition fun_rel where fun_rel_def_internal: "fun_rel A B \ { (f,f'). \(a,a')\A. (f a, f' a')\B }" abbreviation fun_rel_syn (infixr "\" 60) where "A\B \ \A,B\fun_rel" lemma fun_rel_def[refine_rel_defs]: "A\B \ { (f,f'). \(a,a')\A. (f a, f' a')\B }" by (simp add: relAPP_def fun_rel_def_internal) lemma fun_relI[intro!]: "\\a a'. (a,a')\A \ (f a,f' a')\B\ \ (f,f')\A\B" by (auto simp: fun_rel_def) lemma fun_relD: shows " ((f,f')\(A\B)) \ (\x x'. \ (x,x')\A \ \ (f x, f' x')\B)" apply rule by (auto simp: fun_rel_def) lemma fun_relD1: assumes "(f,f')\Ra\Rr" assumes "f x = r" shows "\x'. (x,x')\Ra \ (r,f' x')\Rr" using assms by (auto simp: fun_rel_def) lemma fun_relD2: assumes "(f,f')\Ra\Rr" assumes "f' x' = r'" shows "\x. (x,x')\Ra \ (f x,r')\Rr" using assms by (auto simp: fun_rel_def) lemma fun_relE1: assumes "(f,f')\Id \ Rv" assumes "t' = f' x" shows "(f x,t')\Rv" using assms by (auto elim: fun_relD) lemma fun_relE2: assumes "(f,f')\Id \ Rv" assumes "t = f x" shows "(t,f' x)\Rv" using assms by (auto elim: fun_relD) subsubsection \Terminal Types\ abbreviation unit_rel :: "(unit\unit) set" where "unit_rel == Id" abbreviation "nat_rel \ Id::(nat\_) set" abbreviation "int_rel \ Id::(int\_) set" abbreviation "bool_rel \ Id::(bool\_) set" subsubsection \Product\ definition prod_rel where prod_rel_def_internal: "prod_rel R1 R2 \ { ((a,b),(a',b')) . (a,a')\R1 \ (b,b')\R2 }" abbreviation prod_rel_syn (infixr "\\<^sub>r" 70) where "a\\<^sub>rb \ \a,b\prod_rel" lemma prod_rel_def[refine_rel_defs]: "(\R1,R2\prod_rel) \ { ((a,b),(a',b')) . (a,a')\R1 \ (b,b')\R2 }" by (simp add: prod_rel_def_internal relAPP_def) lemma prod_relI: "\(a,a')\R1; (b,b')\R2\ \ ((a,b),(a',b'))\\R1,R2\prod_rel" by (auto simp: prod_rel_def) lemma prod_relE: assumes "(p,p')\\R1,R2\prod_rel" obtains a b a' b' where "p=(a,b)" and "p'=(a',b')" and "(a,a')\R1" and "(b,b')\R2" using assms by (auto simp: prod_rel_def) lemma prod_rel_simp[simp]: "((a,b),(a',b'))\\R1,R2\prod_rel \ (a,a')\R1 \ (b,b')\R2" by (auto intro: prod_relI elim: prod_relE) lemma in_Domain_prod_rel_iff[iff]: "(a,b)\Domain (A\\<^sub>rB) \ a\Domain A \ b\Domain B" by (auto simp: prod_rel_def) lemma prod_rel_comp: "(A \\<^sub>r B) O (C \\<^sub>r D) = (A O C) \\<^sub>r (B O D)" unfolding prod_rel_def by auto subsubsection \Option\ definition option_rel where option_rel_def_internal: "option_rel R \ { (Some a,Some a') | a a'. (a,a')\R } \ {(None,None)}" lemma option_rel_def[refine_rel_defs]: "\R\option_rel \ { (Some a,Some a') | a a'. (a,a')\R } \ {(None,None)}" by (simp add: option_rel_def_internal relAPP_def) lemma option_relI: "(None,None)\\R\ option_rel" "\ (a,a')\R \ \ (Some a, Some a')\\R\option_rel" by (auto simp: option_rel_def) lemma option_relE: assumes "(x,x')\\R\option_rel" obtains "x=None" and "x'=None" | a a' where "x=Some a" and "x'=Some a'" and "(a,a')\R" using assms by (auto simp: option_rel_def) lemma option_rel_simp[simp]: "(None,a)\\R\option_rel \ a=None" "(c,None)\\R\option_rel \ c=None" "(Some x,Some y)\\R\option_rel \ (x,y)\R" by (auto intro: option_relI elim: option_relE) subsubsection \Sum\ definition sum_rel where sum_rel_def_internal: "sum_rel Rl Rr \ { (Inl a, Inl a') | a a'. (a,a')\Rl } \ { (Inr a, Inr a') | a a'. (a,a')\Rr }" lemma sum_rel_def[refine_rel_defs]: "\Rl,Rr\sum_rel \ { (Inl a, Inl a') | a a'. (a,a')\Rl } \ { (Inr a, Inr a') | a a'. (a,a')\Rr }" by (simp add: sum_rel_def_internal relAPP_def) lemma sum_rel_simp[simp]: "\a a'. (Inl a, Inl a') \ \Rl,Rr\sum_rel \ (a,a')\Rl" "\a a'. (Inr a, Inr a') \ \Rl,Rr\sum_rel \ (a,a')\Rr" "\a a'. (Inl a, Inr a') \ \Rl,Rr\sum_rel" "\a a'. (Inr a, Inl a') \ \Rl,Rr\sum_rel" unfolding sum_rel_def by auto lemma sum_relI: "(l,l')\Rl \ (Inl l, Inl l') \ \Rl,Rr\sum_rel" "(r,r')\Rr \ (Inr r, Inr r') \ \Rl,Rr\sum_rel" by simp_all lemma sum_relE: assumes "(x,x')\\Rl,Rr\sum_rel" obtains l l' where "x=Inl l" and "x'=Inl l'" and "(l,l')\Rl" | r r' where "x=Inr r" and "x'=Inr r'" and "(r,r')\Rr" using assms by (auto simp: sum_rel_def) subsubsection \Lists\ definition list_rel where list_rel_def_internal: "list_rel R \ {(l,l'). list_all2 (\x x'. (x,x')\R) l l'}" lemma list_rel_def[refine_rel_defs]: "\R\list_rel \ {(l,l'). list_all2 (\x x'. (x,x')\R) l l'}" by (simp add: list_rel_def_internal relAPP_def) lemma list_rel_induct[induct set,consumes 1, case_names Nil Cons]: assumes "(l,l')\\R\ list_rel" assumes "P [] []" assumes "\x x' l l'. \ (x,x')\R; (l,l')\\R\list_rel; P l l' \ \ P (x#l) (x'#l')" shows "P l l'" using assms unfolding list_rel_def apply simp by (rule list_all2_induct) lemma list_rel_eq_listrel: "list_rel = listrel" apply (rule ext) apply safe proof goal_cases case (1 x a b) thus ?case unfolding list_rel_def_internal apply simp apply (induct a b rule: list_all2_induct) apply (auto intro: listrel.intros) done next case 2 thus ?case apply (induct) apply (auto simp: list_rel_def_internal) done qed lemma list_relI: "([],[])\\R\list_rel" "\ (x,x')\R; (l,l')\\R\list_rel \ \ (x#l,x'#l')\\R\list_rel" by (auto simp: list_rel_def) lemma list_rel_simp[simp]: "([],l')\\R\list_rel \ l'=[]" "(l,[])\\R\list_rel \ l=[]" "([],[])\\R\list_rel" "(x#l,x'#l')\\R\list_rel \ (x,x')\R \ (l,l')\\R\list_rel" by (auto simp: list_rel_def) lemma list_relE1: assumes "(l,[])\\R\list_rel" obtains "l=[]" using assms by auto lemma list_relE2: assumes "([],l)\\R\list_rel" obtains "l=[]" using assms by auto lemma list_relE3: assumes "(x#xs,l')\\R\list_rel" obtains x' xs' where "l'=x'#xs'" and "(x,x')\R" and "(xs,xs')\\R\list_rel" using assms apply (cases l') apply auto done lemma list_relE4: assumes "(l,x'#xs')\\R\list_rel" obtains x xs where "l=x#xs" and "(x,x')\R" and "(xs,xs')\\R\list_rel" using assms apply (cases l) apply auto done lemmas list_relE = list_relE1 list_relE2 list_relE3 list_relE4 lemma list_rel_imp_same_length: "(l, l') \ \R\list_rel \ length l = length l'" unfolding list_rel_eq_listrel relAPP_def by (rule listrel_eq_len) lemma list_rel_split_right_iff: "(x#xs,l)\\R\list_rel \ (\y ys. l=y#ys \ (x,y)\R \ (xs,ys)\\R\list_rel)" by (cases l) auto lemma list_rel_split_left_iff: "(l,y#ys)\\R\list_rel \ (\x xs. l=x#xs \ (x,y)\R \ (xs,ys)\\R\list_rel)" by (cases l) auto subsubsection \Sets\ text \Pointwise refinement: The abstract set is the image of the concrete set, and the concrete set only contains elements that have an abstract counterpart\ definition set_rel where set_rel_def_internal: "set_rel R \ {(A,B). (\x\A. \y\B. (x,y)\R) \ (\y\B. \x\A. (x,y)\R)}" term set_rel lemma set_rel_def[refine_rel_defs]: "\R\set_rel \ {(A,B). (\x\A. \y\B. (x,y)\R) \ (\y\B. \x\A. (x,y)\R)}" by (simp add: set_rel_def_internal relAPP_def) lemma set_rel_alt: "\R\set_rel = {(A,B). A \ R\``B \ B \ R``A}" unfolding set_rel_def by auto lemma set_relI[intro?]: assumes "\x. x\A \ \y\B. (x,y)\R" assumes "\y. y\B \ \x\A. (x,y)\R" shows "(A,B)\\R\set_rel" using assms unfolding set_rel_def by blast text \Original definition of \set_rel\ in refinement framework. Abandoned in favour of more symmetric definition above: \ definition old_set_rel where old_set_rel_def_internal: "old_set_rel R \ {(S,S'). S'=R``S \ S\Domain R}" lemma old_set_rel_def[refine_rel_defs]: "\R\old_set_rel \ {(S,S'). S'=R``S \ S\Domain R}" by (simp add: old_set_rel_def_internal relAPP_def) text \Old definition coincides with new definition for single-valued element relations. This is probably the reason why the old definition worked for most applications.\ lemma old_set_rel_sv_eq: "single_valued R \ \R\old_set_rel = \R\set_rel" unfolding set_rel_def old_set_rel_def single_valued_def by blast lemma set_rel_simp[simp]: "({},{})\\R\set_rel" by (auto simp: set_rel_def) lemma set_rel_empty_iff[simp]: "({},y)\\A\set_rel \ y={}" "(x,{})\\A\set_rel \ x={}" by (auto simp: set_rel_def; fastforce)+ lemma set_relD1: "(s,s')\\R\set_rel \ x\s \ \x'\s'. (x,x')\R" unfolding set_rel_def by blast lemma set_relD2: "(s,s')\\R\set_rel \ x'\s' \ \x\s. (x,x')\R" unfolding set_rel_def by blast lemma set_relE1[consumes 2]: assumes "(s,s')\\R\set_rel" "x\s" obtains x' where "x'\s'" "(x,x')\R" using set_relD1[OF assms] .. lemma set_relE2[consumes 2]: assumes "(s,s')\\R\set_rel" "x'\s'" obtains x where "x\s" "(x,x')\R" using set_relD2[OF assms] .. subsection \Automation\ subsubsection \A solver for relator properties\ lemma relprop_triggers: "\R. single_valued R \ single_valued R" "\R. R=Id \ R=Id" "\R. R=Id \ Id=R" "\R. Range R = UNIV \ Range R = UNIV" "\R. Range R = UNIV \ UNIV = Range R" "\R R'. R\R' \ R\R'" by auto ML \ structure relator_props = Named_Thms ( val name = @{binding relator_props} val description = "Additional relator properties" ) structure solve_relator_props = Named_Thms ( val name = @{binding solve_relator_props} val description = "Relator properties that solve goal" ) \ setup relator_props.setup setup solve_relator_props.setup declaration \ Tagged_Solver.declare_solver @{thms relprop_triggers} @{binding relator_props_solver} "Additional relator properties solver" (fn ctxt => (REPEAT_ALL_NEW (CHANGED o ( match_tac ctxt (solve_relator_props.get ctxt) ORELSE' match_tac ctxt (relator_props.get ctxt) )))) \ declaration \ Tagged_Solver.declare_solver [] @{binding force_relator_props_solver} "Additional relator properties solver (instantiate schematics)" (fn ctxt => (REPEAT_ALL_NEW (CHANGED o ( resolve_tac ctxt (solve_relator_props.get ctxt) ORELSE' match_tac ctxt (relator_props.get ctxt) )))) \ lemma relprop_id_orient[relator_props]: "R=Id \ Id=R" and relprop_eq_refl[solve_relator_props]: "t = t" by auto lemma relprop_UNIV_orient[relator_props]: "R=UNIV \ UNIV=R" by auto subsubsection \ML-Level utilities\ ML \ signature RELATORS = sig val mk_relT: typ * typ -> typ val dest_relT: typ -> typ * typ val mk_relAPP: term -> term -> term val list_relAPP: term list -> term -> term val strip_relAPP: term -> term list * term val mk_fun_rel: term -> term -> term val list_rel: term list -> term -> term val rel_absT: term -> typ val rel_concT: term -> typ val mk_prodrel: term * term -> term val is_prodrel: term -> bool val dest_prodrel: term -> term * term val strip_prodrel_left: term -> term list val list_prodrel_left: term list -> term val declare_natural_relator: (string*string) -> Context.generic -> Context.generic val remove_natural_relator: string -> Context.generic -> Context.generic val natural_relator_of: Proof.context -> string -> string option val mk_natural_relator: Proof.context -> term list -> string -> term option val setup: theory -> theory end structure Relators :RELATORS = struct val mk_relT = HOLogic.mk_prodT #> HOLogic.mk_setT fun dest_relT (Type (@{type_name set},[Type (@{type_name prod},[cT,aT])])) = (cT,aT) | dest_relT ty = raise TYPE ("dest_relT",[ty],[]) fun mk_relAPP x f = let val xT = fastype_of x val fT = fastype_of f val rT = range_type fT in Const (@{const_name relAPP},fT-->xT-->rT)$f$x end val list_relAPP = fold mk_relAPP fun strip_relAPP R = let fun aux @{mpat "\?R\?S"} l = aux S (R::l) | aux R l = (l,R) in aux R [] end val rel_absT = fastype_of #> HOLogic.dest_setT #> HOLogic.dest_prodT #> snd val rel_concT = fastype_of #> HOLogic.dest_setT #> HOLogic.dest_prodT #> fst fun mk_fun_rel r1 r2 = let val (r1T,r2T) = (fastype_of r1,fastype_of r2) val (c1T,a1T) = dest_relT r1T val (c2T,a2T) = dest_relT r2T val (cT,aT) = (c1T --> c2T, a1T --> a2T) val rT = mk_relT (cT,aT) in list_relAPP [r1,r2] (Const (@{const_name fun_rel},r1T-->r2T-->rT)) end val list_rel = fold_rev mk_fun_rel fun mk_prodrel (A,B) = @{mk_term "?A \\<^sub>r ?B"} fun is_prodrel @{mpat "_ \\<^sub>r _"} = true | is_prodrel _ = false fun dest_prodrel @{mpat "?A \\<^sub>r ?B"} = (A,B) | dest_prodrel t = raise TERM("dest_prodrel",[t]) fun strip_prodrel_left @{mpat "?A \\<^sub>r ?B"} = strip_prodrel_left A @ [B] | strip_prodrel_left @{mpat (typs) "unit_rel"} = [] | strip_prodrel_left R = [R] val list_prodrel_left = Refine_Util.list_binop_left @{term unit_rel} mk_prodrel structure natural_relators = Generic_Data ( type T = string Symtab.table val empty = Symtab.empty val merge = Symtab.join (fn _ => fn (_,cn) => cn) ) fun declare_natural_relator tcp = natural_relators.map (Symtab.update tcp) fun remove_natural_relator tname = natural_relators.map (Symtab.delete_safe tname) fun natural_relator_of ctxt = Symtab.lookup (natural_relators.get (Context.Proof ctxt)) (* [R1,\,Rn] T is mapped to \R1,\,Rn\ Trel *) fun mk_natural_relator ctxt args Tname = case natural_relator_of ctxt Tname of NONE => NONE | SOME Cname => SOME let val argsT = map fastype_of args val (cTs, aTs) = map dest_relT argsT |> split_list val aT = Type (Tname,aTs) val cT = Type (Tname,cTs) val rT = mk_relT (cT,aT) in list_relAPP args (Const (Cname,argsT--->rT)) end fun natural_relator_from_term (t as Const (name,T)) = let fun err msg = raise TERM (msg,[t]) val (argTs,bodyT) = strip_type T val (conTs,absTs) = argTs |> map (HOLogic.dest_setT #> HOLogic.dest_prodT) |> split_list val (bconT,babsT) = bodyT |> HOLogic.dest_setT |> HOLogic.dest_prodT val (Tcon,bconTs) = dest_Type bconT val (Tcon',babsTs) = dest_Type babsT val _ = Tcon = Tcon' orelse err "Type constructors do not match" val _ = conTs = bconTs orelse err "Concrete types do not match" val _ = absTs = babsTs orelse err "Abstract types do not match" in (Tcon,name) end | natural_relator_from_term t = raise TERM ("Expected constant",[t]) (* TODO: Localize this! *) local fun decl_natrel_aux t context = let fun warn msg = let val tP = Context.cases Syntax.pretty_term_global Syntax.pretty_term context t val m = Pretty.block [ Pretty.str "Ignoring invalid natural_relator declaration:", Pretty.brk 1, Pretty.str msg, Pretty.brk 1, tP ] |> Pretty.string_of val _ = warning m in context end in declare_natural_relator (natural_relator_from_term t) context handle TERM (msg,_) => warn msg | exn => if Exn.is_interrupt exn then Exn.reraise exn else warn "" end in val natural_relator_attr = Scan.repeat1 Args.term >> (fn ts => Thm.declaration_attribute ( fn _ => fold decl_natrel_aux ts) ) end val setup = I #> Attrib.setup @{binding natural_relator} natural_relator_attr "Declare natural relator" end \ setup Relators.setup subsection \Setup\ subsubsection "Natural Relators" declare [[natural_relator unit_rel int_rel nat_rel bool_rel fun_rel prod_rel option_rel sum_rel list_rel ]] (*declaration {* let open Relators in fn _ => declare_natural_relator (@{type_name unit},@{const_name unit_rel}) #> declare_natural_relator (@{type_name fun},@{const_name fun_rel}) #> declare_natural_relator (@{type_name prod},@{const_name prod_rel}) #> declare_natural_relator (@{type_name option},@{const_name option_rel}) #> declare_natural_relator (@{type_name sum},@{const_name sum_rel}) #> declare_natural_relator (@{type_name list},@{const_name list_rel}) end *}*) ML_val \ Relators.mk_natural_relator @{context} [@{term "Ra::('c\'a) set"},@{term "\Rb\option_rel"}] @{type_name prod} |> the |> Thm.cterm_of @{context} ; Relators.mk_fun_rel @{term "\Id\option_rel"} @{term "\Id\list_rel"} |> Thm.cterm_of @{context} \ subsubsection "Additional Properties" lemmas [relator_props] = single_valued_Id subset_refl refl (* TODO: Move *) lemma eq_UNIV_iff: "S=UNIV \ (\x. x\S)" by auto lemma fun_rel_sv[relator_props]: assumes RAN: "Range Ra = UNIV" assumes SV: "single_valued Rv" shows "single_valued (Ra \ Rv)" proof (intro single_valuedI ext impI allI) fix f g h x' assume R1: "(f,g)\Ra\Rv" and R2: "(f,h)\Ra\Rv" from RAN obtain x where AR: "(x,x')\Ra" by auto from fun_relD[OF R1 AR] have "(f x,g x') \ Rv" . moreover from fun_relD[OF R2 AR] have "(f x,h x') \ Rv" . ultimately show "g x' = h x'" using SV by (auto dest: single_valuedD) qed lemmas [relator_props] = Range_Id lemma fun_rel_id[relator_props]: "\R1=Id; R2=Id\ \ R1 \ R2 = Id" by (auto simp: fun_rel_def) lemma fun_rel_id_simp[simp]: "Id\Id = Id" by tagged_solver lemma fun_rel_comp_dist[relator_props]: "(R1\R2) O (R3\R4) \ ((R1 O R3) \ (R2 O R4))" by (auto simp: fun_rel_def) lemma fun_rel_mono[relator_props]: "\ R1\R2; R3\R4 \ \ R2\R3 \ R1\R4" by (force simp: fun_rel_def) lemma prod_rel_sv[relator_props]: "\single_valued R1; single_valued R2\ \ single_valued (\R1,R2\prod_rel)" by (auto intro: single_valuedI dest: single_valuedD simp: prod_rel_def) lemma prod_rel_id[relator_props]: "\R1=Id; R2=Id\ \ \R1,R2\prod_rel = Id" by (auto simp: prod_rel_def) lemma prod_rel_id_simp[simp]: "\Id,Id\prod_rel = Id" by tagged_solver lemma prod_rel_mono[relator_props]: "\ R2\R1; R3\R4 \ \ \R2,R3\prod_rel \ \R1,R4\prod_rel" by (auto simp: prod_rel_def) lemma prod_rel_range[relator_props]: "\Range Ra=UNIV; Range Rb=UNIV\ \ Range (\Ra,Rb\prod_rel) = UNIV" apply (auto simp: prod_rel_def) by (metis Range_iff UNIV_I)+ lemma option_rel_sv[relator_props]: "\single_valued R\ \ single_valued (\R\option_rel)" by (auto intro: single_valuedI dest: single_valuedD simp: option_rel_def) lemma option_rel_id[relator_props]: "R=Id \ \R\option_rel = Id" by (auto simp: option_rel_def) lemma option_rel_id_simp[simp]: "\Id\option_rel = Id" by tagged_solver lemma option_rel_mono[relator_props]: "R\R' \ \R\option_rel \ \R'\option_rel" by (auto simp: option_rel_def) lemma option_rel_range: "Range R = UNIV \ Range (\R\option_rel) = UNIV" apply (auto simp: option_rel_def Range_iff) by (metis Range_iff UNIV_I option.exhaust) lemma option_rel_inter[simp]: "\R1 \ R2\option_rel = \R1\option_rel \ \R2\option_rel" by (auto simp: option_rel_def) lemma option_rel_constraint[simp]: "(x,x)\\UNIV\C\option_rel \ (\v. x=Some v \ v\C)" by (auto simp: option_rel_def) lemma sum_rel_sv[relator_props]: "\single_valued Rl; single_valued Rr\ \ single_valued (\Rl,Rr\sum_rel)" by (auto intro: single_valuedI dest: single_valuedD simp: sum_rel_def) lemma sum_rel_id[relator_props]: "\Rl=Id; Rr=Id\ \ \Rl,Rr\sum_rel = Id" apply (auto elim: sum_relE) apply (case_tac b) apply simp_all done lemma sum_rel_id_simp[simp]: "\Id,Id\sum_rel = Id" by tagged_solver lemma sum_rel_mono[relator_props]: "\ Rl\Rl'; Rr\Rr' \ \ \Rl,Rr\sum_rel \ \Rl',Rr'\sum_rel" by (auto simp: sum_rel_def) lemma sum_rel_range[relator_props]: "\ Range Rl=UNIV; Range Rr=UNIV \ \ Range (\Rl,Rr\sum_rel) = UNIV" apply (auto simp: sum_rel_def Range_iff) by (metis Range_iff UNIV_I sumE) lemma list_rel_sv_iff: "single_valued (\R\list_rel) \ single_valued R" apply (intro iffI[rotated] single_valuedI allI impI) apply (clarsimp simp: list_rel_def) proof - fix x y z assume SV: "single_valued R" assume "list_all2 (\x x'. (x, x') \ R) x y" and "list_all2 (\x x'. (x, x') \ R) x z" thus "y=z" apply (induct arbitrary: z rule: list_all2_induct) apply simp apply (case_tac z) apply force apply (force intro: single_valuedD[OF SV]) done next fix x y z assume SV: "single_valued (\R\list_rel)" assume "(x,y)\R" "(x,z)\R" hence "([x],[y])\\R\list_rel" and "([x],[z])\\R\list_rel" by (auto simp: list_rel_def) with single_valuedD[OF SV] show "y=z" by blast qed lemma list_rel_sv[relator_props]: "single_valued R \ single_valued (\R\list_rel)" by (simp add: list_rel_sv_iff) lemma list_rel_id[relator_props]: "\R=Id\ \ \R\list_rel = Id" by (auto simp add: list_rel_def list_all2_eq[symmetric]) lemma list_rel_id_simp[simp]: "\Id\list_rel = Id" by tagged_solver lemma list_rel_mono[relator_props]: assumes A: "R\R'" shows "\R\list_rel \ \R'\list_rel" proof clarsimp fix l l' assume "(l,l')\\R\list_rel" thus "(l,l')\\R'\list_rel" apply induct using A by auto qed lemma list_rel_range[relator_props]: assumes A: "Range R = UNIV" shows "Range (\R\list_rel) = UNIV" proof (clarsimp simp: eq_UNIV_iff) fix l show "l\Range (\R\list_rel)" apply (induct l) using A[unfolded eq_UNIV_iff] by (auto simp: Range_iff intro: list_relI) qed lemma bijective_imp_sv: "bijective R \ single_valued R" "bijective R \ single_valued (R\)" by (simp_all add: bijective_alt) (* TODO: Move *) declare bijective_Id[relator_props] declare bijective_Empty[relator_props] text \Pointwise refinement for set types:\ lemma set_rel_sv[relator_props]: "single_valued R \ single_valued (\R\set_rel)" unfolding single_valued_def set_rel_def by blast lemma set_rel_id[relator_props]: "R=Id \ \R\set_rel = Id" by (auto simp add: set_rel_def) lemma set_rel_id_simp[simp]: "\Id\set_rel = Id" by tagged_solver lemma set_rel_csv[relator_props]: "\ single_valued (R\) \ \ single_valued ((\R\set_rel)\)" unfolding single_valued_def set_rel_def converse_iff by fast subsection \Invariant and Abstraction\ text \ Quite often, a relation can be described as combination of an abstraction function and an invariant, such that the invariant describes valid values on the concrete domain, and the abstraction function maps valid concrete values to its corresponding abstract value. \ definition build_rel where "build_rel \ I \ {(c,a) . a=\ c \ I c}" abbreviation "br\build_rel" lemmas br_def[refine_rel_defs] = build_rel_def lemma in_br_conv: "(c,a)\br \ I \ a=\ c \ I c" by (auto simp: br_def) lemma brI[intro?]: "\ a=\ c; I c \ \ (c,a)\br \ I" by (simp add: br_def) lemma br_id[simp]: "br id (\_. True) = Id" unfolding build_rel_def by auto lemma br_chain: "(build_rel \ J) O (build_rel \ I) = build_rel (\\\) (\s. J s \ I (\ s))" unfolding build_rel_def by auto lemma br_sv[simp, intro!,relator_props]: "single_valued (br \ I)" unfolding build_rel_def apply (rule single_valuedI) apply auto done lemma converse_br_sv_iff[simp]: "single_valued (converse (br \ I)) \ inj_on \ (Collect I)" by (auto intro!: inj_onI single_valuedI dest: single_valuedD inj_onD simp: br_def) [] lemmas [relator_props] = single_valued_relcomp lemma br_comp_alt: "br \ I O R = { (c,a) . I c \ (\ c,a)\R }" by (auto simp add: br_def) lemma br_comp_alt': "{(c,a) . a=\ c \ I c} O R = { (c,a) . I c \ (\ c,a)\R }" by auto lemma single_valued_as_brE: assumes "single_valued R" obtains \ invar where "R=br \ invar" apply (rule that[of "\x. THE y. (x,y)\R" "\x. x\Domain R"]) using assms unfolding br_def by (auto dest: single_valuedD intro: the_equality[symmetric] theI) lemma sv_add_invar: "single_valued R \ single_valued {(c, a). (c, a) \ R \ I c}" by (auto dest: single_valuedD intro: single_valuedI) lemma br_Image_conv[simp]: "br \ I `` S = {\ x | x. x\S \ I x}" by (auto simp: br_def) subsection \Miscellanneous\ lemma rel_cong: "(f,g)\Id \ (x,y)\Id \ (f x, g y)\Id" by simp lemma rel_fun_cong: "(f,g)\Id \ (f x, g x)\Id" by simp lemma rel_arg_cong: "(x,y)\Id \ (f x, f y)\Id" by simp subsection \Conversion between Predicate and Set Based Relators\ text \ Autoref uses set-based relators of type @{typ \('a\'b) set\}, while the transfer and lifting package of Isabelle/HOL uses predicate based relators of type @{typ \'a \ 'b \ bool\}. This section defines some utilities to convert between the two. \ definition "rel2p R x y \ (x,y)\R" definition "p2rel P \ {(x,y). P x y}" lemma rel2pD: "\rel2p R a b\ \ (a,b)\R" by (auto simp: rel2p_def) lemma p2relD: "\(a,b) \ p2rel R\ \ R a b" by (auto simp: p2rel_def) lemma rel2p_inv[simp]: "rel2p (p2rel P) = P" "p2rel (rel2p R) = R" by (auto simp: rel2p_def[abs_def] p2rel_def) named_theorems rel2p named_theorems p2rel lemma rel2p_dflt[rel2p]: "rel2p Id = (=)" "rel2p (A\B) = rel_fun (rel2p A) (rel2p B)" "rel2p (A\\<^sub>rB) = rel_prod (rel2p A) (rel2p B)" "rel2p (\A,B\sum_rel) = rel_sum (rel2p A) (rel2p B)" "rel2p (\A\option_rel) = rel_option (rel2p A)" "rel2p (\A\list_rel) = list_all2 (rel2p A)" by (auto simp: rel2p_def[abs_def] intro!: ext simp: fun_rel_def rel_fun_def simp: sum_rel_def elim: rel_sum.cases simp: option_rel_def elim: option.rel_cases simp: list_rel_def simp: set_rel_def rel_set_def Image_def ) lemma p2rel_dflt[p2rel]: "p2rel (=) = Id" "p2rel (rel_fun A B) = p2rel A \ p2rel B" "p2rel (rel_prod A B) = p2rel A \\<^sub>r p2rel B" "p2rel (rel_sum A B) = \p2rel A, p2rel B\sum_rel" "p2rel (rel_option A) = \p2rel A\option_rel" "p2rel (list_all2 A) = \p2rel A\list_rel" by (auto simp: p2rel_def[abs_def] simp: fun_rel_def rel_fun_def simp: sum_rel_def elim: rel_sum.cases simp: option_rel_def elim: option.rel_cases simp: list_rel_def ) lemma [rel2p]: "rel2p (\A\set_rel) = rel_set (rel2p A)" unfolding set_rel_def rel_set_def rel2p_def[abs_def] by blast lemma [p2rel]: "left_unique A \ p2rel (rel_set A) = (\p2rel A\set_rel)" unfolding set_rel_def rel_set_def p2rel_def[abs_def] by blast lemma rel2p_comp: "rel2p A OO rel2p B = rel2p (A O B)" by (auto simp: rel2p_def[abs_def] intro!: ext) lemma rel2p_inj[simp]: "rel2p A = rel2p B \ A=B" by (auto simp: rel2p_def[abs_def]; meson) - + +lemma rel2p_left_unique: "left_unique (rel2p A) = single_valued (A\)" + unfolding left_unique_def rel2p_def single_valued_def by blast + +lemma rel2p_right_unique: "right_unique (rel2p A) = single_valued A" + unfolding right_unique_def rel2p_def single_valued_def by blast + +lemma rel2p_bi_unique: "bi_unique (rel2p A) \ single_valued A \ single_valued (A\)" + unfolding bi_unique_alt_def by (auto simp: rel2p_left_unique rel2p_right_unique) + +lemma p2rel_left_unique: "single_valued ((p2rel A)\) = left_unique A" + unfolding left_unique_def p2rel_def single_valued_def by blast + +lemma p2rel_right_unique: "single_valued (p2rel A) = right_unique A" + unfolding right_unique_def p2rel_def single_valued_def by blast subsection \More Properties\ (* TODO: Do compp-lemmas for other standard relations *) lemma list_rel_compp: "\A O B\list_rel = \A\list_rel O \B\list_rel" using list.rel_compp[of "rel2p A" "rel2p B"] by (auto simp: rel2p(2-)[symmetric] rel2p_comp) (* TODO: Not very systematic proof *) lemma option_rel_compp: "\A O B\option_rel = \A\option_rel O \B\option_rel" using option.rel_compp[of "rel2p A" "rel2p B"] by (auto simp: rel2p(2-)[symmetric] rel2p_comp) (* TODO: Not very systematic proof *) lemma prod_rel_compp: "\A O B, C O D\prod_rel = \A,C\prod_rel O \B,D\prod_rel" using prod.rel_compp[of "rel2p A" "rel2p B" "rel2p C" "rel2p D"] by (auto simp: rel2p(2-)[symmetric] rel2p_comp) (* TODO: Not very systematic proof *) lemma sum_rel_compp: "\A O B, C O D\sum_rel = \A,C\sum_rel O \B,D\sum_rel" using sum.rel_compp[of "rel2p A" "rel2p B" "rel2p C" "rel2p D"] by (auto simp: rel2p(2-)[symmetric] rel2p_comp) (* TODO: Not very systematic proof *) lemma set_rel_compp: "\A O B\set_rel = \A\set_rel O \B\set_rel" using rel_set_OO[of "rel2p A" "rel2p B"] by (auto simp: rel2p(2-)[symmetric] rel2p_comp) (* TODO: Not very systematic proof *) lemma map_in_list_rel_conv: shows "(l, map \ l) \ \br \ I\list_rel \ (\x\set l. I x)" by (induction l) (auto simp: in_br_conv) lemma br_set_rel_alt: "(s',s)\\br \ I\set_rel \ (s=\`s' \ (\x\s'. I x))" by (auto simp: set_rel_def br_def) (* TODO: Find proof that does not depend on br, and move to Misc *) lemma finite_Image_sv: "single_valued R \ finite s \ finite (R``s)" by (erule single_valued_as_brE) simp lemma finite_set_rel_transfer: "\(s,s')\\R\set_rel; single_valued R; finite s\ \ finite s'" unfolding set_rel_alt by (blast intro: finite_subset[OF _ finite_Image_sv]) lemma finite_set_rel_transfer_back: "\(s,s')\\R\set_rel; single_valued (R\); finite s'\ \ finite s" unfolding set_rel_alt by (blast intro: finite_subset[OF _ finite_Image_sv]) end diff --git a/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Indexed_Array_List.thy b/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Indexed_Array_List.thy --- a/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Indexed_Array_List.thy +++ b/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Indexed_Array_List.thy @@ -1,420 +1,428 @@ theory IICF_Indexed_Array_List imports "HOL-Library.Rewrite" "../Intf/IICF_List" "List-Index.List_Index" IICF_Array IICF_MS_Array_List begin text \We implement distinct lists of natural numbers in the range \{0.. by a length counter and two arrays of size \N\. The first array stores the list, and the second array stores the positions of the elements in the list, or \N\ if the element is not in the list. This allows for an efficient index query. The implementation is done in two steps: First, we use a list and a fixed size list for the index mapping. Second, we refine the lists to arrays. \ type_synonym aial = "nat list \ nat list" locale ial_invar = fixes maxsize :: nat and l :: "nat list" and qp :: "nat list" assumes maxsize_eq[simp]: "maxsize = length qp" assumes l_distinct[simp]: "distinct l" assumes l_set: "set l \ {0..kset l then List_Index.index l k else length qp)" begin lemma l_len: "length l \ length qp" proof - from card_mono[OF _ l_set] have "card (set l) \ length qp" by auto with distinct_card[OF l_distinct] show ?thesis by simp qed lemma idx_len[simp]: "i l!i < length qp" using l_set by (metis atLeastLessThan_iff nth_mem psubsetD psubsetI) lemma l_set_simp[simp]: "k\set l \ k < length qp" by (auto dest: subsetD[OF l_set]) lemma qpk_idx: "k qp ! k < length l \ k \ set l" proof (rule iffI) assume A: "kset l" by (auto split: if_split_asm) } { assume "k\set l" thus "qp!k set l \ l ! (qp ! k) = k" using spec[OF qp_def, of k] by auto lemma "\i \ i=j" by (simp add: nth_eq_iff_index_eq) lemmas index_swap[simp] = index_swap_if_distinct[folded swap_def, OF l_distinct] lemma swap_invar: assumes "i br fst (uncurry (ial_invar maxsize))" definition ial_assn2 :: "nat \ nat list * nat list \ _" where "ial_assn2 maxsize \ prod_assn (marl_assn maxsize nat_assn) (array_assn nat_assn)" (* definition "ial_assn maxsize \ hr_comp (ial_assn2 maxsize) (ial_rel1 maxsize)"*) definition "ial_assn maxsize A \ hr_comp (hr_comp (ial_assn2 maxsize) (ial_rel1 maxsize)) (\the_pure A\list_rel)" lemmas [safe_constraint_rules] = CN_FALSEI[of is_pure "ial_assn maxsize A" for maxsize A] (* lemma ial_assn_precise[constraint_rules]: "precise (ial_assn maxsize)" unfolding ial_assn_def ial_rel1_def ial_assn2_def apply constraint_rules *) subsection \Empty\ definition op_ial_empty_sz :: "nat \ 'a list" where [simp]: "op_ial_empty_sz ms \ op_list_empty" lemma [def_pat_rules]: "op_ial_empty_sz$maxsize \ UNPROTECT (op_ial_empty_sz maxsize)" by simp context fixes maxsize :: nat begin sepref_register "PR_CONST (op_ial_empty_sz maxsize)" end context fixes maxsize :: nat (* If we do not fix maxsize here, the FCOMP-rule will derive a more general rule with two different maxsizes! *) notes [fcomp_norm_unfold] = ial_assn_def[symmetric] notes [simp] = hn_ctxt_def pure_def begin definition "aial_empty \ do { let l = op_marl_empty_sz maxsize; let qp = op_array_replicate maxsize maxsize; RETURN (l,qp) }" lemma aial_empty_impl: "(aial_empty,RETURN op_list_empty) \ \ial_rel1 maxsize\nres_rel" unfolding aial_empty_def apply (refine_vcg nres_relI) apply (clarsimp simp: ial_rel1_def br_def) apply unfold_locales apply auto done (* Note: This lemma requires some setup to handle maxsize simultaneously as a parameter, and as a constant. *) context notes [id_rules] = itypeI[Pure.of maxsize "TYPE(nat)"] notes [sepref_import_param] = IdI[of maxsize] begin sepref_definition ial_empty is "uncurry0 aial_empty" :: "unit_assn\<^sup>k \\<^sub>a ial_assn2 maxsize" unfolding aial_empty_def ial_assn2_def using [[id_debug]] by sepref end sepref_decl_impl (no_register) ial_empty: ial_empty.refine[FCOMP aial_empty_impl] . lemma ial_empty_sz_hnr[sepref_fr_rules]: "(uncurry0 local.ial_empty, uncurry0 (RETURN (PR_CONST (op_ial_empty_sz maxsize)))) \ unit_assn\<^sup>k \\<^sub>a ial_assn maxsize A" using ial_empty_hnr[of A] by simp subsection \Swap\ definition "aial_swap \ \(l,qp) i j. do { vi \ mop_list_get l i; vj \ mop_list_get l j; l \ mop_list_set l i vj; l \ mop_list_set l j vi; qp \ mop_list_set qp vj i; qp \ mop_list_set qp vi j; RETURN (l,qp) }" lemma in_ial_rel1_conv: "((pq, qp), l) \ ial_rel1 ms \ pq=l \ ial_invar ms l qp" by (auto simp: ial_rel1_def in_br_conv) lemma aial_swap_impl: "(aial_swap,mop_list_swap) \ ial_rel1 maxsize \ nat_rel \ nat_rel \ \ial_rel1 maxsize\nres_rel" proof (intro fun_relI nres_relI; clarsimp simp: in_ial_rel1_conv; refine_vcg; clarsimp) fix l qp i j assume [simp]: "i SPEC (\c. (c, swap l i j) \ ial_rel1 maxsize)" unfolding aial_swap_def apply refine_vcg apply (vc_solve simp add: in_ial_rel1_conv swap_def[symmetric] swap_invar) done qed sepref_definition ial_swap is "uncurry2 aial_swap" :: "(ial_assn2 maxsize)\<^sup>d *\<^sub>a nat_assn\<^sup>k *\<^sub>a nat_assn\<^sup>k \\<^sub>a ial_assn2 maxsize" unfolding aial_swap_def ial_assn2_def by sepref sepref_decl_impl (ismop) test: ial_swap.refine[FCOMP aial_swap_impl] uses mop_list_swap.fref . subsection \Length\ definition aial_length :: "aial \ nat nres" where "aial_length \ \(l,_). RETURN (op_list_length l)" lemma aial_length_impl: "(aial_length, mop_list_length) \ ial_rel1 maxsize \ \nat_rel\nres_rel" apply (intro fun_relI nres_relI) unfolding ial_rel1_def in_br_conv aial_length_def by auto sepref_definition ial_length is "aial_length" :: "(ial_assn2 maxsize)\<^sup>k \\<^sub>a nat_assn" unfolding aial_length_def ial_assn2_def by sepref sepref_decl_impl (ismop) ial_length: ial_length.refine[FCOMP aial_length_impl] . subsection \Index\ definition aial_index :: "aial \ nat \ nat nres" where "aial_index \ \(l,qp) k. do { ASSERT (k\set l); i \ mop_list_get qp k; RETURN i }" lemma aial_index_impl: "(uncurry aial_index, uncurry mop_list_index) \ [\(l,k). k\set l]\<^sub>f ial_rel1 maxsize \\<^sub>r nat_rel \ \nat_rel\nres_rel" apply (intro fun_relI nres_relI frefI) unfolding ial_rel1_def proof (clarsimp simp: in_br_conv) fix l qp k assume "ial_invar maxsize l qp" then interpret ial_invar maxsize l qp . assume "k\set l" then show "aial_index (l,qp) k \ RETURN (index l k)" unfolding aial_index_def apply (refine_vcg) by (auto simp: qp_def) qed sepref_definition ial_index is "uncurry aial_index" :: "(ial_assn2 maxsize)\<^sup>k *\<^sub>a nat_assn\<^sup>k \\<^sub>a nat_assn" unfolding aial_index_def ial_assn2_def by sepref sepref_decl_impl (ismop) ial_index: ial_index.refine[FCOMP aial_index_impl] . subsection \Butlast\ definition aial_butlast :: "aial \ aial nres" where "aial_butlast \ \(l,qp). do { ASSERT (l\[]); len \ mop_list_length l; k \ mop_list_get l (len - 1); l \ mop_list_butlast l; qp \ mop_list_set qp k (length qp); RETURN (l,qp) }" lemma aial_butlast_refine: "(aial_butlast, mop_list_butlast) \ ial_rel1 maxsize \ \ial_rel1 maxsize\nres_rel" apply (intro fun_relI nres_relI) unfolding ial_rel1_def proof (clarsimp simp: in_br_conv simp del: mop_list_butlast_alt) fix l qp assume "ial_invar maxsize l qp" then interpret ial_invar maxsize l qp . { assume A: "l\[]" have "ial_invar (length qp) (butlast l) (qp[l ! (length l - Suc 0) := length qp])" apply standard apply clarsimp_all apply (auto simp: distinct_butlast) [] using l_set apply (auto dest: in_set_butlastD) [] using qp_def A l_distinct apply (auto simp: nth_list_update neq_Nil_rev_conv index_append simp del: l_distinct) done } note aux1=this show "aial_butlast (l, qp) \ \ (br fst (uncurry (ial_invar maxsize))) (mop_list_butlast l)" unfolding aial_butlast_def mop_list_butlast_alt apply refine_vcg apply (clarsimp_all simp: in_br_conv aux1) done qed sepref_definition ial_butlast is aial_butlast :: "(ial_assn2 maxsize)\<^sup>d \\<^sub>a ial_assn2 maxsize" unfolding aial_butlast_def ial_assn2_def by sepref sepref_decl_impl (ismop) ial_butlast: ial_butlast.refine[FCOMP aial_butlast_refine] . subsection \Append\ definition aial_append :: "aial \ nat \ aial nres" where "aial_append \ \(l,qp) k. do { ASSERT (k k\set l \ length l < length qp); len \ mop_list_length l; l \ mop_list_append l k; qp \ mop_list_set qp k len; RETURN (l,qp) }" lemma aial_append_refine: "(uncurry aial_append,uncurry mop_list_append) \ [\(l,k). k k\set l]\<^sub>f ial_rel1 maxsize \\<^sub>r nat_rel \ \ial_rel1 maxsize\nres_rel" apply (intro frefI nres_relI) unfolding ial_rel1_def proof (clarsimp simp: in_br_conv) fix l qp k assume KLM: "kset l" assume "ial_invar maxsize l qp" then interpret ial_invar maxsize l qp . from KLM have KLL: "k {0.. {Suc k.. card \" by simp also note card_Un_le also have "card {0.. < length qp" using KLL by simp finally have LLEN: "length l < length qp" . have aux1[simp]: "ial_invar (length qp) (l @ [k]) (qp[k := length l])" apply standard apply (clarsimp_all simp: KNL KLL) using KLL apply (auto simp: Suc_le_eq LLEN) [] apply (auto simp: index_append KNL nth_list_update') apply (simp add: qp_def) apply (simp add: qp_def) done show "aial_append (l, qp) k \ \ (br fst (uncurry (ial_invar maxsize))) (RETURN (l@[k]))" unfolding aial_append_def mop_list_append_def apply refine_vcg apply (clarsimp_all simp: in_br_conv KLL KNL LLEN) done qed private lemma aial_append_impl_aux: "((l, qp), l') \ ial_rel1 maxsize \ l'=l \ maxsize = length qp" unfolding ial_rel1_def by (clarsimp simp: in_br_conv ial_invar.maxsize_eq[symmetric]) context notes [dest!] = aial_append_impl_aux begin (* TODO: Should we integrate the domain-condition, or some similar condition, as assertion (relating length l and length qp) or into ial_assn2 ? *) sepref_definition ial_append is "uncurry aial_append" :: "[\(lqp,_). lqp\Domain (ial_rel1 maxsize)]\<^sub>a (ial_assn2 maxsize)\<^sup>d *\<^sub>a nat_assn\<^sup>k \ ial_assn2 maxsize" unfolding aial_append_def ial_assn2_def by sepref end lemma "(\b. b A \ bool_rel" apply auto oops context begin (* TODO: Maybe inject additional restrictions on sepref_decl_impl command *) (* TODO: Maybe require Domain R \ {0..IS_BELOW_ID R\ \ (uncurry mop_list_append, uncurry mop_list_append) \ \R\list_rel \\<^sub>r R \\<^sub>f \\R\list_rel\nres_rel" by (rule mop_list_append.fref) sepref_decl_impl (ismop) ial_append: ial_append.refine[FCOMP aial_append_refine] uses append_fref' unfolding IS_BELOW_ID_def apply (parametricity; auto simp: single_valued_below_Id) done end (* lemmas ial_append_hnr_mop[sepref_fr_rules] = ial_append.refine[FCOMP aial_append_refine] lemmas ial_append_hnr[sepref_fr_rules] = ial_append_hnr_mop[FCOMP mk_op_rl2_np[OF mop_list_append_alt]] *) subsection \Get\ definition aial_get :: "aial \ nat \ nat nres" where "aial_get \ \(l,qp) i. mop_list_get l i" lemma aial_get_refine: "(aial_get,mop_list_get) \ ial_rel1 maxsize \ nat_rel \ \nat_rel\nres_rel" apply (intro fun_relI nres_relI) unfolding aial_get_def ial_rel1_def mop_list_get_def in_br_conv apply refine_vcg apply clarsimp_all done sepref_definition ial_get is "uncurry aial_get" :: "(ial_assn2 maxsize)\<^sup>k *\<^sub>a nat_assn\<^sup>k \\<^sub>a nat_assn" unfolding aial_get_def ial_assn2_def by sepref sepref_decl_impl (ismop) ial_get: ial_get.refine[FCOMP aial_get_refine] . subsection \Contains\ definition aial_contains :: "nat \ aial \ bool nres" where "aial_contains \ \k (l,qp). do { if k mop_list_get qp k; RETURN (i (nat_rel \\<^sub>r ial_rel1 maxsize) \\<^sub>f \bool_rel\nres_rel" apply (intro frefI nres_relI) unfolding ial_rel1_def proof (clarsimp simp: in_br_conv) fix l qp k (*assume A: "k RETURN (k\set l)" unfolding aial_contains_def apply refine_vcg by (auto simp: l_len qp_def split: if_split_asm) qed context notes [id_rules] = itypeI[Pure.of maxsize "TYPE(nat)"] notes [sepref_import_param] = IdI[of maxsize] begin sepref_definition ial_contains is "uncurry aial_contains" :: "nat_assn\<^sup>k *\<^sub>a (ial_assn2 maxsize)\<^sup>k \\<^sub>a bool_assn" unfolding aial_contains_def ial_assn2_def by sepref end sepref_decl_impl (ismop) ial_contains: ial_contains.refine[FCOMP aial_contains_refine] . end + + + interpretation ial_sz: list_custom_empty "ial_assn N A" "ial_empty N" "PR_CONST (op_ial_empty_sz N)" + apply unfold_locales + apply (rule ial_empty_sz_hnr [unfolded op_ial_empty_sz_def PR_CONST_def]) + by simp + + end diff --git a/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Sepl_Binding.thy b/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Sepl_Binding.thy --- a/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Sepl_Binding.thy +++ b/thys/Refine_Imperative_HOL/IICF/Impl/IICF_Sepl_Binding.thy @@ -1,813 +1,855 @@ section \Sepref Bindings for Imp/HOL Collections\ theory IICF_Sepl_Binding imports Separation_Logic_Imperative_HOL.Imp_Map_Spec Separation_Logic_Imperative_HOL.Imp_Set_Spec Separation_Logic_Imperative_HOL.Imp_List_Spec Separation_Logic_Imperative_HOL.Hash_Map_Impl Separation_Logic_Imperative_HOL.Array_Map_Impl Separation_Logic_Imperative_HOL.To_List_GA Separation_Logic_Imperative_HOL.Hash_Set_Impl Separation_Logic_Imperative_HOL.Array_Set_Impl Separation_Logic_Imperative_HOL.Open_List Separation_Logic_Imperative_HOL.Circ_List "../Intf/IICF_Map" "../Intf/IICF_Set" "../Intf/IICF_List" Collections.Locale_Code begin text \This theory binds collection data structures from the basic collection framework established in \AFP/Separation_Logic_Imperative_HOL\ for usage with Sepref. \ (* TODO: Move, addition to Imp_Map_Spec *) locale imp_map_contains_key = imp_map + constrains is_map :: "('k \ 'v) \ 'm \ assn" fixes contains_key :: "'k \ 'm \ bool Heap" assumes contains_key_rule[sep_heap_rules]: " contains_key k p <\r. is_map m p * \(r\k\dom m)>\<^sub>t" (* TODO: Move to Imp_Map_Spec *) locale gen_contains_key_by_lookup = imp_map_lookup begin definition "contains_key k m \ do {r \ lookup k m; return (\is_None r)}" sublocale imp_map_contains_key is_map contains_key apply unfold_locales unfolding contains_key_def apply (sep_auto split: option.splits) done end (* TODO: Move to Imp_List_Spec *) locale imp_list_tail = imp_list + constrains is_list :: "'a list \ 'l \ assn" fixes tail :: "'l \ 'l Heap" assumes tail_rule[sep_heap_rules]: "l\[] \ tail p \<^sub>t" (* TODO: Move to Open_List *) definition os_head :: "'a::heap os_list \ ('a) Heap" where "os_head p \ case p of None \ raise STR ''os_Head: Empty list'' | Some p \ do { m \!p; return (val m) }" primrec os_tl :: "'a::heap os_list \ ('a os_list) Heap" where "os_tl None = raise STR ''os_tl: Empty list''" | "os_tl (Some p) = do { m \!p; return (next m) }" interpretation os: imp_list_head os_list os_head by unfold_locales (sep_auto simp: os_head_def neq_Nil_conv) interpretation os: imp_list_tail os_list os_tl by unfold_locales (sep_auto simp: os_tl_def neq_Nil_conv) (* TODO: Move to Circ_List *) definition cs_is_empty :: "'a::heap cs_list \ bool Heap" where "cs_is_empty p \ return (is_None p)" interpretation cs: imp_list_is_empty cs_list cs_is_empty by unfold_locales (sep_auto simp: cs_is_empty_def split: option.splits) definition cs_head :: "'a::heap cs_list \ 'a Heap" where "cs_head p \ case p of None \ raise STR ''cs_head: Empty list'' | Some p \ do { n \ !p; return (val n)}" interpretation cs: imp_list_head cs_list cs_head by unfold_locales (sep_auto simp: neq_Nil_conv cs_head_def) definition cs_tail :: "'a::heap cs_list \ 'a cs_list Heap" where "cs_tail p \ do { (_,r) \ cs_pop p; return r }" interpretation cs: imp_list_tail cs_list cs_tail by unfold_locales (sep_auto simp: cs_tail_def) (* TODO: Move to hashmap/hashset *) lemma is_hashmap_finite[simp]: "h \ is_hashmap m mi \ finite (dom m)" unfolding is_hashmap_def is_hashmap'_def by auto lemma is_hashset_finite[simp]: "h \ is_hashset s si \ finite s" unfolding is_hashset_def by (auto dest: is_hashmap_finite) (* TODO: Move to array-map/ array-set *) definition "ias_is_it s a si \ \(a',i). \\<^sub>Al. a\\<^sub>al * \(a'=a \ s=ias_of_list l \ (i=length l \ si={} \ i i\s \ si=s \ {x. x\i} )) " context begin private function first_memb where "first_memb lmax a i = do { if i Array.nth a i; if x then return i else first_memb lmax a (Suc i) } else return i }" by pat_completeness auto termination by (relation "measure (\(l,_,i). l-i)") auto declare first_memb.simps[simp del] private lemma first_memb_rl_aux: assumes "lmax \ length l" "i\lmax" shows "< a \\<^sub>a l > first_memb lmax a i <\k. a\\<^sub>a l * \(k\lmax \ (\j. i\j \ j \l!j) \ i\k \ (k=lmax \ l!k)) >" using assms proof (induction lmax a i rule: first_memb.induct) case (1 lmax a i) show ?case apply (subst first_memb.simps) using "1.prems" apply (sep_auto heap: "1.IH"; ((sep_auto;fail) | metis eq_iff not_less_eq_eq)) done qed private lemma first_memb_rl[sep_heap_rules]: assumes "lmax \ length l" "i\lmax" shows "< a \\<^sub>a l > first_memb lmax a i <\k. a\\<^sub>a l * \(ias_of_list l \ {i.. i\k \ (k k\ias_of_list l \ k=lmax) ) >" using assms by (sep_auto simp: ias_of_list_def heap: first_memb_rl_aux) definition "ias_it_init a = do { l \ Array.len a; i \ first_memb l a 0; return (a,i) }" definition "ias_it_has_next \ \(a,i). do { l \ Array.len a; return (i \(a,i). do { l \ Array.len a; i' \ first_memb l a (Suc i); return (i,(a,i')) }" (* TODO: Move *) lemma ias_of_list_bound: "ias_of_list l \ {0.. is_ias S x \ finite S" unfolding is_ias_def by auto (* TODO: Move, replace original rules by this stronger var! *) lemma to_list_ga_rec_rule: assumes "imp_set_iterate is_set is_it it_init it_has_next it_next" assumes "imp_list_prepend is_list l_prepend" assumes FIN: "finite it" assumes DIS: "distinct l" "set l \ it = {}" shows " < is_it s si it iti * is_list l li > to_list_ga_rec it_has_next it_next l_prepend iti li < \r. \\<^sub>Al'. is_set s si * is_list l' r * \(distinct l' \ set l' = set l \ it) >\<^sub>t" proof - interpret imp_set_iterate is_set is_it it_init it_has_next it_next + imp_list_prepend is_list l_prepend by fact+ from FIN DIS show ?thesis proof (induction arbitrary: l li iti rule: finite_psubset_induct) case (psubset it) show ?case apply (subst to_list_ga_rec.simps) using psubset.prems apply (sep_auto heap: psubset.IH) apply (rule ent_frame_fwd[OF quit_iteration]) apply frame_inference apply solve_entails done qed qed lemma to_list_ga_rule: assumes IT: "imp_set_iterate is_set is_it it_init it_has_next it_next" assumes EM: "imp_list_empty is_list l_empty" assumes PREP: "imp_list_prepend is_list l_prepend" assumes FIN: "finite s" shows " to_list_ga it_init it_has_next it_next l_empty l_prepend si <\r. \\<^sub>Al. is_set s si * is_list l r * true * \(distinct l \ set l = s)>" proof - interpret imp_list_empty is_list l_empty + imp_set_iterate is_set is_it it_init it_has_next it_next by fact+ note [sep_heap_rules] = to_list_ga_rec_rule[OF IT PREP] show ?thesis unfolding to_list_ga_def by (sep_auto simp: FIN) qed subsection \Binding Locales\ method solve_sepl_binding = ( unfold_locales; (unfold option_assn_pure_conv)?; sep_auto intro!: hfrefI hn_refineI[THEN hn_refine_preI] simp: invalid_assn_def hn_ctxt_def pure_def ) subsubsection \Map\ locale bind_map = imp_map is_map for is_map :: "('ki \ 'vi) \ 'm \ assn" begin definition "assn K V \ hr_comp is_map (\the_pure K,the_pure V\map_rel)" lemmas [fcomp_norm_unfold] = assn_def[symmetric] lemmas [safe_constraint_rules] = CN_FALSEI[of is_pure "assn K V" for K V] end locale bind_map_empty = imp_map_empty + bind_map begin lemma empty_hnr_aux: "(uncurry0 empty,uncurry0 (RETURN op_map_empty)) \ unit_assn\<^sup>k \\<^sub>a is_map" by solve_sepl_binding sepref_decl_impl (no_register) empty: empty_hnr_aux . end locale bind_map_is_empty = imp_map_is_empty + bind_map begin lemma is_empty_hnr_aux: "(is_empty,RETURN o op_map_is_empty) \ is_map\<^sup>k \\<^sub>a bool_assn" by solve_sepl_binding sepref_decl_impl is_empty: is_empty_hnr_aux . end locale bind_map_update = imp_map_update + bind_map begin lemma update_hnr_aux: "(uncurry2 update,uncurry2 (RETURN ooo op_map_update)) \ id_assn\<^sup>k *\<^sub>a id_assn\<^sup>k *\<^sub>a is_map\<^sup>d \\<^sub>a is_map" by solve_sepl_binding sepref_decl_impl update: update_hnr_aux . end locale bind_map_delete = imp_map_delete + bind_map begin lemma delete_hnr_aux: "(uncurry delete,uncurry (RETURN oo op_map_delete)) \ id_assn\<^sup>k *\<^sub>a is_map\<^sup>d \\<^sub>a is_map" by solve_sepl_binding sepref_decl_impl delete: delete_hnr_aux . end locale bind_map_lookup = imp_map_lookup + bind_map begin lemma lookup_hnr_aux: "(uncurry lookup,uncurry (RETURN oo op_map_lookup)) \ id_assn\<^sup>k *\<^sub>a is_map\<^sup>k \\<^sub>a id_assn" by solve_sepl_binding sepref_decl_impl lookup: lookup_hnr_aux . end locale bind_map_contains_key = imp_map_contains_key + bind_map begin lemma contains_key_hnr_aux: "(uncurry contains_key,uncurry (RETURN oo op_map_contains_key)) \ id_assn\<^sup>k *\<^sub>a is_map\<^sup>k \\<^sub>a bool_assn" by solve_sepl_binding sepref_decl_impl contains_key: contains_key_hnr_aux . end subsubsection \Set\ locale bind_set = imp_set is_set for is_set :: "('ai set) \ 'm \ assn" + fixes A :: "'a \ 'ai \ assn" begin definition "assn \ hr_comp is_set (\the_pure A\set_rel)" lemmas [safe_constraint_rules] = CN_FALSEI[of is_pure "assn"] end locale bind_set_setup = bind_set begin (* TODO: Use sepref_decl_impl (see map) *) lemmas [fcomp_norm_unfold] = assn_def[symmetric] lemma APA: "\PROP Q; CONSTRAINT is_pure A\ \ PROP Q" . lemma APAlu: "\PROP Q; CONSTRAINT (IS_PURE IS_LEFT_UNIQUE) A\ \ PROP Q" . lemma APAru: "\PROP Q; CONSTRAINT (IS_PURE IS_RIGHT_UNIQUE) A\ \ PROP Q" . lemma APAbu: "\PROP Q; CONSTRAINT (IS_PURE IS_LEFT_UNIQUE) A; CONSTRAINT (IS_PURE IS_RIGHT_UNIQUE) A\ \ PROP Q" . end locale bind_set_empty = imp_set_empty + bind_set begin lemma hnr_empty_aux: "(uncurry0 empty,uncurry0 (RETURN op_set_empty))\unit_assn\<^sup>k \\<^sub>a is_set" by solve_sepl_binding interpretation bind_set_setup by standard lemmas hnr_op_empty = hnr_empty_aux[FCOMP op_set_empty.fref[where A="the_pure A"]] lemmas hnr_mop_empty = hnr_op_empty[FCOMP mk_mop_rl0_np[OF mop_set_empty_alt]] end locale bind_set_is_empty = imp_set_is_empty + bind_set begin lemma hnr_is_empty_aux: "(is_empty, RETURN o op_set_is_empty)\is_set\<^sup>k \\<^sub>a bool_assn" by solve_sepl_binding interpretation bind_set_setup by standard lemmas hnr_op_is_empty[sepref_fr_rules] = hnr_is_empty_aux[THEN APA,FCOMP op_set_is_empty.fref[where A="the_pure A"]] lemmas hnr_mop_is_empty[sepref_fr_rules] = hnr_op_is_empty[FCOMP mk_mop_rl1_np[OF mop_set_is_empty_alt]] end locale bind_set_member = imp_set_memb + bind_set begin lemma hnr_member_aux: "(uncurry memb, uncurry (RETURN oo op_set_member))\id_assn\<^sup>k *\<^sub>a is_set\<^sup>k \\<^sub>a bool_assn" by solve_sepl_binding interpretation bind_set_setup by standard lemmas hnr_op_member[sepref_fr_rules] = hnr_member_aux[THEN APAbu,FCOMP op_set_member.fref[where A="the_pure A"]] lemmas hnr_mop_member[sepref_fr_rules] = hnr_op_member[FCOMP mk_mop_rl2_np[OF mop_set_member_alt]] end locale bind_set_insert = imp_set_ins + bind_set begin lemma hnr_insert_aux: "(uncurry ins, uncurry (RETURN oo op_set_insert))\id_assn\<^sup>k *\<^sub>a is_set\<^sup>d \\<^sub>a is_set" by solve_sepl_binding interpretation bind_set_setup by standard lemmas hnr_op_insert[sepref_fr_rules] = hnr_insert_aux[THEN APAru,FCOMP op_set_insert.fref[where A="the_pure A"]] lemmas hnr_mop_insert[sepref_fr_rules] = hnr_op_insert[FCOMP mk_mop_rl2_np[OF mop_set_insert_alt]] end locale bind_set_delete = imp_set_delete + bind_set begin lemma hnr_delete_aux: "(uncurry delete, uncurry (RETURN oo op_set_delete))\id_assn\<^sup>k *\<^sub>a is_set\<^sup>d \\<^sub>a is_set" by solve_sepl_binding interpretation bind_set_setup by standard lemmas hnr_op_delete[sepref_fr_rules] = hnr_delete_aux[THEN APAbu,FCOMP op_set_delete.fref[where A="the_pure A"]] lemmas hnr_mop_delete[sepref_fr_rules] = hnr_op_delete[FCOMP mk_mop_rl2_np[OF mop_set_delete_alt]] end + locale bind_set_size = imp_set_size + bind_set + begin + lemma hnr_size_aux: "(size, (RETURN o op_set_size))\ is_set\<^sup>k \\<^sub>a nat_assn" + by solve_sepl_binding + + interpretation bind_set_setup by standard + lemmas hnr_op_size[sepref_fr_rules] = hnr_size_aux[THEN APAbu,FCOMP op_set_size.fref[where A="the_pure A"]] + lemmas hnr_mop_size[sepref_fr_rules] = hnr_op_size[FCOMP mk_mop_rl1_np[OF mop_set_size_alt]] + end + primrec sorted_wrt' where "sorted_wrt' R [] \ True" | "sorted_wrt' R (x#xs) \ list_all (R x) xs \ sorted_wrt' R xs" lemma sorted_wrt'_eq: "sorted_wrt' = sorted_wrt" proof (intro ext iffI) fix R :: "'a \ 'a \ bool" and xs :: "'a list" { assume "sorted_wrt R xs" thus "sorted_wrt' R xs" by (induction xs)(auto simp: list_all_iff) } { assume "sorted_wrt' R xs" thus "sorted_wrt R xs" by (induction xs) (auto simp: list_all_iff) } qed lemma param_sorted_wrt[param]: "(sorted_wrt, sorted_wrt) \ (A \ A \ bool_rel) \ \A\list_rel \ bool_rel" unfolding sorted_wrt'_eq[symmetric] sorted_wrt'_def by parametricity lemma obtain_list_from_setrel: assumes SV: "single_valued A" assumes "(set l,s) \ \A\set_rel" obtains m where "s=set m" "(l,m)\\A\list_rel" using assms(2) proof (induction l arbitrary: s thesis) case Nil show ?case apply (rule Nil(1)[where m="[]"]) using Nil(2) by auto next case (Cons x l) obtain s' y where "s=insert y s'" "(x,y)\A" "(set l,s')\\A\set_rel" proof - from Cons.prems(2) obtain y where X0: "y\s" "(x,y)\A" unfolding set_rel_def by auto from Cons.prems(2) have X1: "\a\set l. \b\s. (a,b)\A" and X2: "\b\s. \a\insert x (set l). (a,b)\A" unfolding set_rel_def by auto show ?thesis proof (cases "\a\set l. (a,y)\A") case True show ?thesis apply (rule that[of y s]) subgoal using X0 by auto subgoal by fact subgoal apply (rule set_relI) subgoal using X1 by blast subgoal by (metis IS_RIGHT_UNIQUED SV True X0(2) X2 insert_iff) done done next case False show ?thesis apply (rule that[of y "s-{y}"]) subgoal using X0 by auto subgoal by fact subgoal apply (rule set_relI) subgoal using False X1 by fastforce subgoal using IS_RIGHT_UNIQUED SV X0(2) X2 by fastforce done done qed qed moreover from Cons.IH[OF _ \(set l,s')\\A\set_rel\] obtain m where "s'=set m" "(l,m)\\A\list_rel" . ultimately show thesis apply - apply (rule Cons.prems(1)[of "y#m"]) by auto qed lemma param_it_to_sorted_list[param]: "\IS_LEFT_UNIQUE A; IS_RIGHT_UNIQUE A\ \ (it_to_sorted_list, it_to_sorted_list) \ (A \ A \ bool_rel) \ \A\set_rel \ \\A\list_rel\nres_rel" unfolding it_to_sorted_list_def[abs_def] apply (auto simp: it_to_sorted_list_def pw_nres_rel_iff refine_pw_simps) apply (rule obtain_list_from_setrel; assumption?; clarsimp) apply (intro exI conjI; assumption?) using param_distinct[param_fo] apply blast apply simp using param_sorted_wrt[param_fo] apply blast done locale bind_set_iterate = imp_set_iterate + bind_set + assumes is_set_finite: "h \ is_set S x \ finite S" begin context begin private lemma is_imp_set_iterate: "imp_set_iterate is_set is_it it_init it_has_next it_next" by unfold_locales private lemma is_imp_list_empty: "imp_list_empty (list_assn id_assn) (return [])" apply unfold_locales apply solve_constraint apply sep_auto done private lemma is_imp_list_prepend: "imp_list_prepend (list_assn id_assn) (return oo List.Cons)" apply unfold_locales apply solve_constraint apply (sep_auto simp: pure_def) done definition "to_list \ to_list_ga it_init it_has_next it_next (return []) (return oo List.Cons)" private lemmas tl_rl = to_list_ga_rule[OF is_imp_set_iterate is_imp_list_empty is_imp_list_prepend, folded to_list_def] private lemma to_list_sorted1: "(to_list,PR_CONST (it_to_sorted_list (\_ _. True))) \ is_set\<^sup>k \\<^sub>a list_assn id_assn" unfolding PR_CONST_def apply (intro hfrefI) apply (rule hn_refine_preI) apply (rule hn_refineI) unfolding it_to_sorted_list_def apply (sep_auto intro: hfrefI hn_refineI intro: is_set_finite heap: tl_rl) done private lemma to_list_sorted2: "\ CONSTRAINT (IS_PURE IS_LEFT_UNIQUE) A; CONSTRAINT (IS_PURE IS_RIGHT_UNIQUE) A\ \ (PR_CONST (it_to_sorted_list (\_ _. True)), PR_CONST (it_to_sorted_list (\_ _. True))) \ \the_pure A\set_rel \ \\the_pure A\list_rel\nres_rel" unfolding PR_CONST_def CONSTRAINT_def IS_PURE_def by clarify parametricity lemmas to_list_hnr = to_list_sorted1[FCOMP to_list_sorted2, folded assn_def] lemmas to_list_is_to_sorted_list = IS_TO_SORTED_LISTI[OF to_list_hnr] lemma to_list_gen[sepref_gen_algo_rules]: "\CONSTRAINT (IS_PURE IS_LEFT_UNIQUE) A; CONSTRAINT (IS_PURE IS_RIGHT_UNIQUE) A\ \ GEN_ALGO to_list (IS_TO_SORTED_LIST (\_ _. True) (bind_set.assn is_set A) A)" by (simp add: GEN_ALGO_def to_list_is_to_sorted_list) end end + locale bind_set_union = imp_set_union + bind_set + + assumes is_prime_set_finite: "h \ is_set S x \ finite S" + begin + lemma hnr_union_aux: "(uncurry union, uncurry (RETURN oo op_set_union)) + \ is_set\<^sup>d *\<^sub>a is_set\<^sup>k \\<^sub>a is_set" + apply (sep_auto intro!: is_prime_set_finite ) + unfolding invalid_assn_def pure_def pure_assn_def hfref_def + apply (solve_sepl_binding) unfolding entails_def + using is_prime_set_finite subgoal + using mod_starD by blast + apply sep_auto + using is_prime_set_finite mod_starD + unfolding hoare_triple_def ex_assn_def apply sep_auto + using mod_starD union_rule + by (metis assn_times_comm mult_1 pure_assn_def pure_true) + + interpretation bind_set_setup by standard + lemmas hnr_op_union[sepref_fr_rules] = hnr_union_aux[FCOMP op_set_union.fref[where A="the_pure A"]] + lemmas hnr_mop_union[sepref_fr_rules] = hnr_op_union[FCOMP mk_mop_rl2_np[OF mop_set_union_alt]] + + end + + + subsubsection \List\ locale bind_list = imp_list is_list for is_list :: "('ai list) \ 'm \ assn" + fixes A :: "'a \ 'ai \ assn" begin (*abbreviation "Ap \ the_pure A"*) definition "assn \ hr_comp is_list (\the_pure A\list_rel)" lemmas [safe_constraint_rules] = CN_FALSEI[of is_pure "assn"] end locale bind_list_empty = imp_list_empty + bind_list begin lemma hnr_aux: "(uncurry0 empty,uncurry0 (RETURN op_list_empty))\(pure unit_rel)\<^sup>k \\<^sub>a is_list" apply rule apply rule apply (sep_auto simp: pure_def) done lemmas hnr = hnr_aux[FCOMP op_list_empty.fref[of "the_pure A"], folded assn_def] lemmas hnr_mop = hnr[FCOMP mk_mop_rl0_np[OF mop_list_empty_alt]] end locale bind_list_is_empty = imp_list_is_empty + bind_list begin lemma hnr_aux: "(is_empty,RETURN o op_list_is_empty)\(is_list)\<^sup>k \\<^sub>a pure bool_rel" apply rule apply rule apply (sep_auto simp: pure_def) done lemmas hnr[sepref_fr_rules] = hnr_aux[FCOMP op_list_is_empty.fref, of "the_pure A", folded assn_def] lemmas hnr_mop[sepref_fr_rules] = hnr[FCOMP mk_mop_rl1_np[OF mop_list_is_empty_alt]] end locale bind_list_append = imp_list_append + bind_list begin lemma hnr_aux: "(uncurry (swap_args2 append),uncurry (RETURN oo op_list_append)) \(is_list)\<^sup>d *\<^sub>a (pure Id)\<^sup>k \\<^sub>a is_list" by solve_sepl_binding lemmas hnr[sepref_fr_rules] = hnr_aux[FCOMP op_list_append.fref,of A, folded assn_def] lemmas hnr_mop[sepref_fr_rules] = hnr[FCOMP mk_mop_rl2_np[OF mop_list_append_alt]] end locale bind_list_prepend = imp_list_prepend + bind_list begin lemma hnr_aux: "(uncurry prepend,uncurry (RETURN oo op_list_prepend)) \(pure Id)\<^sup>k *\<^sub>a (is_list)\<^sup>d \\<^sub>a is_list" by solve_sepl_binding lemmas hnr[sepref_fr_rules] = hnr_aux[FCOMP op_list_prepend.fref,of A, folded assn_def] lemmas hnr_mop[sepref_fr_rules] = hnr[FCOMP mk_mop_rl2_np[OF mop_list_prepend_alt]] end locale bind_list_hd = imp_list_head + bind_list begin lemma hnr_aux: "(head,RETURN o op_list_hd) \[\l. l\[]]\<^sub>a (is_list)\<^sup>d \ pure Id" by solve_sepl_binding lemmas hnr[sepref_fr_rules] = hnr_aux[FCOMP op_list_hd.fref,of A, folded assn_def] lemmas hnr_mop[sepref_fr_rules] = hnr[FCOMP mk_mop_rl1[OF mop_list_hd_alt]] end locale bind_list_tl = imp_list_tail + bind_list begin lemma hnr_aux: "(tail,RETURN o op_list_tl) \[\l. l\[]]\<^sub>a (is_list)\<^sup>d \ is_list" by solve_sepl_binding lemmas hnr[sepref_fr_rules] = hnr_aux[FCOMP op_list_tl.fref,of "the_pure A", folded assn_def] lemmas hnr_mop[sepref_fr_rules] = hnr[FCOMP mk_mop_rl1[OF mop_list_tl_alt]] end locale bind_list_rotate1 = imp_list_rotate + bind_list begin lemma hnr_aux: "(rotate,RETURN o op_list_rotate1) \(is_list)\<^sup>d \\<^sub>a is_list" by solve_sepl_binding lemmas hnr[sepref_fr_rules] = hnr_aux[FCOMP op_list_rotate1.fref,of "the_pure A", folded assn_def] lemmas hnr_mop[sepref_fr_rules] = hnr[FCOMP mk_mop_rl1_np[OF mop_list_rotate1_alt]] end locale bind_list_rev = imp_list_reverse + bind_list begin lemma hnr_aux: "(reverse,RETURN o op_list_rev) \(is_list)\<^sup>d \\<^sub>a is_list" by solve_sepl_binding lemmas hnr[sepref_fr_rules] = hnr_aux[FCOMP op_list_rev.fref,of "the_pure A", folded assn_def] lemmas hnr_mop[sepref_fr_rules] = hnr[FCOMP mk_mop_rl1_np[OF mop_list_rev_alt]] end subsection \Array Map (iam)\ definition "op_iam_empty \ IICF_Map.op_map_empty" interpretation iam: bind_map_empty is_iam iam_new by unfold_locales interpretation iam: map_custom_empty op_iam_empty by unfold_locales (simp add: op_iam_empty_def) lemmas [sepref_fr_rules] = iam.empty_hnr[folded op_iam_empty_def] definition [simp]: "op_iam_empty_sz (N::nat) \ IICF_Map.op_map_empty" lemma [def_pat_rules]: "op_iam_empty_sz$N \ UNPROTECT (op_iam_empty_sz N)" by simp interpretation iam_sz: map_custom_empty "PR_CONST (op_iam_empty_sz N)" apply unfold_locales apply (simp) done lemma [sepref_fr_rules]: "(uncurry0 iam_new, uncurry0 (RETURN (PR_CONST (op_iam_empty_sz N)))) \ unit_assn\<^sup>k \\<^sub>a iam.assn K V" using iam.empty_hnr[of K V] by simp interpretation iam: bind_map_update is_iam Array_Map_Impl.iam_update by unfold_locales interpretation iam: bind_map_delete is_iam Array_Map_Impl.iam_delete by unfold_locales interpretation iam: bind_map_lookup is_iam Array_Map_Impl.iam_lookup by unfold_locales setup Locale_Code.open_block interpretation iam: gen_contains_key_by_lookup is_iam Array_Map_Impl.iam_lookup by unfold_locales setup Locale_Code.close_block interpretation iam: bind_map_contains_key is_iam iam.contains_key by unfold_locales subsection \Array Set (ias)\ definition [simp]: "op_ias_empty \ op_set_empty" interpretation ias: bind_set_empty is_ias ias_new for A by unfold_locales interpretation ias: set_custom_empty ias_new op_ias_empty by unfold_locales simp lemmas [sepref_fr_rules] = ias.hnr_op_empty[folded op_ias_empty_def] definition [simp]: "op_ias_empty_sz (N::nat) \ op_set_empty" lemma [def_pat_rules]: "op_ias_empty_sz$N \ UNPROTECT (op_ias_empty_sz N)" by simp interpretation ias_sz: bind_set_empty is_ias "ias_new_sz N" for N A by unfold_locales interpretation ias_sz: set_custom_empty "ias_new_sz N" "PR_CONST (op_ias_empty_sz N)" for A by unfold_locales simp lemma [sepref_fr_rules]: "(uncurry0 (ias_new_sz N), uncurry0 (RETURN (PR_CONST (op_ias_empty_sz N)))) \ unit_assn\<^sup>k \\<^sub>a ias.assn A" using ias_sz.hnr_op_empty[of N A] by simp interpretation ias: bind_set_member is_ias Array_Set_Impl.ias_memb for A by unfold_locales interpretation ias: bind_set_insert is_ias Array_Set_Impl.ias_ins for A by unfold_locales interpretation ias: bind_set_delete is_ias Array_Set_Impl.ias_delete for A by unfold_locales setup Locale_Code.open_block interpretation ias: bind_set_iterate is_ias ias_is_it ias_it_init ias_it_has_next ias_it_next for A by unfold_locales auto setup Locale_Code.close_block subsection \Hash Map (hm)\ interpretation hm: bind_map_empty is_hashmap hm_new by unfold_locales definition "op_hm_empty \ IICF_Map.op_map_empty" interpretation hm: map_custom_empty op_hm_empty by unfold_locales (simp add: op_hm_empty_def) lemmas [sepref_fr_rules] = hm.empty_hnr[folded op_hm_empty_def] interpretation hm: bind_map_is_empty is_hashmap Hash_Map.hm_isEmpty by unfold_locales interpretation hm: bind_map_update is_hashmap Hash_Map.hm_update by unfold_locales interpretation hm: bind_map_delete is_hashmap Hash_Map.hm_delete by unfold_locales interpretation hm: bind_map_lookup is_hashmap Hash_Map.hm_lookup by unfold_locales setup Locale_Code.open_block interpretation hm: gen_contains_key_by_lookup is_hashmap Hash_Map.hm_lookup by unfold_locales setup Locale_Code.close_block interpretation hm: bind_map_contains_key is_hashmap hm.contains_key by unfold_locales subsection \Hash Set (hs)\ interpretation hs: bind_set_empty is_hashset hs_new for A by unfold_locales definition "op_hs_empty \ IICF_Set.op_set_empty" interpretation hs: set_custom_empty hs_new op_hs_empty for A by unfold_locales (simp add: op_hs_empty_def) lemmas [sepref_fr_rules] = hs.hnr_op_empty[folded op_hs_empty_def] interpretation hs: bind_set_is_empty is_hashset Hash_Set_Impl.hs_isEmpty for A by unfold_locales interpretation hs: bind_set_member is_hashset Hash_Set_Impl.hs_memb for A by unfold_locales interpretation hs: bind_set_insert is_hashset Hash_Set_Impl.hs_ins for A by unfold_locales interpretation hs: bind_set_delete is_hashset Hash_Set_Impl.hs_delete for A by unfold_locales + interpretation hs: bind_set_size is_hashset hs_size for A + by unfold_locales + setup Locale_Code.open_block interpretation hs: bind_set_iterate is_hashset hs_is_it hs_it_init hs_it_has_next hs_it_next for A by unfold_locales simp setup Locale_Code.close_block + interpretation hs: bind_set_union is_hashset hs_is_it hs_it_init hs_it_has_next hs_it_next hs_union + for A + by unfold_locales simp + + subsection \Open Singly Linked List (osll)\ interpretation osll: bind_list os_list for A by unfold_locales interpretation osll_empty: bind_list_empty os_list os_empty for A by unfold_locales definition "osll_empty \ op_list_empty" interpretation osll: list_custom_empty "osll.assn A" os_empty osll_empty apply unfold_locales apply (rule osll_empty.hnr) by (simp add: osll_empty_def) interpretation osll_is_empty: bind_list_is_empty os_list os_is_empty for A by unfold_locales interpretation osll_prepend: bind_list_prepend os_list os_prepend for A by unfold_locales interpretation osll_hd: bind_list_hd os_list os_head for A by unfold_locales interpretation osll_tl: bind_list_tl os_list os_tl for A by unfold_locales interpretation osll_rev: bind_list_rev os_list os_reverse for A by unfold_locales subsection \Circular Singly Linked List (csll)\ (* TODO: In-place reversal of circular list! *) interpretation csll: bind_list cs_list for A by unfold_locales interpretation csll_empty: bind_list_empty cs_list cs_empty for A by unfold_locales definition "csll_empty \ op_list_empty" interpretation csll: list_custom_empty "csll.assn A" cs_empty csll_empty apply unfold_locales apply (rule csll_empty.hnr) by (simp add: csll_empty_def) interpretation csll_is_empty: bind_list_is_empty cs_list cs_is_empty for A by unfold_locales interpretation csll_prepend: bind_list_prepend cs_list cs_prepend for A by unfold_locales interpretation csll_append: bind_list_append cs_list cs_append for A by unfold_locales interpretation csll_hd: bind_list_hd cs_list cs_head for A by unfold_locales interpretation csll_tl: bind_list_tl cs_list cs_tail for A by unfold_locales interpretation csll_rotate1: bind_list_rotate1 cs_list cs_rotate for A by unfold_locales schematic_goal "hn_refine (emp) (?c::?'c Heap) ?\' ?R (do { x \ mop_list_empty; RETURN (1 \ dom [1::nat \ True, 2\False], {1,2::nat}, 1#(2::nat)#x) })" apply (subst iam_sz.fold_custom_empty[where N=10]) apply (subst hs.fold_custom_empty) apply (subst osll.fold_custom_empty) by sepref end diff --git a/thys/Refine_Imperative_HOL/IICF/Intf/IICF_Set.thy b/thys/Refine_Imperative_HOL/IICF/Intf/IICF_Set.thy --- a/thys/Refine_Imperative_HOL/IICF/Intf/IICF_Set.thy +++ b/thys/Refine_Imperative_HOL/IICF/Intf/IICF_Set.thy @@ -1,70 +1,77 @@ section \Set Interface\ theory IICF_Set imports "../../Sepref" begin subsection \Operations\ definition [simp]: "op_set_is_empty s \ s={}" lemma op_set_is_empty_param[param]: "(op_set_is_empty,op_set_is_empty)\\A\set_rel \ bool_rel" by auto +definition op_set_copy :: "'a set \ 'a set" where [simp]: "op_set_copy s \ s" + + context notes [simp] = IS_LEFT_UNIQUE_def (* Argh, the set parametricity lemmas use single_valued (K\) here. *) begin +sepref_decl_op (no_def) set_copy: "op_set_copy" :: "\A\set_rel \ \A\set_rel" where "A = Id" . sepref_decl_op set_empty: "{}" :: "\A\set_rel" . sepref_decl_op (no_def) set_is_empty: op_set_is_empty :: "\A\set_rel \ bool_rel" . sepref_decl_op set_member: "(\)" :: "A \ \A\set_rel \ bool_rel" where "IS_LEFT_UNIQUE A" "IS_RIGHT_UNIQUE A" . sepref_decl_op set_insert: Set.insert :: "A \ \A\set_rel \ \A\set_rel" where "IS_RIGHT_UNIQUE A" . sepref_decl_op set_delete: "\x s. s - {x}" :: "A \ \A\set_rel \ \A\set_rel" where "IS_LEFT_UNIQUE A" "IS_RIGHT_UNIQUE A" . sepref_decl_op set_union: "(\)" :: "\A\set_rel \ \A\set_rel \ \A\set_rel" . sepref_decl_op set_inter: "(\)" :: "\A\set_rel \ \A\set_rel \ \A\set_rel" where "IS_LEFT_UNIQUE A" "IS_RIGHT_UNIQUE A" . sepref_decl_op set_diff: "(-) ::_ set \ _" :: "\A\set_rel \ \A\set_rel \ \A\set_rel" where "IS_LEFT_UNIQUE A" "IS_RIGHT_UNIQUE A" . sepref_decl_op set_subseteq: "(\)" :: "\A\set_rel \ \A\set_rel \ bool_rel" where "IS_LEFT_UNIQUE A" "IS_RIGHT_UNIQUE A" . sepref_decl_op set_subset: "(\)" :: "\A\set_rel \ \A\set_rel \ bool_rel" where "IS_LEFT_UNIQUE A" "IS_RIGHT_UNIQUE A" . (* TODO: We may want different operations here: pick with predicate returning option, pick with remove, ... *) sepref_decl_op set_pick: "RES" :: "[\s. s\{}]\<^sub>f \K\set_rel \ K" by auto +sepref_decl_op set_size: "(card)" :: "\A\set_rel \ nat_rel" where "IS_LEFT_UNIQUE A" "IS_RIGHT_UNIQUE A" . + + end (* TODO: Set-pick. Move from where it is already defined! *) subsection \Patterns\ lemma pat_set[def_pat_rules]: "{} \ op_set_empty" "(\) \ op_set_member" "Set.insert \ op_set_insert" "(\) \ op_set_union" "(\) \ op_set_inter" "(-) \ op_set_diff" "(\) \ op_set_subseteq" "(\) \ op_set_subset" by (auto intro!: eq_reflection) lemma pat_set2[pat_rules]: "(=) $s${} \ op_set_is_empty$s" "(=) ${}$s \ op_set_is_empty$s" "(-) $s$(Set.insert$x${}) \ op_set_delete$x$s" "SPEC$(\\<^sub>2x. (\) $x$s) \ op_set_pick s" "RES$s \ op_set_pick s" by (auto intro!: eq_reflection) locale set_custom_empty = fixes empty and op_custom_empty :: "'a set" assumes op_custom_empty_def: "op_custom_empty = op_set_empty" begin sepref_register op_custom_empty :: "'ax set" lemma fold_custom_empty: "{} = op_custom_empty" "op_set_empty = op_custom_empty" "mop_set_empty = RETURN op_custom_empty" unfolding op_custom_empty_def by simp_all end end diff --git a/thys/Separation_Logic_Imperative_HOL/Examples/Hash_Set_Impl.thy b/thys/Separation_Logic_Imperative_HOL/Examples/Hash_Set_Impl.thy --- a/thys/Separation_Logic_Imperative_HOL/Examples/Hash_Set_Impl.thy +++ b/thys/Separation_Logic_Imperative_HOL/Examples/Hash_Set_Impl.thy @@ -1,150 +1,170 @@ section "Hash-Sets" theory Hash_Set_Impl imports Imp_Set_Spec Hash_Map_Impl begin subsection \Auxiliary Definitions\ definition map_of_set:: "'a set \ 'a\unit" where "map_of_set S x \ if x\S then Some () else None" lemma ne_some_unit_eq: "x\Some () \ x=None" by (cases x) auto lemma map_of_set_simps[simp]: "dom (map_of_set s) = s" "map_of_set (dom m) = m" "map_of_set {} = Map.empty" "map_of_set s x = None \ x\s" "map_of_set s x = Some u \ x\s" "(map_of_set s) (x\()) = map_of_set (insert x s)" "(map_of_set s) |` (-{x}) = map_of_set (s -{x})" apply (auto simp: map_of_set_def dom_def ne_some_unit_eq restrict_map_def intro!: ext) done lemma map_of_set_eq': "map_of_set a = map_of_set b \ a=b" apply (auto simp: map_of_set_def[abs_def]) apply (metis option.simps(3))+ done lemma map_of_set_eq[simp]: "map_of_set s = m \ dom m=s" apply (auto simp: dom_def map_of_set_def[abs_def] ne_some_unit_eq intro!: ext) apply (metis option.simps(3)) done subsection \Main Definitions\ type_synonym 'a hashset = "('a,unit) hashtable" definition "is_hashset s ht \ is_hashmap (map_of_set s) ht" lemma hs_set_impl: "imp_set is_hashset" apply unfold_locales apply rule unfolding is_hashset_def apply (subst map_of_set_eq'[symmetric]) by (metis preciseD[OF is_hashmap_prec]) interpretation hs: imp_set is_hashset by (rule hs_set_impl) definition hs_new :: "'a::{heap,hashable} hashset Heap" where "hs_new = hm_new" lemma hs_new_impl: "imp_set_empty is_hashset hs_new" apply unfold_locales apply (sep_auto heap: hm_new_rule simp: is_hashset_def hs_new_def) done interpretation hs: imp_set_empty is_hashset hs_new by (rule hs_new_impl) definition hs_memb:: "'a::{heap,hashable} \ 'a hashset \ bool Heap" where "hs_memb x s \ do { r\hm_lookup x s; return (case r of Some _ \ True | None \ False) }" lemma hs_memb_impl: "imp_set_memb is_hashset hs_memb" apply unfold_locales unfolding hs_memb_def apply (sep_auto heap: hm_lookup_rule simp: is_hashset_def split: option.split) done interpretation hs: imp_set_memb is_hashset hs_memb by (rule hs_memb_impl) definition hs_ins:: "'a::{heap,hashable} \ 'a hashset \ 'a hashset Heap" where "hs_ins x ht \ hm_update x () ht" lemma hs_ins_impl: "imp_set_ins is_hashset hs_ins" apply unfold_locales apply (sep_auto heap: hm_update_rule simp: hs_ins_def is_hashset_def) done interpretation hs: imp_set_ins is_hashset hs_ins by (rule hs_ins_impl) definition hs_delete :: "'a::{heap,hashable} \ 'a hashset \ 'a hashset Heap" where "hs_delete x ht \ hm_delete x ht" lemma hs_delete_impl: "imp_set_delete is_hashset hs_delete" apply unfold_locales apply (sep_auto heap: hm_delete_rule simp: is_hashset_def hs_delete_def) done interpretation hs: imp_set_delete is_hashset hs_delete by (rule hs_delete_impl) definition "hs_isEmpty == hm_isEmpty" lemma hs_is_empty_impl: "imp_set_is_empty is_hashset hs_isEmpty" apply unfold_locales apply (sep_auto heap: hm_isEmpty_rule simp: is_hashset_def hs_isEmpty_def) done interpretation hs: imp_set_is_empty is_hashset hs_isEmpty by (rule hs_is_empty_impl) definition "hs_size == hm_size" lemma hs_size_impl: "imp_set_size is_hashset hs_size" apply unfold_locales apply (sep_auto heap: hm_size_rule simp: is_hashset_def hs_size_def) done interpretation hs: imp_set_size is_hashset hs_size by (rule hs_size_impl) type_synonym ('a) hs_it = "('a,unit) hm_it" definition "hs_is_it s hs its it \ hm_is_it (map_of_set s) hs (map_of_set its) it" definition hs_it_init :: "('a::{heap,hashable}) hashset \ 'a hs_it Heap" where "hs_it_init \ hm_it_init" definition hs_it_has_next :: "('a::{heap,hashable}) hs_it \ bool Heap" where "hs_it_has_next \ hm_it_has_next" definition hs_it_next :: "('a::{heap,hashable}) hs_it \ ('a\'a hs_it) Heap" where "hs_it_next it \ do { ((x,_),it) \ hm_it_next it; return (x,it) }" lemma hs_iterate_impl: "imp_set_iterate is_hashset hs_is_it hs_it_init hs_it_has_next hs_it_next" apply unfold_locales unfolding hs_it_init_def hs_it_next_def hs_it_has_next_def hs_is_it_def is_hashset_def apply sep_auto apply sep_auto apply sep_auto apply (sep_auto eintros: hm.quit_iteration) done + interpretation hs: imp_set_iterate is_hashset hs_is_it hs_it_init hs_it_has_next hs_it_next by (rule hs_iterate_impl) +definition "hs_union + \ union_loop_ins hs_it_init hs_it_has_next hs_it_next hs_ins" + +lemmas hs_union_rule[sep_heap_rules] = + set_union_rule[OF hs_iterate_impl hs_ins_impl, + folded hs_union_def] + +lemma hs_union_impl: "imp_set_union +is_hashset hs_is_it hs_it_init hs_it_has_next hs_it_next hs_union" + apply (unfold_locales) + by (sep_auto) + +interpretation hs: imp_set_union + is_hashset hs_is_it hs_it_init hs_it_has_next hs_it_next hs_union + by (rule hs_union_impl) + + + + export_code hs_new hs_memb hs_ins hs_delete hs_isEmpty hs_size - hs_it_init hs_it_has_next hs_it_next + hs_it_init hs_it_has_next hs_it_next hs_union checking SML_imp end diff --git a/thys/Separation_Logic_Imperative_HOL/Examples/Imp_Set_Spec.thy b/thys/Separation_Logic_Imperative_HOL/Examples/Imp_Set_Spec.thy --- a/thys/Separation_Logic_Imperative_HOL/Examples/Imp_Set_Spec.thy +++ b/thys/Separation_Logic_Imperative_HOL/Examples/Imp_Set_Spec.thy @@ -1,67 +1,144 @@ section \Interface for Sets\ theory Imp_Set_Spec imports "../Sep_Main" begin text \ This file specifies an abstract interface for set data structures. It can be implemented by concrete set data structures, as demonstrated in the hash set example. \ locale imp_set = fixes is_set :: "'a set \ 's \ assn" assumes precise: "precise is_set" locale imp_set_empty = imp_set + constrains is_set :: "'a set \ 's \ assn" fixes empty :: "'s Heap" assumes empty_rule[sep_heap_rules]: " empty \<^sub>t" locale imp_set_is_empty = imp_set + constrains is_set :: "'a set \ 's \ assn" fixes is_empty :: "'s \ bool Heap" assumes is_empty_rule[sep_heap_rules]: " is_empty p <\r. is_set s p * \(r \ s={})>\<^sub>t" locale imp_set_memb = imp_set + constrains is_set :: "'a set \ 's \ assn" fixes memb :: "'a \ 's \ bool Heap" assumes memb_rule[sep_heap_rules]: " memb a p <\r. is_set s p * \(r \ a \ s)>\<^sub>t" locale imp_set_ins = imp_set + constrains is_set :: "'a set \ 's \ assn" fixes ins :: "'a \ 's \ 's Heap" assumes ins_rule[sep_heap_rules]: " ins a p \<^sub>t" locale imp_set_delete = imp_set + constrains is_set :: "'a set \ 's \ assn" fixes delete :: "'a \ 's \ 's Heap" assumes delete_rule[sep_heap_rules]: " delete a p \<^sub>t" locale imp_set_size = imp_set + constrains is_set :: "'a set \ 's \ assn" fixes size :: "'s \ nat Heap" assumes size_rule[sep_heap_rules]: " size p <\r. is_set s p * \(r = card s)>\<^sub>t" locale imp_set_iterate = imp_set + constrains is_set :: "'a set \ 's \ assn" fixes is_it :: "'a set \ 's \ 'a set \ 'it \ assn" fixes it_init :: "'s \ ('it) Heap" fixes it_has_next :: "'it \ bool Heap" fixes it_next :: "'it \ ('a\'it) Heap" assumes it_init_rule[sep_heap_rules]: " it_init p \<^sub>t" assumes it_next_rule[sep_heap_rules]: "s'\{} \ it_next it <\(a,it'). is_it s p (s' - {a}) it' * \(a \ s')>\<^sub>t" assumes it_has_next_rule[sep_heap_rules]: " it_has_next it <\r. is_it s p s' it * \(r\s'\{})>\<^sub>t" assumes quit_iteration: "is_it s p s' it \\<^sub>A is_set s p * true" + +locale imp_set_union = imp_set_iterate + + fixes union :: "'s \ 's \ 's Heap" + assumes union_rule[sep_heap_rules]: + "finite se \ <(is_set s p) * (is_set se q)> union p q <\r. + \\<^sub>As'. is_set s' r * (is_set se q)* true * \ (s' = s \ se)>" + +(* TODO: Move Generic implementation*) + +partial_function (heap) set_it_union + where [code]: "set_it_union + it_has_next it_next set_ins it a = do { + co \ it_has_next it; + if co then do { + (x,it') \ it_next it; + insx <- set_ins x a; + set_it_union it_has_next it_next set_ins it' (insx) + } else return a + }" + + + +lemma set_it_union_rule: + assumes "imp_set_iterate is_set is_it it_init it_has_next it_next" + assumes "imp_set_ins is_set set_ins" + assumes FIN: "finite it" + shows " + < is_it b q it iti * is_set a p> + set_it_union it_has_next it_next set_ins iti p + < \r. \\<^sub>As'. is_set s' r * is_set b q * true * \ (s' = a \ it) >" + proof - + interpret imp_set_iterate is_set is_it it_init it_has_next it_next + + imp_set_ins is_set set_ins + by fact+ + + from FIN show ?thesis + proof (induction arbitrary: a p iti rule: finite_psubset_induct) + case (psubset it) + show ?case + apply (subst set_it_union.simps) + using imp_set_iterate_axioms + apply (sep_auto heap: psubset.IH) + by (metis ent_refl_true ent_star_mono_true quit_iteration star_aci(2)) + qed + qed + + +definition union_loop_ins where +"union_loop_ins it_init it_has_next it_next set_ins a b \ do { + it <- (it_init b); + set_it_union it_has_next it_next set_ins it a + }" + + + +lemma set_union_rule: + assumes IT: "imp_set_iterate is_set is_it it_init it_has_next it_next" + assumes INS: "imp_set_ins is_set set_ins" + assumes finb: "finite b" + shows " + + union_loop_ins it_init it_has_next it_next set_ins p q + <\r. \\<^sub>As'. is_set s' r * true * is_set b q * \ (s' = a \ b)>" + proof - + interpret + imp_set_iterate is_set is_it it_init it_has_next it_next + + imp_set_ins is_set set_ins + by fact+ + + note it_aux[sep_heap_rules] = set_it_union_rule[OF IT INS finb] + show ?thesis + unfolding union_loop_ins_def + apply (sep_auto) + done + qed + + end