HiddenAlgebraCurrentResearchContentsofthispageHiddenalgebraa
nalmodelof'abstractbehaviours'.Behaviouralequivalencearisesa
ecificationofAbstractDataTypes.Springer-VerlagLectureNotesin
tory,1994.[Revisedversion,1996.]Anotherpossibility,currently
h,InA.W.Roscoe(ed.),AClassicalMind:EssaysinHonourofC.A.R.Hoa
iddenAlgebraandCoalgebraTherelationshipbetweenhiddenalgebraa
onsystemscanbeviewedascoalgebrasofanendofunctorthatusesthepo
mparticularlynaturalwhenviewedasconstructionsoncolagebras:fi
inimalrealisation.InMagneHaveraaenandOlafOweandOle-JohanDahl
enAlgebra:parameterizedobjectsandinheritance.Draftofapaperpr
hsaysthatthecategoryofcoalgebrasofaleftexactcomonadisatopos.
ndcoalgebraHiddenalgebrawithsubsortsToposesofhiddenalgebrasH
fobjectsthathaveobjectsasattributes).Onepromisingavenueofres
esentedatthe12thWorkshoponAlgebraicDevelopmentTechniques,Jun
nalmodels,behaviouralequivalence,productsandconcurrentconnec
ospecifyconstructorsforcomplexclassesofobjects(i.e.,classeso
earchistoextendthealgebraicandcoalgebraicnatureofhiddenalgeb
rell,Atoposofhiddenalgebras.TechnicalReportPRG-TR18-97,Prog
beingexplored,introducesorderedsortswhilemaintiningthelinkwi
tions,andthecofreeextensionsusedinparameterizedhiddenspecifi
coalgebraic.Hiddenalgebraimposesaconstraintonoperations:they
ratoallowoperationsthattakemorethanonehiddensortasargument,w
iththeideathatmodelshaveacoalgebraiccomponentthatdescribesth
re,Prentice-HallInternationalSeriesinComputerScience,chapter
JosephA.Goguen.Provingcorrectnessofrefinementandimplementati
thcoalgebra.ToposesofHiddenModelsArecentdevelopmentisthereal
ductsinthetopos,andthetruthobjectconsistsofabstractstatesand
roofsintheinternallanguageofthetopos.Furtherreading:JamesWor
cations.Theseconstructionsareoftenthedualoftheirclassicalalg
e1997.SeealsotheBibliographypage.SubsortsThealgebraicspecifi
sievesofcontexts.Oneinterestingpossibilitywouldbetolookatref
sthekernelofuniquemorphismstothefinalmodel.Thisgivesafundame
ebraiccounterparts.Forexample,hiddentheoriesdefinecovarietie
nctor.However,thereisnothinginherentlycoalgebraicinhiddenalg
maytakenomorethanoneargumentofhiddensort.Thismakesitawkwardt
ndRazvanDiaconescu.HidingandBehaviour:anInstitutionalApproac
rordefinitionandhandling,coercion,overwriting,multiplerepres
isationthatthemodelsofahiddensignaturewithnoconstantsformsat
ust1997.[HiddenAlgebraHome|Background|People|Bibliography]5A
eading:GrantMalcolm.Behaviouralequivalence,bisimulation,andm
s,andtheadjunctionwithunderlyingcarriersetsgivesacomonadicfu
tingsystems,partialrecursivefunctions,multipleinheritance,er
ebratoorderedsorts,correspondingtodifferentwaysoftreatingerr
inementsasgeometricmorphisms,andperhapsconstructcoinductionp
ch.HorstReichelnotedthecorrespondancebetweenobjectclassesand
wersetfunctor.Manyinterestingconstructionsinhiddenalgebrasee
a.Theextensionofhiddenalgebratohiddenordersortedalgebraisnot
sheavesonan'anaemic'(withoutproducts)versionofaLawverecatego
eirbehaviour,andanalgebraiccomponentforconstructors.Furtherr
(eds.),RecentTrendsinDataTypeSpecifications.11thWorkshoponSp
ryforthesignature.Behaviouralequivalencearisesnaturallyaspro
isetoanendofunctorwhosecoalgebrasarethehiddenmodelsofthesign
reallydifficult,butitcannotbetrivial,sinceitcoversnontermina
entation,andmore.Infact,therearemanywaysofextendinghiddenalg
5,pages75-92.Prentice-HallInternational,1994.GrantMalcolmand
ComputerScience,1996.CorinaCîrstea,CoalgebraSemanticsforHidd
opos.ThisseemstoberelatedtoaresultofMoerdijkandMacLane'swhic
Anotherwayofviewingthetoposisasaslicecategoryofthetoposofpre
coalgebras,anditwasestablishedthateveryhiddensignaturegivesr
ature.Moreover,forsignatureswithnoconstantsymbols,thereisafi
ntalrelationshipbetweencoinductionandbisimulation,astransiti
ebra;infact,thetreatmentofconstantsymbolsismorealgebraicthan
orsincomputations.TwopossibilitiesaredescribedinRodBurstalla
cationlanguageOBJhasanotionofsubsortbasedonordersortedalgebr
ndcoalgebrahasbeenveryproductiveinsuggestingnewareasofresear
rammingResearchGroup,OxfordUniversityComputingLaboratory,Aug
on.TechnicalMonographPRG-114,OxfordUniversityComputingLabora
ugust1997.............................More_Hidden_Algebra...

HiddenAlgebraMoreHiddenAlgebraContentsof
enotedifferentstates,thosestatescannotbe
lyfortheothermethods.TheequationsinFLAGc
.optail:State-]State.endthNowaclassofobj
beusedtosolvequeries;ingeneral,coinducti
hodsontheattributeup?,thoughingeneralequ
dLogicParadigmsTheFLAGexampleaboveshowsh
lementationoftheSTREAMtheoryisgivenbythe
heflagisup.ModelsofFLAGhaveastateset,Fla
agf2iffup?f1=up?f2b1RBoolb2iffb1=b2canbe
senderobject:thSENDER||SUMisprSUM[SENDER
.[HiddenAlgebraHome|Research|People|Bibl
isanimplementationofSTREAM,wecanpassSEND
andLogicParadigmsParameterizedprogrammin
theleftandrightsidesareequalinallcontext
rem.Behaviouralequivalence(equalityinall
coinduction:ifanybehaviouralcongruencere
eequationisbehaviourallysatisfied.Forexa
befoundonthebibliographypage.TheObjectan
stream,andthemethodtailsendsthisvaluetot
ERasanargumenttotheparameterizedtheorySU
].varS:State.eqinputaddS=inputS.eqsumput
nticsofparameterizedalgebraicspecificati
ldeductionissoundforbehaviouralsatisfact
ion,asthisallowstheobjectandlogicparadig
ce,whereabehaviouralcongruenceisafamilyo
onaboutclassesofobjectswhosebehaviouriss
gAsimpleexampleofaHiddenTheoryisthefollo
atisfiedbythefirstmodeldescribedabove,bu
ughtheleftandrightsidesoftheequationmayd
objectparadigm,weneedahiddenHerbrandtheo
e.g.,ofobjectorienteddatabases)toreasoni
(N,S)=sumS.eqput(N,addS)=addput(N,S).end
methodstoraiseit,lowerit,orreverseit:Thi
snotationisbasedonthelanguageOBJ,althoug
sup,dnandrevchangethestateofflagobjects,
ion.Thismeanswecanusestandardtechniquess
uchasrewritingtoprovethingsabouthiddensp
mstobecombinedatthesemanticlevel.Wedefin
atequationaltechniquessuchasnarrowingcan
adigmmayinvolvequeriestoanobjectoriented
theadofthestreamtotherunningtotal,whichi
thInterestingly,thesemanticsofhiddenpara
ingaflagtwicehasnoeffect.Thisequationiss
fcongruencerelationsforeachsortsuchthatt
lsbehaviourallysatisfyrevrevF=F.Moreonco
blecode)astheresultofthequery.Parameteri
owerofhigherorderprogramminginasimplefir
rate'astreambysendingnumberstoit:Here,th
andup?isanattributethatsayswhetherornott
eset{true,false},withtheobviousoperation
sfromFLAG,wecanshowthatup?revrevF=up?Fwh
ngthosevariables.Suchaqueryisbehavioural
ariablesthatmakeseachtibehaviourallyequi
bra(seetheBibliographypage),whichmeansth
rieswithotherhiddentheories,weobtainthep
ons;seetheBibliographypageformoredetails
ly,aflagobjectcanbeeitherupordown,andhas
anbethoughtofasdefiningtheeffectofthemet
ails.CoinductionandBisimulationEquationa
sallowsustoshowbehaviouralsatisfactionby
inductionanditsrelationtobisimulationcan
pecifiedbyequationswithuniversallyquanti
bedefinedforotherlogicalconnectives.Ofpa
rticularinterestisexistentialquantificat
valenttoti'.Toestablishthecombinedlogic-
onemightdescribeaholidaypackage(orasoftw
wingspecificationofflagobjects.Intuitive
meofthehiddensortofflagobjects.Themethod
entheyarebehaviourallyequivalent,andsoth
showntobeabehaviouralcongruence,andsince
up?revrevF=up?F,itfollowsthatallFLAGmode
databasewheretheresultingobjectisnotjust
reFLAGisthenameofthemoduleandFlagisthena
andattributes.Forexample,onemodelhasstat
ichisvalidforallFLAGmodels.Morepowerfult
hiddenHerbrandtheoremexistsforhiddenalge
zedProgrammingByparameterizinghiddentheo
thispageCoinductionandbisimulationObject
eahiddenquerytobeasentenceoftheform(Exis
tsX)t1=t1'and...andtn=tn'whereXisasetofv
ngoverasingle'Herbranduniverse'termalgeb
arepackage)thatonewants,andthenactuallyg
ecification,sobehaviouralsatisfactionall
fiedvariables.Behaviouralsatisfactioncan
remtoreducereasoningoverarbitrarymodels(
followingspecificationofobjectsthat'gene
hestream.ThetailmethodisimportedfromtheS
themethodupappen th FLAG is
satisfytheequati   sort Flag .
ecifications.For   op up?_ : Flag -> Bool .
ra,asinordinaryl   ops (up_) (dn_) (rev_) : Flag -> Flag .
onwillalsobeneed   var F : Flag .
inagivenstreamca   eq  up? up F  =  true .
TREAMtheoryinthe   eq  up? dn F  =  false .
s,whereacontexti   eq  up? rev F =  not up? F .
sforup,dn,etc.An endth
ationscanspecifyabstractbehaviours.Forex
ample,theequationrevrevF=Fsaysthatrevers
owsustoabstractawayfromimplementationdet
echniquesfortheo th SUM[S :: STREAM] is
wingtheory,which   op sum : State -> Nat .
htheintendedsema   op add : State -> State .
g,andoperationsc   var N : Nat .
,dn,rev}*,theset   var S : State .
herelationsonvis   eq  sum(add(S))  =  head(S) + sum(S) .
latestheleftandr   eq  sum(tail(S)) =  sum(S) .
lysatisfiedifthe   eq  head(add(S)) =  head(S) .
Here,themethodad endth
sgivenbytheattributesum.Amoreconcreteimp
M,tobuildasystemthatsumsthevaluessentbya
wedbyanattribute.Inotherwords,bothmodels
distinguishedbya th SENDER is
contexts)isthela   pr STREAM .
mple,thefamilyof   op input : State -> Nat .
ariablesandeacht   op put : Nat State -> State .
implehiddentheor   var N : Nat .
rs:thSTREAMissor   var S : State .
ectsthatkeeparun   eq  head(put(N,S))  =  head(S) .
emethodputsetsth   eq  input(put(N,S)) =  N .
ourallysatisfyth   eq  head(tail(S))  =  input(S) .
owhiddenalgebrac   eq  input(tail(S)) =  input(S) .
meterizedtheorie endth
tnotbythesecond.However,bothmodelsbehavi
evrevF=up?upFup?dnrevrevF=up?dnF...Altho
ettheticketsandreservations(ortheexecuta
stordersetting.Asanexample,webeginwithas
retrieved,butactuallycreated.Forexample,
iography]5August1997.................PbN