{"entities":{"Q5940962":{"pageid":8117764,"ns":120,"title":"Item:Q5940962","lastrevid":97644500,"modified":"2026-06-05T15:09:36Z","type":"item","id":"Q5940962","labels":{"en":{"language":"en","value":"Min-max Computation Tree Logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1635113"}},"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":"Q5940962$89A21DF6-9144-45BB-8EA8-4372B449CCF6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f68d1ab3c5b874610f7d70864436b36b0341b30c","datavalue":{"value":{"text":"Min-max Computation Tree Logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5940962$722A88AA-A3D0-466E-8B4D-693A8D3B920F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"110a12f3f1710eadb57ba503853da3ac9e81c179","datavalue":{"value":"0976.68104","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940962$8391A2F0-A6BE-4432-890C-8C138338B216","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"15a94daa40751617ff3e3725caa7a83f3f447d2e","datavalue":{"value":"10.1016/S0004-3702(01)00059-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940962$4248769B-CAAA-484E-AD9E-2C11A99E627A","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"984e6510ec40a363d20e607cce2cc2f8b07918ae","datavalue":{"value":{"entity-type":"item","numeric-id":72340,"id":"Q72340"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$CFDC5162-4B84-4C8A-8D61-10CD9B656626","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0d780905acb67c2b1b938af03e08b68df411214b","datavalue":{"value":{"time":"+2001-08-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":"Q5940962$0C149F1E-9068-49A6-9DB9-142FB8E185AF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"63761941fdbcb9542eb5e226b5705dc3353f3ce0","datavalue":{"value":"This paper introduces a branching time temporal query language called Min-max CTL which is similar in syntax to the popular temporal logic, CTL [\\textit{E. M. Clarke, E. A. Emerson} and \\textit{A. P. Sistla}, ACM Trans. Program. Lang. Systems 8, 244-263 (1986; Zbl 0591.68027)]. However unlike CTL, Min-max CTL can express timing queries on a timed model. We show that interesting timing queries involving a combination of min and max can be expressed in Min-max CTL. While model checking using most timed temporal logics is PSPACE-complete or harder [\\textit{R. Alur} and \\textit{T. A. Henzinger}, Inf. Comput. 104, No. 1, 35-77 (1993; Zbl 0791.68103); \\textit{A. Alur, C. Courcoubetis} and \\textit{D. Dill}, Inf. Comput. 104, No. 1, 2-34 (1993; Zbl 0783.68076)], we show that many practical timing queries, where we are interested in the worst-case or best-case timings, can be answered in polynomial time by querying the system using Min-max CTL.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940962$A870BE67-69BB-44C6-99E8-85012D00D263","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940962$C114BA5E-4498-414A-8650-83FBEAB868EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"e2244b32b83bf71a9c045223e635ab074452b389","datavalue":{"value":"03B44","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940962$C9A967BB-9BF6-4E8A-BA12-BD58DF360D4F","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"fb01387328e1380b9995b1a1dd981bde5311d97f","datavalue":{"value":"1635113","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940962$859E9C01-8786-4790-951C-ADB565730B22","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2eb4d1af95699ef062cce80ecbcf1e1484586450","datavalue":{"value":"formal verification","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940962$490BD1EC-398C-4584-A34D-3E2EE386C0C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fb9f8004d477a3922fe8bde53d670f8b57c48852","datavalue":{"value":"model checking","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940962$92BF7AF8-2D44-4501-BEC0-53286078A26E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a4a6f11756e1720f07cda5a080ef0476786d909b","datavalue":{"value":"temporal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940962$B458F157-0067-401C-956F-8B89A0B0BAA2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06083a62f9f1207530e3a85b407d2e98bb9afdc0","datavalue":{"value":"timing verification","type":"string"},"datatype":"string"},"type":"statement","id":"Q5940962$654FD283-C3D3-4EA3-8474-04D2BD639C96","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":"Q5940962$3081CD51-641A-46CD-B51D-E49DD4DEC026","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"f3c7f8b3f1ff6940d5ec48ef42f10efe12dcb747","datavalue":{"value":{"entity-type":"item","numeric-id":689093,"id":"Q689093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$580A3BF0-8E02-4B0D-84E5-125B3120A879","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6df3bae9c756efbb8cf10516a99531fddb50833e","datavalue":{"value":{"entity-type":"item","numeric-id":689092,"id":"Q689092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$9E1AF8A3-FE74-4297-B19E-935B23952EEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be00c63685f57348b9e88ace758aea96980b1481","datavalue":{"value":{"entity-type":"item","numeric-id":4299300,"id":"Q4299300"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$8334E331-2785-4FD9-817B-94788BA1C53E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"731fff832e7711198e063399154f72f88c50c123","datavalue":{"value":{"entity-type":"item","numeric-id":3719811,"id":"Q3719811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$8B43F2FC-939A-4AEF-B595-FD903393B508","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11eefd7e7dc86c1755a8db4c6825e6e9fdeb6d39","datavalue":{"value":{"entity-type":"item","numeric-id":3619797,"id":"Q3619797"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$0D768609-36D5-4A96-AED7-6ED7EB49E229","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c1f86e355662baa4d9f9fd9a0faea2fe6a1b817d","datavalue":{"value":{"entity-type":"item","numeric-id":4037378,"id":"Q4037378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$6C9B6771-47EA-409C-8C41-C18AF0BF3BCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cb1ddcd136aa166a56029731024130ebca61ea05","datavalue":{"value":{"entity-type":"item","numeric-id":4946960,"id":"Q4946960"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$3AD3637E-3FC0-411D-9F10-6324CFD46DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"458ab467d1c5397109a383d0e5c939369d06a212","datavalue":{"value":{"entity-type":"item","numeric-id":3221403,"id":"Q3221403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$DA841541-CDFE-418E-96B9-0DBE0618E91E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e42adb00a8973720e1a31b9e204a2d407c533197","datavalue":{"value":"https://doi.org/10.1016/s0004-3702(01)00059-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q5940962$367F54BA-1562-4650-9E66-15D141060133","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"7c611a36b1f404121bb1ede78c2c6cde29497dba","datavalue":{"value":"W1966598143","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940962$8409255A-FFF9-4EB5-8BD4-5569723AB2B3","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"d7e41f80bfe9cc32ca36b799d37e9c29d9b710ce","datavalue":{"value":"Q128132728","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5940962$7B55613A-3E82-475B-B7B8-D43BEB445A0F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c6867ed345a06a38fcda3c647c6bdec4ad7f63de","datavalue":{"value":{"entity-type":"item","numeric-id":1847543,"id":"Q1847543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22d11ebf98793b3ced5fe4f5d8785a9aee4fb4c4","datavalue":{"value":{"amount":"+0.913871","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$05B1310D-BAC9-4C3D-BA81-57A75430C93A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7d3e8acb7f38ff6bc0c7d7739611ad753ded2e91","datavalue":{"value":{"entity-type":"item","numeric-id":3650147,"id":"Q3650147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b7801b15752251e8104caa9646177fcb72d1a097","datavalue":{"value":{"amount":"+0.8880628","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$B651BCA5-F2B4-414F-8F29-B9075ABF8CFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f42496d23b7132781c17a6c0e5a23927c43c54f9","datavalue":{"value":{"entity-type":"item","numeric-id":1761500,"id":"Q1761500"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7602e15a018787c30374a0a70a98019dcb0ab79b","datavalue":{"value":{"amount":"+0.8735086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$FA410AEB-B178-49D7-BF5F-7F57FD13462D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b23c7202107824f09a80ad0ae64a5e238cf7cd8","datavalue":{"value":{"entity-type":"item","numeric-id":3651553,"id":"Q3651553"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7602e15a018787c30374a0a70a98019dcb0ab79b","datavalue":{"value":{"amount":"+0.8735086","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$404DBBB6-0D7B-4085-96D8-954338DB062D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6df8933c9da83f1b006f38dc9ea90049710d7ae9","datavalue":{"value":{"entity-type":"item","numeric-id":4229621,"id":"Q4229621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cca68dbfe089e01fa87c430823de52159c4e5cc0","datavalue":{"value":{"amount":"+0.87085634","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$2D48A533-6CE0-48A5-92E3-ACBF3B79BDF7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3ddb2998ecdaf61e3821797fdbef2259a7543ab7","datavalue":{"value":{"entity-type":"item","numeric-id":5916057,"id":"Q5916057"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74be522cb444ddacc3d8ef1e015f9a6f0d1a1a9f","datavalue":{"value":{"amount":"+0.8604692","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$66DC5D7A-FDC1-41E5-9711-4DE05EDEB298","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6c9ccc0e8e9d8faa2fd77b8d1b34ba24e36b153c","datavalue":{"value":{"entity-type":"item","numeric-id":5890931,"id":"Q5890931"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74be522cb444ddacc3d8ef1e015f9a6f0d1a1a9f","datavalue":{"value":{"amount":"+0.8604692","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$B6E37F34-D577-402E-8C17-9573B652FD06","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"95b7bba3ea135a2152641aacc6dc442092538789","datavalue":{"value":{"entity-type":"item","numeric-id":3057112,"id":"Q3057112"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50ebbc745bb28090b7a7b35f6deebe3bc00ca2cf","datavalue":{"value":{"amount":"+0.8573881","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$F7F68BE2-7436-4BD6-9FC6-8B861B04F43A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"11ff885dc054cf63bdb7a16e597a256ce999f4b7","datavalue":{"value":{"entity-type":"item","numeric-id":3321863,"id":"Q3321863"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a5d8951ef6f7197846f02256054b445de8ae9887","datavalue":{"value":{"amount":"+0.85604227","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$5C7909DB-0D52-4843-8A5D-998685CCE9F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ab2b0e0dfe140e013d76013b6a5951689556d4fe","datavalue":{"value":{"entity-type":"item","numeric-id":4933296,"id":"Q4933296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"63fa3f975058b99d8cf785f022b33fa886e1ed96","datavalue":{"value":{"amount":"+0.85231453","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q5940962$C13CFD38-4BC5-431A-867F-FD5EB420ED5D","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6dc74ace289d4fd30a2ff7eb42f16f953c350db3","datavalue":{"value":{"entity-type":"item","numeric-id":230078,"id":"Q230078"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$85DCD9C3-99EB-4622-B628-9E2EDDCC963A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06e88ac0bd75d2e13952e3076643b78912ad4a51","datavalue":{"value":{"entity-type":"item","numeric-id":334151,"id":"Q334151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$C3C159E0-4C69-4D11-9F5B-030DECCB369B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"79d592124ba84fe2ec516373ec84316af394a2fc","datavalue":{"value":{"entity-type":"item","numeric-id":1847542,"id":"Q1847542"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$9EA4845F-B298-4310-8BB6-95B154E8DD16","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b6752993e2d9c35c8179f010cae2de325123239b","datavalue":{"value":{"entity-type":"item","numeric-id":3547579,"id":"Q3547579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5940962$AB9586E8-1CCA-4B44-8E90-761A46B62EFE","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Min-max Computation Tree Logic","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Min-max_Computation_Tree_Logic"}}}}}