Uniification i booleska ringar, eller algebras, har nyligen väckt stort intresse både för sina teoretiska meriter, eftersom den är enhetlig, och för dess praktiska relevans för att manipulera maskinvarubeskrivningar, till exempel i BiJtner & Simonis (1986). Syftet med detta dokument är att ge en omfattande undersökning av teknik och resultat på området så långt det har utvecklats hittills. Men de flesta av resultaten har funnits länge; några av dem går tillbaka till Boole själv (Bode, 1847). En mycket bra källa för ranch av matematik underliggande unificat;ion i Booleska ringar är Rudeanu (1974). Det viktigaste resultatet är att Boolesk förening är enhetlig, det är antingen en ekvation har ingen lösning eller det finns en enda mest allmän unifier (i sequeh mgu). Vi presenterar två olika algoritmer, en på grund av Boole och den andra på LSwenheim. Papperet är uppbyggt på följande sätt: I avsnittet presenterar vi bara de mycket grundläggande fakta om Booleska ringar, precis tillräckligt för att förklara de enande algoritmer presenteras i avsnitt. Men algoritmerna presenteras i avsnitt yxa parameteriserade på förfaranden för att förenkla Booleska termer och hitta lösningar på Booleska ekvationer. För att lösa dessa två problem avsnitt åberopar lite struktur teori Booleska algebras. Detta gör det möjligt för oss i avsnitt och att hitta lösningar på de två återstående underproblemen med förenkling och att hitta särskilda lösningar. Avsnittet ger en grov komplexitetsanalys av de presenterade algoritmerna. Det visar sig att både enande metoder har samma komplexitet som är exponentiellt i antalet konstanter och variabler. I avsnittet förklaras hur de resultat som uppnåtts i fråga om en viss uppsättning operatörer (ringverksamheten + och *) kan överföras till en annan uppsättning operatörer. Hittills har vi bara hanterat villkoren över ringoperationerna a.nd godtyckliga konstanter. I avsnittet utvidgar vi enandet till inchde fria termer med variabler också. Den resulterande uppsättningen av formler är i grund och botten de av de okvantifierade predikat kalcuhs. Det visas att enandet i denna teori är finitaxiskt. Denna förlängning används i avsnitt för att erhålla semibeslutsförfarande för den första erder predicate kalkylen. *Denna forskning genomfördes vid t, han University of Manchester, ~Författaren erkänner partiellt stöd av Storbritannien SERC under graxxt GR8:tT18D. 275
REF studerar enandet i booleska ringar.
Boolean unification - The story so far
{'venue': 'J. Symb. Comput.', 'journal': 'J. Symb. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}