4 ms·
Note that SHACL is in somewhat more common use these days, and can also be given a logical basis not unlike OWL: https://news.ycombinator.com/item?id=31890041 h
by zozbot234 4y ago
Note that SHACL is in somewhat more common use these days, and can also be given a logical basis not unlike OWL: https://news.ycombinator.com/item?id=31890041 https://news.ycombinator.com/item?id=31890041 Given that both are part of Semantic Web standards, it's a bit surprising that this was not noticed before.
- PaulHoule 4y agoOWL's got the tough problem that it is hard to know what it can do and what it can't do. What documentation there is https://www.w3.org/TR/2012/REC-owl2-direct-semantics-20121211/ https://www.w3.org/TR/2012/REC-owl2-direct-semantics-2012121... tells you how to convert an OWL ontology into a set of first-order logic axioms and presumably an OWL reasoner can do whatever a FOL reasoner could do on those axioms. Compared to other schema and ontology languages, OWL makes it possible to write an ontology in terms of logical definitions. For instance an "OddLotTrade" could be a "Trade" where the quantity is less than 100. The trouble is that OWL can't do math in the sense of "compute the body mass index from a person's height and weight and determine that the person is underweight if the BMI is under a threshold." If you have the BMI precomputed it can do that, but you can't define the BMI itself in OWL. There is a good reason for that which is that FOL + arithmetic is undecidable for reasons Kurt Godel discovered. You can write "logical definitions" in another sense with production rules, for instance you can match the height and weight and add a fact with the BMI, but you lose the ability the OWL reasoner has to validate the ontology as a whole (e.g. if you have an xⁿ+yⁿ=zⁿ kindof rule you wish it would know that it could never be satisfied but that's a very hard proof.) That said, the ability to export OWL to FOL means you can use OWL tools to develop and validate an ontology and then add some beyond-OWL stuff to it to do some reasoning.
- wizeman 4y ago> FOL + arithmetic is undecidable for reasons Kurt Godel discovered. Adding finite arithmetic (i.e. on N-bit words rather than mathematical integers) to FOL should not change the decidability of FOL, or does it?
- a1369209993 4y ago> Adding finite arithmetic [...] should not change the decidability No (unless you can implement arbitrary-precision arithmetic indirectly, which you frequently can), but then you have insane, nonsensical conclusions[0] due to integer overflow. 0: Eg, the mass of the earth (in grams) is less than the mass of the moon (in grams) if you use 64-bit ints - but that's not true of their masses in kilograms or pounds.
- wizeman 4y ago> No To be clear, you're saying that it wouldn't change the decidability, correct? > 0: Eg, the mass of the earth (in grams) is less than the mass of the moon (in grams) if you use 64-bit ints - but that's not true of their masses in kilograms or pounds. Which is why you should have used 256-bit ints for computing that answer ;)
- a1369209993 4y agoAdding (fixed-size) finite arithmetic will not change decidability in principle. In practice it can often be jury-rigged into non-fixed-size arithmetic. Also in practice, anything that requires enumerating all possible values of even a 64-bit integer to decide is bordering on undecidable in practice. > 256-bit ints And now you're well over the border.
- wizeman 4y ago> > 256-bit ints > And now you're well over the border. Here's my plan. I'll wait a few decades until we have sufficiently-large and powerful quantum computers. Those reduce the time complexity from 2^256 to 2^128 just by being capable of performing sufficiently large quantum computations. I will precompute a table for 64-bit integers and store the results. Then for every 256-bit computation of complexity 2^128, I will split the computation in two parts: the first 64 bits of complexity will use raw CPU power to compute, and the last 64 bits will look up the result in the pre-computed table. Easy peasy. Hah! :)
- YeGoblynQueenne 4y ago>> There is a good reason for that which is that FOL + arithmetic is undecidable for reasons Kurt Godel discovered. Undecidability is overrated. We have computers, no? Particularly for FOL undecidability does not mean that every FOL formula is undecidable, it just means that there exist some formulae which are undecidable. There may even be an infinite number of undecidable formulae ... and an infinite number of decidable ones, too. If you think about it, Gödel's proof was the construction of one undecidable formula ("this sentence is false"). His proof followed multiple similar proofs in different contexts all proposed around the same time, in the early 1920's, for example Russel's paradox and all more or less variations of one of Epimeneide's paradox. I don't know if anyone has since produced any more instances of undecidable problems in FOL. If there were an infinity of such undecidable problems (or classes of problems) wouldn't we have stumbled on them a lot more often? Anyway the simple solution to do arithmetic in FOL-based languages is well-known to the logic programming community: constraint logic programming (an idea which I recently learned also came from Alain Colmerauer, creator of Prolog): https://en.wikipedia.org/wiki/Constraint_logic_programming https://en.wikipedia.org/wiki/Constraint_logic_programming https://www.swi-prolog.org/pldoc/man?section=clpfd-arith-constraints https://www.swi-prolog.org/pldoc/man?section=clpfd-arith-con...