In database theory, Imieliński–Lipski algebra is an extension of relational algebra onto tables with different types of null values. It is used to operate on relations with incomplete information. Imieliński–Lipski algebras are defined to satisfy precise conditions for semantically meaningful extension of the usual relational operators, such as projection, selection, union, and join, from operators on relations to operators on relations with various kinds of "null values". These conditions require that the system be safe in the sense that no incorrect conclusion is derivable by using a specified subset F of the relational operators; and that it be complete in the sense that all valid conclusions expressible by relational expressions using operators in F are in fact derivable in this system. For example, it is well known that the three-valued logic approach to deal with null values, supported treatment of nulls values by SQL is not complete, see Ullman book. To show this, let T be: Take SQL query Q SQL query Q will return empty set (no results) under 3-valued semantics currently adopted by all variants of SQL. This is the case because in SQL, NULL is never equal to any constant – in this case, neither to “Spring” nor “Fall” nor “Winter” (if there is Winter semester in this school). NULL='Spring' will evaluate to MAYBE and so will NULL='Fall'. The disjunction MAYBE OR MAYBE evaluates to MAYBE (not TRUE). Thus Igor will not be part of the answer (and of course neither will Rohit). But Igor should be returned as the answer. Indeed, regardless what semester Igor took the Networks class (no matter what was the unknown value of NULL), the selection condition will be true. This “Igor” will be missed by SQL and the SQL answer would be incomplete according to completeness requirements specified in Tomasz Imieliński, Witold Lipski, 'Incomplete Information in Relational Databases'. It is also argued there that 3-valued logic (TRUE, FALSE, MAYBE) can never provide guarantee of complete answer for tables with incomplete information. Three algebras which satisfy conditions of safety and completeness are defined as Imielinski–Lipski algebras: the Codd-Tables algebra, the V-tables algebra and the Conditional tables (C-tables) algebra. == Codd-tables algebra == Codd-tables algebra is based on the usual Codd's single NULL values. The table T above is an example of Codd-table. Codd-table algebra supports projection and positive selections only. It is also demonstrated in [IL84 that it is not possible to correctly extend more relational operators over Codd-Tables. For example, such basic operation as join is not extendable over Codd-tables. It is not possible to define selections with Boolean conditions involving negation and preserve completeness. For example, queries like the above query Q cannot be supported. In order to be able to extend more relational operators, more expressive form of null value representation is needed in tables which are called V-table. == V-tables algebra == V-tables algebra is based on many different ("marked") null values or variables allowed to appear in a table. V-tables allow to show that a value may be unknown but the same for different tuples. For example, in the table below Gaurav and Igor order the same (but unknown) beer in two unknown bars (which may, or may not be different – but remain unknown). Gaurav and Jane frequent the same unknown bar (Y1). Thus, instead one NULL value, we use indexed variables, or Skolem constants . V-tables algebra is shown to correctly support projection, positive selection (with no negation occurring in the selection condition), union, and renaming of attributes, which allows for processing arbitrary conjunctive queries. A very desirable property enjoyed by the V-table algebra is that all relational operators on tables are performed in exactly the same way as in the case of the usual relations. === Conditional tables (c-tables) algebra === Example of conditional table (c-table) is shown below. It has additional column “con” which is a Boolean condition involving variables, null values – same as in V-tables. over the following table c-table Conditional tables algebra, mainly of theoretical interest, supports projection, selection, union, join, and renaming. Under closed-world assumption, it can also handle the operator of difference, thus it can support all relational operators. == History == Imieliński–Lipski algebras were introduced by Tomasz Imieliński and Witold Lipski Jr. in Incomplete Information in Relational Databases.
AI-complete
In the field of artificial intelligence (AI), tasks that are hypothesized to require artificial general intelligence to solve are informally known as AI-complete or AI-hard. Calling a problem AI-complete reflects the belief that it cannot be solved by a simple specific algorithm. Prior to 2013, problems supposed to be AI-complete included computer vision, natural language understanding, and dealing with unexpected circumstances while solving any real-world problem. AI-complete tasks were notably considered useful for distinguishing humans from automated agents, as CAPTCHAs aim to do. == History == The term was coined by Fanya Montalvo by analogy with NP-complete and NP-hard in complexity theory, which formally describes the most famous class of difficult problems. Early uses of the term are in Erik Mueller's 1987 PhD dissertation and in Eric Raymond's 1991 Jargon File. Expert systems, that were popular in the 1980s, were able to solve very simple and/or restricted versions of AI-complete problems, but never in their full generality. When AI researchers attempted to "scale up" their systems to handle more complicated, real-world situations, the programs tended to become excessively brittle without commonsense knowledge or a rudimentary understanding of the situation: they would fail as unexpected circumstances outside of its original problem context would begin to appear. When human beings are dealing with new situations in the world, they are helped by their awareness of the general context: they know what the things around them are, why they are there, what they are likely to do and so on. They can recognize unusual situations and adjust accordingly. Expert systems lacked this adaptability and were brittle when facing new situations. DeepMind published a work in May 2022 in which they trained a single model to do several things at the same time. The model, named Gato, can "play Atari, caption images, chat, stack blocks with a real robot arm and much more, deciding based on its context whether to output text, joint torques, button presses, or other tokens." Similarly, some tasks once considered to be AI-complete, like machine translation, are among the capabilities of large language models. == AI-complete problems == AI-complete problems have been hypothesized to include: AI peer review (composite natural language understanding, automated reasoning, automated theorem proving, formalized logic expert system) Bongard problems Computer vision (and subproblems such as object recognition) Natural language understanding (and subproblems such as text mining, machine translation, and word-sense disambiguation) Autonomous driving Dealing with unexpected circumstances while solving any real world problem, whether navigation, planning, or even the kind of reasoning done by expert systems. == Formalization == Computational complexity theory deals with the relative computational difficulty of computable functions. By definition, it does not cover problems whose solution is unknown or has not been characterized formally. Since many AI problems have no formalization yet, conventional complexity theory does not enable a formal definition of AI-completeness. == Research == Roman Yampolskiy suggests that a problem C {\displaystyle C} is AI-Complete if it has two properties: It is in the set of AI problems (Human Oracle-solvable). Any AI problem can be converted into C {\displaystyle C} by some polynomial time algorithm. On the other hand, a problem H {\displaystyle H} is AI-Hard if and only if there is an AI-Complete problem C {\displaystyle C} that is polynomial time Turing-reducible to H {\displaystyle H} . This also gives as a consequence the existence of AI-Easy problems, that are solvable in polynomial time by a deterministic Turing machine with an oracle for some problem. Yampolskiy has also hypothesized that the Turing Test is a defining feature of AI-completeness. Groppe and Jain classify problems which require artificial general intelligence to reach human-level machine performance as AI-complete, while only restricted versions of AI-complete problems can be solved by the current AI systems. For Šekrst, getting a polynomial solution to AI-complete problems would not necessarily be equal to solving the issue of artificial general intelligence, while emphasizing the lack of computational complexity research being the limiting factor towards achieving artificial general intelligence. For Kwee-Bintoro and Velez, solving AI-complete problems would have strong repercussions on society.
Parallel terraced scan
The parallel terraced scan is a multi-agent based search technique that is basic to cognitive architectures, such as Copycat, Letter-string, the Examiner, Tabletop, and others. It was developed by John Rehling and Douglas Hofstadter at the Center for Research on Concepts and Cognition at Indiana University, Bloomington. The parallel terraced scan builds on the concepts of the workspace, coderack, conceptual memory, and temperature. According to Hofstadter the parallel and random nature of the processing captures aspects of human cognition.
Revoscalepy
revoscalepy is a machine learning package in Python created by Microsoft. It is available as part of Machine Learning Services in Microsoft SQL Server 2017 and Machine Learning Server 9.2.0 and later. The package contains functions for creating linear model, logistic regression, random forest, decision tree and boosted decision tree, in addition to some summary functions for inspecting data. Other machine learning algorithms such as neural network are provided in microsoftml, a separate package that is the Python version of MicrosoftML. revoscalepy also contains functions designed to run machine learning algorithms in different compute contexts, including SQL Server, Apache Spark, and Hadoop. In June 2021, Microsoft announced to open source the revoscalepy and RevoScaleR packages, making them freely available under the MIT License.
Knowledge Engineering Environment
Knowledge Engineering Environment (KEE) is a frame-based development tool for expert systems. It was developed and sold by IntelliCorp, and was first released in 1983. It ran on Lisp machines, and was later ported to Lucid Common Lisp with the CLX library, an X Window System (X11) interface for Common Lisp. This version was available on several different UNIX workstations. On KEE, several extensions were offered: Simkit, a frame-based simulation library KEEconnection, database connection between the frame system and relational databases In KEE, frames are called units. Units are used for both individual instances and classes. Frames have slots and slots have facets. Facets can describe, for example, a slot's expected values, its working value, or its inheritance rule. Slots can have multiple values. Behavior can be implemented using a message passing model. KEE provides an extensive graphical user interface (GUI) to create, browse, and manipulate frames. KEE also includes a frame-based rule system. In the KEE knowledge base, rules are frames. Both forward chaining and backward chaining inference are available. KEE supports non-monotonic reasoning through the concepts of worlds. Worlds allow providing alternative slot-values of frames. Through an assumption-based truth or reason maintenance system, inconsistencies can be detected and analyzed. ActiveImages allows graphical displays to be attached to slots of Units. Typical examples are buttons, dials, graphs, and histograms. The graphics are also implemented as Units via KEEPictures, a frame-based graphics library.
InstallCore
InstallCore (stylized as installCore) was an installation and content distribution platform created by ironSource, considered potentially unwanted programs (PUP) by a number of anti-malware vendors. It included a software development kit (SDK) for Windows and Mac OS X. The program allowed those using it for distribution to include monetization by advertisements or charging for installation, and made its installations invisible to the user and its anti-virus software. The platform and its programs have been rated potentially unwanted programs (PUP) or potentially unwanted applications (PUA) by anti-malware product vendors since 2014, and by Windows Defender Antivirus since 2015. The platform was primarily designed for efficient web-based deployment of various types of application software. As of August 2012, InstallCore was managing 100 million installations every month, offering services for paid, unpaid, and free software by using the SDK version. == History == The InstallCore team introduced the first version of the SDK at the beginning of 2011. The SDK was a fork of the FoxTab installer and had only basic Installation features. InstallCore was discontinued as part of a company flotation in late 2020. == Criticism and malware classification == InstallCore and its software packages have been classified as potentially unwanted programs (PUP) or potentially unwanted applications (PUA), by anti-malware product vendors and Windows Defender Antivirus from 2014–2015 onwards, with many stating that it installs adware and other additional PUPs. Malwarebytes identified the program as "a family of bundlers that installs more than one application on the user's computer". It has been described as "crossing the line into full-blown malware" and a "nasty Trojan".
Metaclass (knowledge representation)
In knowledge representation, particularly in the Semantic Web, a metaclass is a class whose instances can themselves be classes. Similar to their role in programming languages, metaclasses in ontology languages can have properties otherwise applicable only to individuals, while retaining the same class's ability to be classified in a concept hierarchy. This enables knowledge about instances of those metaclasses to be inferred by semantic reasoners using statements made in the metaclass. Metaclasses thus enhance the expressivity of knowledge representations in a way that can be intuitive for users. While classes are suitable to represent a population of individuals, metaclasses can, as one of their feature, be used to represent the conceptual dimension of an ontology. Metaclasses are supported in the Web Ontology Language (OWL) and the data-modeling vocabulary RDFS. Metaclasses are often modeled by setting them as the object of claims involving rdf:type and rdfs:subClassOf—built-in properties commonly referred to as instance of and subclass of. Instance of entails that the subject of the claim is an instance, i.e. an individual that is a member of a class. Subclass of entails that the subject is a class. In the context of instance of and subclass of, the key difference between metaclasses and ordinary classes is that metaclasses are the object of instance of claims used on a class, while ordinary classes are not objects of such claims. (e.g. in a claim Bob instance of Human, Bob is the subject and an Instance, while the object, Human, is an ordinary class; but a further claim that Human instance of Animal species makes "Animal species" a metaclass because it has a member, "Human", that is also a Class). OWL 2 DL supports metaclasses by a feature called punning, in which one entity is interpreted as two different types of thing—a class and an individual—depending on its syntactic context. For example, through punning, an ontology could have a concept hierarchy such as Harry the eagle instance of golden eagle, golden eagle subclass of bird, and golden eagle instance of species. In this case, the punned entity would be golden eagle, because it is represented as a class (second claim) and an instance (third claim); whereas the metaclass would be species, as it has an instance that is a class. Punning also enables other properties that would otherwise be applicable only to ordinary instances to be used directly on classes, for example "golden eagle conservation status least concern." Having arisen from the fields of knowledge representation, description logic and formal ontology, Semantic Web languages have a closer relationship to philosophical ontology than do conventional programming languages such as Java or Python. Accordingly, the nature of metaclasses is informed by philosophical notions such as abstract objects, the abstract and concrete, and type-token distinction. Metaclasses permit concepts to be construed as tokens of other concepts while retaining their ontological status as types. This enables types to be enumerated over, while preserving the ability to inherit from types. For example, metaclasses could allow a machine reasoner to infer from a human-friendly ontology how many elements are in the periodic table, or, given that number of protons is a property of chemical element and isotopes are a subclass of elements, how many protons exist in the isotope hydrogen-2. Metaclasses are sometime organized by levels, in a similar way to the simple Theory of types where classes that are not metaclasses are assigned the first level, classes of classes in the first level are in the second level, classes of classes in the second level on the next and so on. == Examples == Following the type-token distinction, real world objects such as Abraham Lincoln or the planet Mars are regrouped into classes of similar objects. Abraham Lincoln is said to be an instance of human, and Mars is an instance of planet. This is a kind of is-a relationship. Metaclasses are class of classes, such as for example the nuclide concept. In chemistry, atoms are often classified as elements and, more specifically, isotopes. The glass of water one last drank has many hydrogen atoms, each of which is an instance of hydrogen. Hydrogen itself, a class of atoms, is an instance of nuclide. Nuclide is a class of classes, hence a metaclass. == Implementations == === RDF and RDFS === In RDF, the rdf:type property is used to state that a resource is an instance of a class. This enables metaclasses to be easily created by using rdf:type in a chain-like fashion. For example, in the two triples the resource species is a metaclass, because golden eagle is used as a class in the first statement and the class golden eagle is said to be an instance of the class species in the second statement. This way of doing allows :species to have non-class instances. RDF also provides rdf:Property as a way to create properties beyond those defined in the built-in vocabulary. Properties can be used directly on metaclasses, for example "species quantity 8.7 million", where quantity is a property defined via rdf:Property and species is a metaclass per the preceding example above. RDFS, an extension of RDF, introduced rdfs:Class and rdfs:subClassOf and enriched how vocabularies can classify concepts. Whereas rdf:type enables vocabularies to represent instantiation, the property rdfs:subClassOf enables vocabularies to represent subsumption. RDFS thus makes it possible for vocabularies to represent taxonomies, also known as subsumption hierarchies or concept hierarchies, which is an important addition to the type–token distinction made possible by RDF. Notably, the resource rdfs:Class is an instance of itself, demonstrating both the use of metaclasses in the language's internal implementation and a reflexive usage of rdf:type. RDFS is its own metamodel. This allows a second way to express that a resource is a metaclass. A triple to instantiate rdfs:Class, for example :golden_eagle rdf:type rdfs:Class will declare :golden_eagle as a class. It's also possible to subclass the rdfs:Class resource to declare a meta-class resource, for example :species rdfs:SubclassOf. By deduction, any instance of :species is then a class, so it is a class with class-instances, a meta-class.. This second way does not allows non-class instances of species and explicitly declares :tpecies as a meta-class. === OWL === In some OWL flavors like OWL1-DL, entities can be either classes or instances, but cannot be both. This limitations forbids metaclasses and metamodeling. This is not the case in the OWL1 full flavor, but this allows the model to be computationally undecidable. In OWL2, metaclasses can implemented with punning, that is a way to treat classes as if they were individuals. Other approaches have also been proposed and used to check the properties of ontologies at a meta level. ==== Punning ==== OWL 2 supports metaclasses through a feature called punning. In metaclasses implemented by punning, the same subject is interpreted as two fundamentally different types of thing—a class and an individual—depending on its syntactic context. This is similar to a pun in natural language, where different senses of the same word are emphasized to illustrate a point. Unlike in natural language, where puns are typically used for comedic or rhetorical effect, the main goal of punning in Semantic Web technologies is to make concepts easier to represent, closer to how they are discussed in everyday speech or academic literature. Although OWL 2 permits the same symbol to assume different roles, its standard semantics (known as Direct Semantics) still interprets the symbol differently depending on whether it is used as an individual, a class, or a property. === Protégé === In the ontology editor Protégé, metaclasses are templates for other classes who are their instances. == Classification == Some ontologies like the Cyc AI project's classifies classes and metaclasses. Classes are divided into fixed-order classes and variable-order classes. In the case of fixed-order classes, an order is attributed for metaclasses by measuring the distance to individuals with respect to the number of "instance of" triples that are necessary to find an individual. Classes that are not metaclasses are classes of individuals, so their order is "1" (first-order classes). Metaclasses that are classes of first-order classes' order is "2" (second-order classes), and so on. Variable-order metaclasses, on the other hand, can have instances; one example of variable-order metaclass is the class of all fixed-order classes.