Abstrakt. Ställa begränsningar är integrationsrelationer mellan uppsättningar av marktermer över ett rankat alfabet. De har använts i stor utsträckning vid programanalys och typinferens. Här presenterar vi en ekvationell axiomatisering av algebran av bestämda begränsningar. Modeller av dessa axiom kallas termet algebras. De är relaterade till de booleska algebras med operatörer av J onsson och Tarski. Vi de ne en familj av kombinatoriska modeller som kallas topologisk term automata, som i huvudsak är den term automata studeras av Kozen, Palsberg, och Schwartzbach utrustade med en topologi så att alla relevanta operationer är kontinuerlig. Dessa modeller liknar Kripke-ramar för modal eller dynamisk logik. Vi etablerar en sten dualitet mellan termeret algebras och topological term automata, och använder detta för att härleda en fullständighet teorem för en relaterad multidimensionell modal logik. Slutligen bevisar vi en liten modell egenskap genom ltration, och hävdar att detta resultat innehåller essensen av flera algoritmer som visas i litteraturen på bestämda begränsningar.
Dokumentet REF innehåller kärnan i alla dessa algoritmer.
Logical Aspects of Set Constraints
{'venue': 'In Proc. 1993 Conf. Computer Science Logic (CSL’93', 'journal': None, 'mag_field_of_study': ['Computer Science']}