{"entities":{"Q4242583":{"pageid":6272184,"ns":120,"title":"Item:Q4242583","lastrevid":108441368,"modified":"2026-11-06T12:02:25Z","type":"item","id":"Q4242583","labels":{"en":{"language":"en","value":"Augmenting branching temporal logics with existential quantification over atomic propositions"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1286042"}},"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":"Q4242583$0DFDD9E6-4770-4ED0-AB35-FD4EF5F1864D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c5cfb1566ad02a1e4654fd081a8d9e16f7df707","datavalue":{"value":{"text":"Augmenting branching temporal logics with existential quantification over atomic propositions","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q4242583$7CE10E14-3838-40D7-92F3-8ADAFE64C421","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"07439ab104510549d34c6e9a3b91e83394010b02","datavalue":{"value":"0942.68072","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4242583$89CFAF44-757A-4F2F-92E4-42F1C2AB4AD9","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3315bf391c0a058853db1fdd065cc2cb8ff023ce","datavalue":{"value":{"entity-type":"item","numeric-id":216121,"id":"Q216121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4242583$0FA385A8-E2D7-43C5-B240-2BC6B4C939D4","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"641f83e1b8c9394b4305abfb8491fe0a448b416c","datavalue":{"value":{"time":"+1999-06-20T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q4242583$146385FE-2909-4A58-AD6B-13C5274C0578","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4242583$11720286-0631-4167-9A4C-E6E86BD4ADCA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e2244b32b83bf71a9c045223e635ab074452b389","datavalue":{"value":"03B44","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4242583$12B26BAA-8D0B-457B-AB15-4D8B44F8199B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8195a9e26c453276e1d31339bf2413392412013d","datavalue":{"value":"68Q17","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4242583$5E27879C-E96D-4F60-BA5A-5E9CAFBED72D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"edfee002eb644ecbc2a45e0d5cc285787faa2c3b","datavalue":{"value":"1286042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4242583$B9A01CB2-76A8-44C2-ACF4-FE1EB21E0C9D","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c8325b19a9709030932dad486052e4e0093ba153","datavalue":{"value":"branching temporal logics","type":"string"},"datatype":"string"},"type":"statement","id":"Q4242583$EA0ECC7F-0B61-4515-A44D-BFC2CAD969D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb9f8004d477a3922fe8bde53d670f8b57c48852","datavalue":{"value":"model checking","type":"string"},"datatype":"string"},"type":"statement","id":"Q4242583$A022BD62-C595-4FE6-823E-E68FB66ED7A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c5f8382ba04f9f05f645b4d0e4b9ea28f0619583","datavalue":{"value":"complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4242583$3A75D0BB-B08E-4332-A5AB-829A1F6821B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"afed029624869c3f1cd911322ad6ae398a5fce78","datavalue":{"value":"program complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q4242583$177E6867-393D-43DD-8515-361495048E81","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":"Q4242583$62323F26-2B06-4559-A47B-3AA72AAA77AC","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e2d78d1681c02700416e0edc4e30fd16ac0c11bc","datavalue":{"value":"https://doi.org/10.1093/logcom/9.2.135","type":"string"},"datatype":"url"},"type":"statement","id":"Q4242583$DDC9BFCE-18E2-4A74-BD93-65981D5C4DB5","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2eff276ae8a7a8da67dc49b111714e2707bb2ad9","datavalue":{"value":"W2082808848","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4242583$8F5599C7-5D58-42F2-8B53-2D0C599E327E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0794e013e6fcd10905b04c69fa6c2c4afe2fe0ba","datavalue":{"value":"10.1093/LOGCOM/9.2.135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q4242583$C8E4F0D4-A18C-47BB-B2E4-B0FE36DE994D","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"9e6aedf3faf6964e0bbb1663882629f007284aa9","datavalue":{"value":{"entity-type":"item","numeric-id":2983390,"id":"Q2983390"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q4242583$3C6760EC-2D1E-46DB-94A7-95E3563E195A","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"47a692f977b2b5a6577b9e26d31d979c09bb8c82","datavalue":{"value":{"entity-type":"item","numeric-id":5311048,"id":"Q5311048"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cb3260376bf443ee924e0df14324c147e40b7f18","datavalue":{"value":{"amount":"+0.8320802450180054","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":"Q4242583$8F0311F5-464A-43B6-A7D5-426831FA9FF4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b368a560c3ed3ed70188dfe1eb32036b8e65fbd2","datavalue":{"value":{"entity-type":"item","numeric-id":2771058,"id":"Q2771058"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c96f224f70d83e3002c066052eb153d4d758065","datavalue":{"value":{"amount":"+0.8180211186408997","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":"Q4242583$D9FFDA87-162C-4325-B92D-A2EEBD0AE627","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"791ff92a215bb66d971a2775ffed0ebf24a772f4","datavalue":{"value":{"entity-type":"item","numeric-id":1917081,"id":"Q1917081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0559e38af5b774b259018bd9fec88fc7ed4dcdd","datavalue":{"value":{"amount":"+0.8081324100494385","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":"Q4242583$30792142-2644-46CC-994C-3A5672C06E8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0913a62d4a4cad9c6e300c9e86267156ced39ac5","datavalue":{"value":{"entity-type":"item","numeric-id":4508400,"id":"Q4508400"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e8fb5f4d6e69afe13845defb152f5dda4c0e7ad8","datavalue":{"value":{"amount":"+0.8052714467048645","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":"Q4242583$0A6AC113-69AB-412D-B26B-D103A3D83F25","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3c9a4a91c151ece8d6f06cabc0545d8cf72e2840","datavalue":{"value":"Temporal-logic model checking is used in verification of program correctness. The complexity of model-checking algorithms on finite propositional Kripke structures was established previously, in particular for the temporal logics CTL and CTL*. The author explores the relevant complexities when we enrich CTL and CTL* by existential quantification over atomic propositions. By this enrichment, the structure semantics and the (unfolded) computation tree semantics differ. This yields four cases to examine. Besides the complexity of the model checking problem (where the instance is a finite-state program and a formula), the author also studies, in each of the four cases, the so-called program complexity (when the formula is fixed). Therefore the paper contains eight complexity results, varying from P-completeness to 2EXPTIME-completeness.","type":"string"},"datatype":"string"},"type":"statement","id":"Q4242583$77620B67-A8C5-4905-BE2D-3C246EB95163","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Augmenting branching temporal logics with existential quantification over atomic propositions","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Augmenting_branching_temporal_logics_with_existential_quantification_over_atomic_propositions"}}}}}