{"entities":{"Q2366686":{"pageid":2377429,"ns":120,"title":"Item:Q2366686","lastrevid":46351830,"modified":"2025-12-24T15:10:54Z","type":"item","id":"Q2366686","labels":{"en":{"language":"en","value":"On the expressive power of temporal logic"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 227331"}},"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":"Q2366686$9A1601CF-AB5D-4CF5-B86D-10F4E4C988C7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"afc9bf2b0361915d3c3ace473d4b2d0c679f7b4c","datavalue":{"value":{"text":"On the expressive power of temporal logic","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2366686$6AB661C2-6185-459E-BE8A-A585F5A937FB","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2ffc7bbad507334e4c7da217f86a3ab1fc7a4383","datavalue":{"value":"0784.03014","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$461E73D7-BC6C-491C-A47F-2E0FF0B74E08","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d8a066da2f58e28abfa242ea2f2bb994782ea7ce","datavalue":{"value":"10.1016/0022-0000(93)90005-H","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$898B7362-D0CF-4162-B347-8A5E33226F34","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"803c62cdb8922d3e350fdeeb28e26167b0dfd05b","datavalue":{"value":{"entity-type":"item","numeric-id":2366685,"id":"Q2366685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$6988677B-3ABC-49FA-855E-771CED1703B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"cd7534d49be8f15cc7d26daeab10531db6ccc7a7","datavalue":{"value":{"entity-type":"item","numeric-id":213071,"id":"Q213071"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$6D000240-3AD9-4F32-B5E6-770B42BA62C7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f6749bcdead989847e012c6d63fa055fe98296ad","datavalue":{"value":{"entity-type":"item","numeric-id":230066,"id":"Q230066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$8498D4C0-6FE9-4A8E-B043-6E5F9B242051","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"3340243f57e05f2265c56423c388055a14b114fa","datavalue":{"value":{"entity-type":"item","numeric-id":107189,"id":"Q107189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$2A7CFAF7-D85A-43FF-B7A6-921E35B2BA9C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"3ed735b2a3fb0b444d70f4eac102ee82cf6f12a1","datavalue":{"value":{"time":"+1993-08-18T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2366686$1B3AAE61-79A3-4346-BF6A-278607CBC046","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"2485fabad2d5cb1671d11a59f17082866cf2ed82","datavalue":{"value":"The expressive powers of propositional linear temporal logic (PTL) and of a restriction of temporal logic (RTL), obtained by considering only the operators ``next'' and ``eventually'', are studied. Temporal logics are interpreted on finite words, i.e., a temporal logic formula defines a set of words and the problem is to determine which formal language can be specified in this way. The transparent proof of the fact that a formal language is expressible in PTL if and only if its syntactic semigroup is finite and aperiodic is presented. This gives an effective algorithm to decide whether a given rational language is expressible. The main result of the paper states a similar condition for RTL. A language is RTL expressible if and only if its syntactic semigroup is finite and it satisfies a certain simple algebraic condition. This leads to a polynomial algorithm to check whether the formal language accepted by an \\(n\\)-state deterministic automaton is RTL-expressible. Also, another (non- effective) description of RTL-definable languages is given: these form the smallest Boolean algebra of formal languages containing the language \\(aA^*\\) and closed under the operations \\(L\\to aL\\) and \\(L\\to A^* L\\) for every letter \\(a\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$EBD21F42-AA20-490E-B877-A2D7B054D4D9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"74a6cec96241e450625296e63e8dd539239d7104","datavalue":{"value":"03B45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$A25E2DD0-D42C-4681-8172-0FFCF1A47728","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$E39F2168-2E58-46B6-9245-54B4A495CB29","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"35bbdcbda53152c249a7f99650e19b5ef62999f2","datavalue":{"value":"68Q10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$8865AA37-D708-443A-9B68-FD9F1649BFD9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"7cfff2e3b7f009b69ae82e4aa296ae1902bd02ff","datavalue":{"value":"68Q60","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$A5D331C7-89ED-4000-AFDA-555799BEBC4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"c270fb88a62fde738bd530246c5ba57a005a4efd","datavalue":{"value":"03D05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$17C8F037-B20B-4601-A0B8-B871A59C9796","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"02baa413858d842be44771e24eb83e601447cbac","datavalue":{"value":"227331","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$C72DA4B6-4308-41AB-A12E-FE1344C69FEE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7f688d80cd10dc9c0b004843c0674655ad59b2fb","datavalue":{"value":"linear logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$2984FAFC-6504-4CFD-9B11-89EA0BFA6C95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ceda7008fe09fdf28806f1d5cdbb9e84182a0456","datavalue":{"value":"propositional linear temporal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$FFFD0C1D-DBBE-48E5-84AE-21CC44A97951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"56fbe76f0caeba167ccf7bb257359899dccafc2b","datavalue":{"value":"restriction of temporal logic","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$98684DEF-01B2-4947-8126-0C03BA887E36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f81406898349e4c73610116261aaccda50fa702","datavalue":{"value":"formal language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$7F4FEAE5-96F4-49BC-A99F-E4A0BCCBDE54","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8bdb0313b5df46932abb16144ea5fad2c913d01b","datavalue":{"value":"syntactic semigroup","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$DE019ADE-46F5-415B-AD1D-E3834FB3E78F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"01588185e6a0ea452aabe243e9d0ed340c301288","datavalue":{"value":"rational language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$595E083E-60A4-413A-B23B-98601D4F3D20","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"207f10c4b49e7a8185ccd53556264d79bbc60a2d","datavalue":{"value":"deterministic automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q2366686$7BEECC2B-8DFC-4F6F-8C42-EDED8F58E652","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"773908fafc294c05eb3467ec5d713b5469e8b7b3","datavalue":{"value":{"entity-type":"item","numeric-id":590927,"id":"Q590927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$6ED2F244-F3AE-4FEB-9F9C-FB86F43A4931","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":"Q2366686$8ED70825-6DBA-4355-9C78-E688B128B1C7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"69d90cc4fbc5f5010b872b4415e8fd3d87ac5522","datavalue":{"value":{"entity-type":"item","numeric-id":809608,"id":"Q809608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$1E480E36-A42E-4BCF-AE2B-BEA870FE1D39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f2716451e75e131a2b07c55da6f5e535035caf72","datavalue":{"value":{"entity-type":"item","numeric-id":2546343,"id":"Q2546343"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$4124FA5D-D027-4918-9B41-2DC6D87BEEBA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"daa28b36f1d47ef725ba4acb380f1839600a6b45","datavalue":{"value":{"entity-type":"item","numeric-id":4132170,"id":"Q4132170"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$0F740C8C-2C03-4B01-8D1F-7D6981DF025A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cd56f820547becaf1640ba57e415b67b2dccf11","datavalue":{"value":{"entity-type":"item","numeric-id":3766825,"id":"Q3766825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$0A86A8FE-8F1A-41FD-91CD-C5D5DA9673CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"afe18fdfb882c799d34a7482b763d96a45625e71","datavalue":{"value":{"entity-type":"item","numeric-id":3853827,"id":"Q3853827"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$B127DA1A-4100-4AC9-BC7B-9994E7481C33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ac56484821fb9e3cfb27d78979d101fe32a191a1","datavalue":{"value":{"entity-type":"item","numeric-id":5631023,"id":"Q5631023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$92B5A3E6-B52E-4E3C-B862-EC05FD6F20BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e2dd225cb7a1f1b5d01838e5961bac1df864370d","datavalue":{"value":{"entity-type":"item","numeric-id":5641083,"id":"Q5641083"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$80199F41-0F6D-4DB6-BBCA-225E250127D3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89a21c74e359251764374c0019e3cd7c965b9167","datavalue":{"value":{"entity-type":"item","numeric-id":3767334,"id":"Q3767334"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$4BA7568E-B950-481C-AE78-ED3760A02A8D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38f57872b55df963de6c9939d692ed2ca987da0a","datavalue":{"value":{"entity-type":"item","numeric-id":1088982,"id":"Q1088982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$1B23EFB4-6A5B-4A69-97DA-1C2586A53756","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"983c6d361b39a1c2df39031e508b7ae6b374912a","datavalue":{"value":{"entity-type":"item","numeric-id":4385527,"id":"Q4385527"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$69C8BD18-02F5-41F1-B8C7-ED4EE6A28A5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed68160731cf55d219ba94647825683328472c30","datavalue":{"value":{"entity-type":"item","numeric-id":3769981,"id":"Q3769981"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$DF33740C-2BF2-4E75-B6D3-1883F2BE3F2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98554b277242125c67fbb359aa4c54ca22c25d4c","datavalue":{"value":{"entity-type":"item","numeric-id":5339335,"id":"Q5339335"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$6CE4AD71-4AB7-4368-B275-F1CE927B3F08","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"858af5de7e93ef8dc1b75b5073ab869dd54013e3","datavalue":{"value":{"entity-type":"item","numeric-id":3740247,"id":"Q3740247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$25349AF4-F1F0-4706-9CE6-8098FCD8AF05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7ad71e0c47b486677961310ebe80bdd31a6c3125","datavalue":{"value":{"entity-type":"item","numeric-id":2266068,"id":"Q2266068"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$51B17D9E-B7C7-478C-9B01-5B439BE5E954","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36f5833550e269623349e512f5f9ffd53bbcd5fc","datavalue":{"value":{"entity-type":"item","numeric-id":4385515,"id":"Q4385515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2366686$0535E73B-EFA1-4127-8DC7-BAE97F9EBDF9","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"922297357783cade797765b53d5a3a82ca797fab","datavalue":{"value":"https://doi.org/10.1016/0022-0000(93)90005-h","type":"string"},"datatype":"url"},"type":"statement","id":"Q2366686$5AA57626-452F-4F6E-A4EE-425C53D68AC8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"979eae90042e5a4926b557733a1c9730cc01c003","datavalue":{"value":"W2052706627","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2366686$24173801-8B70-4753-9E25-D26C14387B22","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"79cf21de47ba6ff03a897d8cd84e6e2d168de4f8","datavalue":{"value":{"entity-type":"item","numeric-id":4503155,"id":"Q4503155"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7efb7ca24a4a245e2ea75e2d66449c809ac405ea","datavalue":{"value":{"amount":"+0.853523850440979","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":"Q2366686$139C7E57-F9EA-4639-A7C6-5473A275A21B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"243a61169595355e418736f096741a43e3b14394","datavalue":{"value":{"entity-type":"item","numeric-id":3752371,"id":"Q3752371"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13d0b0a0f5382a54ca8fde91f9f6cc1065b297b2","datavalue":{"value":{"amount":"+0.8347588181495667","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":"Q2366686$BEFD8F2F-BB7B-435C-B214-15AA4B4B80C8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8598f1843ab4781c8f5a3dbac4e6ceffefb55c67","datavalue":{"value":{"entity-type":"item","numeric-id":3317085,"id":"Q3317085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d253596d9eb6664b393996bba8340df52392683","datavalue":{"value":{"amount":"+0.8304004669189453","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":"Q2366686$53836394-F4A4-4353-94AC-D2F1F42F617A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7c407890860efae23b3223165cac9e39a7f1c330","datavalue":{"value":{"entity-type":"item","numeric-id":3525092,"id":"Q3525092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"feccf1b3a4182ebae78b57bdca4298f802109a4b","datavalue":{"value":{"amount":"+0.8287758231163025","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":"Q2366686$EC5AA510-10BA-4EBF-ABB1-26BE63487099","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2366686","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2366686"}}}}}