The purpose of this document is to categorize and relate KP research at LIM, if only for the
LIM day "Systèmes formels sous-jacents aux fondements de nos activités de recherche"
(beginning of October; decided during the
Conseil de laboratoire du 10 Mai 2024). KP examples:
- K. Acquisition, K. Extraction, K. Mining, K. Discovery, K. Classification, K. Categorization
- K. Retrieval, K. Comparison, K. Mapping, K. Matching, K. Merging, K. Evaluation, K. Validation, K. Analysis
- K. Representation, K. Normalization, K. Organization, K. Partitioning, K. Modularization, K. Sharing
- K. Engineering, K. Modelling, K. Management, K. Edition, K. Exploitation
- K. Import, K. Interpretation, K. Translation, K. Export, K. Generation
- K. Inferencing (reasoning, deduction, abduction, induction, analogy/case-based, Bayesian/fuzzy, monotonic, ...).
0. Some Useful Types about Information (= Data / Knowledge) and KPs
The following list defines terms – and thereby distinctions –
that are useful for the categorization of research in KPs.
In this HTML version,
the rest of this section formally categorizes these distinctions.
In the Google Doc version, this formalization is referred to.
Information Object: anything that has or may have a truth value (e.g. statement, proposition),
or that is part of such a thing (e.g., a term);
either "Knowledge Representation" (KB; see next item below) or "Data", for each particular
agent(software or not), depending on whether this agent can interpret the semantics of the information.
Knowledge Representation (KR, or simply knowledge):
information that is at least partially represented
in a language having a formal syntax (formal: unambiguous, hence unique) which has a meaning
in a logic (→ KR language: KRL),
via semantic relations (e.g. subtype, type, part, result, instrument, time, place, author, ...), and
that is interpreted by an agent (this is what make an information object a KR for this agent).
Some expressions (parts of information objects that do not have a truth value) of a KR may be informal,
e.g., some of its terms, but not its syntax.
Knowledge Representing: creating KRs.
Term: information object with a formal/informal identifier (hence, if formal, with a unique sense).
Individual: term that is not a type, i.e. that cannot have an instance.
Knowledge Base (KBs): set of KRs; composed of an ontology (the definitions of the terms used
in the KB) and the base of facts (the rest of the KB).
Like a database, a KB may either be networked (i.e., "distributed on"/"composed of" other KBs) or
physical.
Database: an information base that is not a KB;
composed of a database schema (formal description
of the structure the database may have but without using a KRL; this is the counterpart of an ontology
for a database) and a set of data following this schema.
An XML document is a database (its "database schema" is an XML schema).
The schema may be empty. An informal document, or a set of informal documents, is a database.
KB Management System (KBMS): software allowing to manage KBs.
Like a DBMS, a KBMS may be either "networked" or "physical".
Database Management System (DBMS): software allowing to manage databases.
Well-organized KB: KB which, if it contains contradictions or full/partial redundancies that its
inference engines(s) or users can detect, represents them via relations specializing those of
exclusion, generalization or implication; in such a KB, statements that are not definitions are beliefs
(instead of facts) and contradictory beliefs do not make the KB inconsistent.
Linked Data: set of KBs on the Web, poorly interrelated (i.e. very far from forming a
networked well-organized KB, hence mostly "data" for each other); they may or may not be used for
indexing documents.
Individual-focused Knowledge Representing: creating KBs mostly to represent relations from/to named
individuals or creating ontologies mostly to enable representing relations between individuals
(as opposed to creating KBs mostly composed of general statements about unnamed instances of
particular types, or about properties of these types).
This is what RDF+OWL is meant to be used for (and is used for), if only because of its
restricted expressiveness. This approach may be ok for "restricted KS" (see below) but not
"general KS".
KR Sharing (KS): representing and exchanging KRs.
Restricted KS:
KS close to data sharing in the sense that it is about
easing the exchange of structured information (KRs or structured data)
between particular agents (persons, businesses, or applications) that
can discuss with each other to solve ambiguities or other problems,
representing only information that is needed for particular applications or that can
be completely or efficiently exploited by particular agents.
This is the approach that the W3C has in mind for KS or "Linked Data" (an apt renaming of its vision for
a Semantic Web).
The rest of this section uses the FL notation to categorize some of the above cited distinctions.
FL is designed for expressiveness, flexibility and
"readability even when there are many relations to represent, see or compare".
After each FL block, its Formalized-English (FE) version is given to show how the FL version
should be read. This also shows that, being more verbose and easy-to-understand for beginners,
FE also makes it harder to represent, see or compare more than a few objects or relations.
any ?thing pm#type: pm#Thing. /* A definition of pm#Thing is: anything is of type pm#Thing.
In FE:
any ?thing has for pm#type pm#Thing. //A definition of pm#Thing is: anything is of type pm#Thing
//More explanations:
// - variable IDs begin by '?'
// - IDs prefixed by "pm#" have been created by a user who has for ID (among others) "pm" (Philippe Martin)
// - "any" (the universal quantifier to be used for definitions) has no prefix: it is a keywork in FE an FL
// - From now on, the prefix "pm#" is ommited: Philippe Martin has been declared as the default creator in this file.
*/
pm#Thing = owl#Thing, //If you are new to FL, see (and compare with) the translation in Formalized English (FE) below
\. p{ (Situation = Perdurant,
\. v_p{ State
(Process \. (Knowledge-representation_related_process = KP))
})
(
Entity
//Use the expansion/contraction symbols to ease the reading
\. p{ (Attribute_or_characteristic_or_dimension_or_measure
\. Logic-or-computational_characteristic )
(Endurant
\. p{ (Spatial_entity = Entity_with_dimension-or-location_in_a_space)
(Non-spatial_endurant
\. (
pm#Thing is pm#equal to owl#Thing and has for `subtype partition´ the set
{ `Situation
which is equal to Perdurant andhas for `viewpoint subtype partition´ the set
{ State,
`Process which has for
subtype `Knowledge-representation_related_process which is pm#equal to KP´
} ´,
`
Entity
which has for `subtype partition´ the set
{ `Attribute_or_characteristic_or_dimension_or_measure which has for
subtype Logic-or-computational_characteristic´,
`Endurant which has for `subtype partition´ the set
{ `Spatial_entity which is pm#equal to Entity_with_dimension-or-location_in_a_space ´,
`Non-spatial_endurant which has for `subtype partition´ the set
{ `
which is pm#equal to Description_object and has for `subtype partition´ the set
{ Description_semantic-content,
`Description_instrument-or-result which is pm#equal toInformation_objectand has for `complete subtype set´ the set
{ `Description_instrument which has for `set of exlusive subtypes´
{ `Language which has for `set of exlusive subtypes´
{ Formal_language, Informal_language } ´,
`Deductive_system which is pm#equal to Proof_system
as well as Formal-logic_system ´,
`Formal_systemwhich has for part at least 1 Formal_language as well as
at least 1 Deductive_system ´
} ´,
`Description_result which is equal toRepresented_informationand has for `viewpoint subtype partition´ the set
{ `Represented_datawhich has for subtype Database´,
`Represented_Knowledgewhich is equal toKnowledge_representation along with KRand has for subtype KB´
} ´
and has for subtype
`Specification which has for `subtype partition´ the set
{ Entity_specification,
`Situation_specification which has for subtype
`Process_specification which has for subtype
`Software_or_software-specification
which has for `subtype partition´ the set
{ Software_specification,
`Software which has for `subtype partition´
{ `Software_for_KPs which has for subtype
^`Software for evaluating logic or computational
characteristics´ and
`Knowledge_management_system
which is equal to KBMS
and has for object at least one KB´,
`Software_not_for_KPs which has for subtype
`Database_management_system which is equal to DBMS
and has for object at least one Database´
} ´
} ´
} ´
} ´
}
´,
`
Description_container
which has for `set of exlusive subtypes´
{ `Database_mamanagement_system which is pm#equal to DBMS
and has for part at least one Represented_data´,
`Knowledge_mamanagement_system which is pm#equal to KBMS
and has for part at least one KR´
} and for `set of exlusive subtypes´
{ File, Memory_area }
´
} ´
} ´
}
´
}.
*/
any Thing //E.g. the situation that pm described (referred to) via: pm#[Tom place: a Mat]
description:
0..* (Description_semantic-content //E.g. what pm thinks that pm#[Tom place: a Mat] refers to
description:
1..* (Description_result //E.g. &(pm#[Tom place: a Mat]) a description by pm of Tom being on a mat
description_instrument:
1..* Description_instrument //E.g. &&(pm#[Tom place: a Mat]), a graph abstract data structure
) ). // and "pm#[Tom place: a Mat]", a string and concrete data structure
/*
In FE:
any Thing //E.g. the situation that pm described (referred to) via: ` `Tom has for place a Mat´ wrt. pm´
may have for description a
`Description_semantic-content //E.g., what pm thinks that ` `Tom has for place a Mat´ wrt. pm´ refers to
which has for description at least one
`Description_result //E.g. &(pm#[Tom place: a Mat]) a description by pm of Tom being on a mat
which has for description_instrument at least one
Description_instrument //E.g. &&(pm#[Tom place: a Mat]), a graph abstract data structure,
´ ´. // and "pm#[Tom place: a Mat]", a string and concrete data structure
any Knowledge-representation_process has for result at least one `KR´ //knowledge representations
and has for `set of exclusive subtypes´
{ `Implementation-or-application_oriented_knowledge-representation_process,
any instance of this type having for result at least one
`Executable_model, any instance of this type having for part at least one KR´ ´,
`Modelization-or-reusability_oriented_knowledge-representation_process
any instance of this type having for result at least one
`Conceptual_model, any instance of this type having for part at least one KR
(and `any `Knowledge_sharing or Knowledge_reuse´ has for input at least one Conceptual_model´)
´ ´
}.
Formal definition (hence, ontology / representation and organization via semantic relations) of
KRL elements for creating KRs (especially for asserting knowledge), e.g.
individuals / types (concept/relation, asserted/generated, contextualized or not, ...)
KRLO is a KR language ontology, which has been begun in 2016, that WebKB-2 will enable Web users to
extend KRLs, and that WebKB-2 will exploit to parse those KRLs.
For more details, see this core ontology and
this article.
1.1.2. KR (Assertion) Languages ("models or notations") Definition/Organization/Extension
A KR language (e.g. "RDF/XML") is
a KR "abstract model" (a collection of particular abstract data structures referring to particular
KR abstract elements, often logical elements; e.g. RDF) and/or
a "concrete models" (notations, e.g. a linearization with the XML notation).
Here is a page for some KR "abstract models" in KRLO.
Figure 1.1.2. “Slightly adapted UML” representation of
some relations between some types of KRL models
and between some types of KRL notations.
Legend:
Each arrow "->" represents a super-type (here, subClassOf) link.
For other links, an arrow "➞" is used with an associated link type and also a
destination cardinality when this cardinality is different from 0..*, i.e. 0–N.
For concision purposes, boxes around classes (types) and associations (links) are not drawn.
Associations are in italics and their cardinalities are not displayed since they are all 0-N in both directions.
Thus, the rightmost lowest has_part association can be read:
“any (version of) RIF-FLD has as part 0 to many (versions of) RIF-BLD, and conversely”.
1.1.3. KR Query/Constraint/Evaluation/... Languages Definition/Organization/Extension
To be flexible/generic and easy-to-implement, a KR query/constraint/... language must
have only one explicit/implicit query/constraint/... operator (e.g. noted "?" for queries)
which takes arguments written with some/any existing KRL ;
the operator may have some variants/options ; for constraints, contexts may be used instead ;
here is an
example for queries,
one for constraints and one
for KB completeness evaluation ;
exploit some/any inference engine that operates the KRL used for the arguments.
In Prolog or Datalog, the query operator is implicit.
When creating SPARQL, the W3C added a lot of arbitrary syntactic sugar and restrictions (and only one
notation was allowed). Similarly, for SHACL (a constraint language) they created a whole new language
instead of reusing OWL, any RDF+OWL notation and any OWL engine.
1.1.4. KR Storage in Input/Documentation/Backup Files, Fully Formal or Not
Module-based (e.g. file-based) knowledge sharing is restricting and leads to many implicit redundancies
and inconsistencies between modules, hence to problem of module selection and reuse.
Only KB servers with edition protocols (within a KB) and KR/query forwarding protocols (between KB servers)
can avoid implicit redundancies and inconsistencies between modules (shared KBs in this case).
Then, files are only useful for KB input/documentation/backup purposes.
For checking and maintenance purposes, these files should be (re-)generated from the KB:
regenerating the content of an input file is a minimal check of the correctness of the
knowledge interpretation and generation processes of a KB server, and ensure that these files can be used
as backup files.
For readability and informal structuration purposes, or for documentation and KR-based data indexing purposes,
it is often very advantageous to be able to mix informal information and KRs in the same document.
WebKB-1 (private KB server) and
WebKB-2 (shared KB server) allow this in HTML files:
i) the parsers they use skip any informal content and, within formal content, skip HTML tags, and
ii) query results can use HTML tags to enhance readability and can include or link to informal information
indexed by KRs in query results.
1.1.5. KR-based Indexation of Document Elements
Simply indexing whole documents by KRs does not significantly improve knowledge retrieval: what is
retrieved is still a list of documents that are likely to be partially redundant and inconsistent with
each other, and there is still a recall/precision ratio problem (in fact, this problem remains when
querying unconnected or poorly connected KBs since they cannot be merged into a unique well-organized KB:
they are mostly just data for each other).
Similarly, simply indexing document elements by KR terms (types or individuals) is too imprecise to
significantly improve knowledge retrieval.
The only solution for a genuine scalable knowledge sharing/retrieval/reuse is, via shared KB servers,
to progressively create a network of (physical) KBs that can be seen as one (virtual) well-organized
KB. This requires very good knowledge normalization and organization methods.
In this global virtual KB, it is worthwhile for KRs to index particular document elements that cannot
be regenerated from these KRs.
1.1.6. ...
1.2. KR Implementation Models (Data Structures, Databases, ...) and
Generic APIs for them
Although they are abstract models, some KRL models like RDF have such low-level peculiarities that they
may also be seen as abstract data types (ADTs).
When a KBMS (KB Management System) is implemented, ADTs or other implementation-dependent tools
must be used to store the implementation models for KRL models, e.g. databases, allocated memory areas
or distant servers.
However, a generic API may also be implemented (and used whenever possible) to hide
implementation details and enable choices between them. This is becoming the case in WebKB-2
(the generic API is a C++ class with virtual methods, specialized by various implementation classes).
Note: the distinctions between KRs and most data structures (ADTs, databases, ...) are two-fold:
Structural: directly or indirectly, graph structures composed of relation nodes and concept nodes (the nodes
related by relation nodes). ADTs (objects, arrays, ...) and databases used for implementing KRs often have
a tree structure (with implicit relations which, unlike relation nodes, are not 1st-order entities).
As an example, the attribute/part relation between an object (or a frame) and its attributes is
known/referable and an attribute is local to an object (i.e., the same attribute name may occur in
different objects while referring to different kinds of attributes).
Semantic (and hence inferential): KRs represent the semantics of what they store (and in ways that enable
logical inferences); this is not the case with data structures (including those for graphs).
There are cases where, for efficiency reasons, particular ADTs are needed for storing particular kinds of KRs,
typically KRs representing spatial relationships between 2D or 3D things (e.g., things in maps or images).
Here is a paragraph about KR-based maps and
an example class to implement them.
1.3. KRs for Programming/Control Structures/Instructions
Section 1.1.1 referred to the representation of instructions and control structures.
Thus, programs (control flow, best practice following, ...) may be represented and then
their design or control flow may be statically: dynamically queried/checked via semantic
queries/constraints/rules (e.g., design best practice, error detection, etc.).
Neural networks and some other objects that support – or are the results of –
machine learning processes are not based on logic deductions but on
inductions/abductions/analogies or probabilistic inferencing.
There are many ways to mix logical and non-logical processes.
Generally speaking, non-logical processes are used by logical ones for hypothesis generation
and communication with people.
1.5. ...
2. Methods/Criteria/Constraints/Rules/Patterns/... for KPs
2.1. Logic/Computational Criteria And Methods to Evaluate/Satisfy Them
Logic-or-computational_characteristic /^ Attribute_or_characteristic_or_dimension_or_measure,
\. c{ //complete, not exclusive
(
Formal-logic-system_characteristic
.[0..1 Formal-logic_system ?ls, 0..1 Property ?p -> ?attr] ?attr
\. (Logical-system_soundness
:=> "In a sound logical system ?ls, every satisfiable theory is consistent
(i.e., does not lead to a logical contradiction),
but the converse only holds if ?ls is complete"
\. (Logical-system_soundness_wrt_a_property
:= "a logical system ?ls is sound with respect to a property
if each of its theorems has that property",
\. (Logical-system_completeness_relative-to-a-property _(Semantical_validity)
= Logical-system_weak_soundness, //Tautologousness
:= "every sentence (well-formed formula) ?s that can be proved in the logical system ?ls
is logically valid wrt. the semantics of ?ls
(i.e, is also true on all interpretations or structures of the semantic theory for
the language ?l upon which ?ls is based): all its theorems are tautologies;
formally: ⊦?ls ?s; → ⊧?ls ?s;",
converse: Logical-system_semantic-completeness, //see below
\. (Logical-system_strong-soundness
:= "any sentence ?s of the language ?l upon which the logical system ?ls is based
that is derivable from a set ?ss of sentences of ?l
is also a logical consequence of ?ss, in the sense that any model that
makes all members of ?ss true will also make ?s true;
formally: ?ss ⊦?ls ?s → ?ss ⊧?ls ?s"
) ) ) )
(Logical-system_completeness
\. (Logical-system_completeness_wrt_a_property
:= "a logical system ?ls is called complete with respect to a particular property ?p
if every formula having the property can be derived using that system,
i.e. is one of its theorems",
\. (Logical-system_completeness_relative-to-a-property _(Semantical_validity)
= Logical-system_semantic-completeness, //Tautologousness
:= "?ls can derive every tautology (i.e., every formula ?s that is true):
all its tautologies are also its theorems; formally: ⊧?ls ?s → ⊦?ls ?s",
//Gödel's completeness theorem establishes semantic completeness for first-order logic
\. (Logical-system_refutation-completeness
:= "for every unsatisfiable set (of formulas) ?ss, the logical system ?ls
is able to derive false; formally: ?ss ⊧?ls ⊥ → ?ss ⊦?ls ⊥"
\. (Logical-system_strong-completeness
:= "for every set of premises ?ss, any formula ?s that semantically follows
from ?ss is derivable from ?ss; formally: ?ss ⊧?ls ?s → ?ss ⊦?ls ?s" ) )
(Logical-system_syntactical-completeness
= Logical-system_deductive-completeness Logical-system_maximal-completeness
Logical-system_negation-completeness,
:= "for each sentence (closed formula) ?s of the language of the
logical system ?ls, either ?s or ¬?s is a theorem of ?ls" ) ) ) )
(Logical-system_computational-characteristic
\. Logical-system_decidability )
)
(
Computational_characteristic
.[0..1 Software_or_software-specification ?ls, 0..1 Property ?p -> ?attr] ?attr
\. ne{ (Complexity-or-decidability-or-termination_related_characteristic
\. Logical-system_decidabilityProgram_terminationComputational_complexity )
(Software_correctness_wrt_a_specification .[0..1 Software, Software_specification ?ss
-> ?attr] ?attr
\= (Software_partial-correctness_wrt_a_specification
:=> "if an answer is returned, it is correct",
\. (Software_total-correctness_wrt_a_specification
:=> "an answer is returned and it is correct" ) ),
\. (Software_functional-correctness_wrt_a_specification
= ^"Software_correctness_wrt_a_specification restricted to inputs and outputs:
for each input, the software must produce an output satisfying the specification" ) )
}
Logic-program_algorithmic-characteristic
)
}.
2.1.1. Computational Termination and Other Properties of Logic Programs
(and hence also: Methods To Evaluate/Satisfy These properties)
2.1.1.1. (Non-)Termination of Logic Programs
2.1.1.2. Properties of Logic Programs Different From Termination
2.1.1.3. Relationships Between Abstract Interpretation and The Proof of Logic Program Properties
2.1.1.4. Relationships Between Proof-By-Resolution and Natural Deduction
2.1.1.5. Translation Of Proofs Into Logic Programs
2.2. Criteria/Constraints/Rules For Knowledge Organization/Sharing
Within a KB (networked or not)
Software_at_least_partially_created_by_at_least_one_member_of_the_LIM_of_the_UR /^ Software,
\. p{ (Software_for_KPs_at_least_partially_created_by_at_least_one_member_of_the_LIM_of_the_UR
/^ Software_for_KPs,
\. (^`Software for evaluating logic or computational characteristics
created_by_at_least_one_member_of_the_LIM_of_the_UR´
/^ ^`Software for evaluating logic or computational characteristics´,
\. ^`The NTI+cTI software ranked 1st at TermComp 2022, 2023´ )
(KBMS_created_by_at_least_one_member_of_the_LIM_of_the_UR /^ KBMS,
\. WebKB-1WebKB-2IKBS )
)
(Software_not_for_KPs_at_least_partially_created_by_at_least_one_member_of_the_LIM_of_the_UR
\. ^`User Interface created_by_at_least_one_member_of_the_LIM_of_the_UR´
)
}.
3.1. User Interfaces
Nowadays, web applications or documents have particular interfaces or presentations that
i. must be predefined (often by a programmer), hence that
ii. are hardly modifiable by the end-user or reader, and that, for this one,
iii. require learning and getting used to each interface and its particularities.
These three problems can be solved through a generic and adaptable interface
(used in addition to or instead of a traditional interface). This implies that
i. the content and/or presentation of each modifiable element (document, menu, etc.)
must be generated from a specification, and that
ii. these specifications can be accessed and modified by each user, via navigation in
contextual menus from each element (hence from each menu element too).
Such menus and interfaces exploit an ontology of Web presentation components (HTML, CSS) and
Javascript functions enabling navigation and modifications of presentation and content.
3.3. Software to Evaluate/Generate Logic Programs Satisfying Some Properties
(see Section 2.1.1)
3.4. ...
4. Applications/Results/Resources
4.1. General Ontologies Not About KPs
The default ontology that WebKB-2 invites its users to extend is
the MSO, a source-preserving integration of several ontologies,
including one derived from WordNet (corrected and transformed into an ontology).
4.2. Domain/Task Ontologies Not About KPs
Many small ontologies have been formalized into WebKB-2.
6. History of How Some Works at LIM Have Been Above Categorized
6.1. Categorization of Some Works of F. Mesnard, E. Payet et T. Marianne
The following text led to the creation of Section 2.1 (before its sibling sections) and its subsections.
Nous (Fred Mesnard, Etienne Payet et Thierry Marianne) étudions divers aspects de la programmation
logique (éventuellement avec contraintes). En particulier, nous nous intéressons :
aux techniques de preuve de terminaison et non-terminaison de programmes logiques ;
aux systèmes de preuves de propriétés de programmes logiques ;
aux liens entre interprétation abstraite et preuve interactive de propriétés de programmes logiques ;
aux liens entre preuve par résolution et déduction naturelle ;
aux techniques de synthèse automatique de programmes logiques à partir de preuves.
Nous nous sommes également penchés sur la génération automatique de tests pour
la programmation logique. Pour chacun de ces points, nous expérimentons avec des outils logiciels.
6.2. ...
7. Restrictions About the Dates of the Above Cited LIM Day
For this day, Fred Mesnard will mainly only be available Week 41 (7-11/10) and 43 (21-25/10),
Tuesday-Friday.
