Nevertheless, I felt that there have been less presentations at #AAAI2024 about classic #AI topics such as #ConstraintSatisfaction, #KnowledgeRepresentation and #Reasoning, #Planning, #Scheduling, #Search and so on. I only hope that these topics will not end like rule-based systems, which are nowadays used in many business applications, but largely ignored in academia. On the positive side, there has been a good number of presentations about economic paradigms and game theory.
Today I found this lovely lattice of every possible "clone" of Boolean functions. A clone is a set closed under projection and composition, so you can think of each entry as the set of circuits constructible using particular logic gates.
But, there's more! This is from "The Complexity of Satisfiability Problems: Refining Schaefer’s Theorem" (https://www.sciencedirect.com/science/article/pii/S0022000008001141) The colored nodes are the sets of functions that can be polymorphisms of a set of relations. They are the invariants or closures of those relations -- pick N tuples from the relation, apply the N-ary function elementwise, and out pops a new element of the relation.
Knowing the set of polymorphisms for a set of relations R tells you the complexity class of the decision problem for conjuctive clauses built out of R. For example, we can pick relations that correspond to 3SAT, but they have only the identity polymorphisms, so the decision problem is in NP. This provides more structure within P (under AC0-reductions) than the older Shaefer's Dichotomy Theorem.
Now, I don't really understand the proof yet. In fact, I don't even understand why these classes are the only ones that can be polymorphisms of binary relations. I think I should be able to prove that some of them could not be, but the paper just breezily states "It is immediate from a look at Figure 1 that this covers all cases." The lattice structure itself was discovered by Emil Post.
Finally, #ConstraintSatisfaction makes it to the #AIHype! Not sure that it is the good thing to hide the topic behind acronyms (CCSP for continuous constraint satisfaction problems, which are studied since several decades) and to catch the attention by intriguing phrases speaking of robots that make decisions?
“How Can Robots Make Better Decisions? MIT and Stanford Researchers Introduce Diffusion-CCSP for Advanced Robotic Reasoning and Planning”
#ThemeOneProgram • #JetsAndSharks 1
• https://inquiryintoinquiry.com/2022/08/25/theme-one-program-jets-and-sharks-1/
In developing the Theme One Program I tested successive versions of its #InferenceEngine for #PropositionalCalculus #ConstraintSatisfaction on examples of #Logic problems current in the literature of the day. #McClelland and #Rumelhart's #PDPHandbook set one of the wittiest gems ever to whet one's app-titude so I could hardly help but take it on. The linked text is a light revision of the way I set it up in the program's User Guide.
#ThemeOneProgram • #SurveyPage
• https://inquiryintoinquiry.com/2022/06/12/survey-of-theme-one-program-4/
A program I worked on all through the 80s aimed to develop #Algorithms and #DataStructures for integrating #EmpiricalLearning and #LogicalReasoning. I had earlier developed programs for #Learning #TwoLevelFormalLanguages and for #PropositionalLogic #ConstraintSatisfaction based on C.S. #Peirce's #LogicalGraphs. Getting those 2 faculties to work together meant integrating the ways of #Empiricism and #Rationalism.
#ThemeOneProgram #Learning #Reasoning
#Logic #LogicalGraphs #FormalLanguages
#Algorithm #DataStructure #GraphTheory
#Peirce #PragmaticSemioticInformation
#Empiricism #Rationalism #Pragmatism
#ModelTheory #ProofTheory #Semiotics
#ParallelDistributedProcessing #PDP
#Grossberg #McClelland #Rumelhart
