{"entities":{"Q4500376":{"pageid":6529969,"ns":120,"title":"Item:Q4500376","lastrevid":108632732,"modified":"2026-11-09T13:21:15Z","type":"item","id":"Q4500376","labels":{},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1501629"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4500376$133EE893-23F4-43B3-814E-0832ABFE5AE8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"848c0caac1136a7bfabfeaa340752cea4441f373","datavalue":{"value":"0961.68024","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4500376$35244204-521F-4313-A8FB-B089214675FC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"71f937babc345aca7a341434b23c60d034c4634e","datavalue":{"value":{"entity-type":"item","numeric-id":229744,"id":"Q229744"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4500376$7918FD16-690D-406F-B236-CDF9D8B91804","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"751594203bc637c9523539b1699de34093fb9590","datavalue":{"value":{"time":"+2001-01-11T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4500376$BB838E6E-DD7D-4537-BD3E-994EB971CB7F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b492f281b8f52c724f2bc547e7e570cccf4bd5e0","datavalue":{"value":"68N17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4500376$B862364B-CC8C-4C42-A071-4A4A1B862E30","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d7fdf203358763024e8dd997417f97e108c34b3e","datavalue":{"value":"1501629","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4500376$4DADBBF0-2B37-42D5-89DC-723C8EDD98B8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f1dda010537b7b36bd45151721146f720815706e","datavalue":{"value":"modal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q4500376$9E7CE7A8-5C71-4858-BDF0-6E0476A87872","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e2e80a7123e4ea6d0418cb24d37b1837f13e3514","datavalue":{"value":"first-order logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q4500376$CF03EC56-1AE4-4B30-9D22-42B0FC438A4C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6da4b3b17a9c9f1f96d899cec70ac99b3e5443e9","datavalue":{"value":"modal logic programming","type":"string"},"datatype":"string"},"type":"statement","id":"Q4500376$A7986553-C0B1-40F0-B27E-A4AAA4F26AF9","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4500376$F9DEA170-C927-4A76-9C3B-74A25E64E069","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f9e42ba31e9a4e2566b7e863ec89ebb5ce5c8f74","datavalue":{"value":{"entity-type":"item","numeric-id":5460207,"id":"Q5460207"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd34b39c8a3456d628445b04cbdc2787521324f0","datavalue":{"value":{"amount":"+0.7905750870704651","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4500376$46A898C0-19E1-41CA-940C-1D236A7FFB3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e1d1196886ec419cb266613345ab37f74b3286fe","datavalue":{"value":{"entity-type":"item","numeric-id":3509063,"id":"Q3509063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8d1ddc02761f017ad73dc33c912d3ac1932dce8","datavalue":{"value":{"amount":"+0.7854474782943726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4500376$087C5E8E-BB2C-49A2-95B4-DD87529E85B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a55e94f6099ffc982216ba04842319b5e4c428b4","datavalue":{"value":{"entity-type":"item","numeric-id":4454845,"id":"Q4454845"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"27e66ee308aa2b7f409173a631dcf1c935e9af7e","datavalue":{"value":{"amount":"+0.7828617095947266","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4500376$14AB02E0-6B5D-44B6-9592-1A7FDE7CD911","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"32da014e27af5b8721b1d32334147627c3a21ba3","datavalue":{"value":{"entity-type":"item","numeric-id":5483012,"id":"Q5483012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"961ffade58a549ce9b339bd394295d968a1c2d40","datavalue":{"value":{"amount":"+0.7765005826950073","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4500376$19C387C9-309E-4DAD-B4CB-5DEFA1F12D10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9953939d905374d9fce2b02b69e4489f8df1fb2","datavalue":{"value":{"entity-type":"item","numeric-id":2762271,"id":"Q2762271"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3c3f7dcf50b9fb676ad41295633db29ab0994929","datavalue":{"value":{"amount":"+0.7639651298522949","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q4500376$97426AEB-C226-4386-A863-C15613CBC658","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e1adc702a5fdcf5248e32caa6c68c9ddb64070dd","datavalue":{"value":"Modal logic, as an extension of the First Order Logic (FOL), is used to express concepts concerned with possibility, necessity, belief, temporal progression, etc. Logic programming attempts to use a part of the FOL syntax as a programming language and has achieved certain success in practice, via such language as Prolog. Modal logic programming tries to do the same, but is clearly not as successful. A classical result in theoretical programming is that for every positive logic program, namely, a collection of Horn clauses, there exists the least (Herbrand) model, which can be constructed in PTIME. This paper generalizes the above result to the class of positive modal logic programs. More specifically, it is proved in this paper that for any such program, \\(P\\), of size \\(n\\) in a modal logic \\(L\\in \\{KD, T, KDB, B,KD4, S4, KD5,KD45, S5\\}\\), there exists the least \\(L\\)-model for \\(P\\), via a usual model extension order. Moreover, if \\(L\\in \\{KD5, KD45, S5\\}\\), or \\(L\\in \\{KD, T, KDB, B\\}\\) and the modal depth of \\(P\\) is finitely bounded, then the least \\(L\\)-model can be algorithmically constructed in PTIME and coded in PSPACE. It is also proved that any such program \\(P\\) for \\(L\\in \\{KB, K4, K45, KB5\\}\\) can be characterized by one or two models, in the sense that a positive formula follows from \\(P\\) iff it is satisfied in all these characterizing models. Finally, if \\(L\\in \\{K5, K45, KB5\\}\\), or \\(L\\) is \\(KB\\) and the modal depth of \\(P\\) is finitely bounded, then the models can be algorithmically constructed in PTIME and coded in PSPACE. This paper also contains some complexity results: Besides providing a different proof for the result that the satisfiability problem for Horn formulae in \\(\\{K5, KD5, T,K45, KD45, KB5, S5\\}\\) is decidable in PTIME, it is proved that the satisfiability problem for Horn formulae, with finitely bounded modal depth in \\(\\{KD, T, KB, KDB, B\\}\\) is also decidable in PTIME. In achieving various results, this paper follows the traditional path of deriving finite models, which has long been recognized as the main technique to establish decidability (satisfiability), both in classic and modal logic. (For a much more thorough presentation, and discussion, of issues related to computability and complexity in general modal logic, together with various model construction techniques, readers are referred to [\\textit{P. Blackburn}, \\textit{M. de Rijke} and \\textit{Y. Venema}, Modal Logic (Cambridge University Press. Forthcoming), Chapter 6].) Nevertheless, some of the model construction techniques as reflected in various construction algorithms might be useful to prove similar results in the field. Following the flow in logic programming, an immediate question is how to generalize these results achieved in this paper to normal modal programming, i.e., those containing negative literals in their clausal bodies. Finally, from a practical point of view, although the author cites solving querying problem in modal deductive database as one of the possible application of these results obtained in this paper, I really doubt it will become reality, considering the involved computational, and conceptual, complexity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4500376$19D9D28D-C4E7-491C-930C-A4A4E11AFA5A","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:4500376","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:4500376"}}}}}