{"entities":{"Q3477958":{"pageid":5499680,"ns":120,"title":"Item:Q3477958","lastrevid":46798455,"modified":"2025-12-25T15:03:31Z","type":"item","id":"Q3477958","labels":{"en":{"language":"en","value":"A Nontrivial Lower Bound for an NP Problem on Automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4147509"}},"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":"Q3477958$F0F5A0FC-87A4-44EF-A3B9-9242431C6010","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"4b392cc3b44888e6da7f20e0ea4587efcfeab70f","datavalue":{"value":{"text":"A Nontrivial Lower Bound for an NP Problem on Automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3477958$CA3DD361-A40B-47CC-B2EF-AE3FE78A53A5","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"19536ee633d5f9d53f6cd4af5cf2357503088166","datavalue":{"value":"0699.68062","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477958$72EC5122-A342-475C-8987-63FBB6DA0848","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c49946238a635e57f271cf89c324ed0c574c2bec","datavalue":{"value":"10.1137/0219028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477958$5C5D2B75-2D78-4DC2-8327-D8CE5A8E86D1","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5dae8f46f54ddef78ce2c5c814dc33261ca054d1","datavalue":{"value":{"entity-type":"item","numeric-id":295629,"id":"Q295629"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3477958$D9505F5D-8970-45BA-83AF-95B64E994997","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"c2a1c45d0f0997786c62faf9f7fcd603424632e8","datavalue":{"value":{"entity-type":"item","numeric-id":84798,"id":"Q84798"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3477958$0F237D65-4665-4427-B13F-681E8F493B13","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"70d2fbf8bcd48a5ca1ac752985098b379d0dbb65","datavalue":{"value":{"time":"+1990-00-00T00:00:00Z","timezone":0,"before":0,"after":0,"precision":9,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q3477958$75EC615F-6114-4A59-B9E6-C878BF1D0B9C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477958$AA719ED8-13F1-4F75-A4CD-68A464B69B31","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477958$E38EC79D-BD9F-44E1-9EEB-B20D00A485C8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3486114868bc29e168e0b2d11d567a28b3eef683","datavalue":{"value":"4147509","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477958$7C071DF5-E299-458D-A728-882167252D00","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"50dc5a1d041f9e444212e60e5236dde69d229f7d","datavalue":{"value":"NP-complete problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477958$ECB92FE1-CA38-47DC-963D-AA86679CE763","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a5314c5330d656c5a3ee6808cfb6f22952d33610","datavalue":{"value":"random access machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477958$6797D093-BE1A-4E08-A831-A6203303E699","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6446e76d22cec3c5238cddcadbd8eb9cc724852f","datavalue":{"value":"linear time reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477958$0ECC9920-86D9-49D9-9256-38262C663075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ef283e9003e2d4c6cbb7e24b9f000f92cbde853a","datavalue":{"value":"reduction of automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477958$FA3287A9-2C29-4E1F-8D6C-67D40602E8BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"709c0f1970b625c924543cd42f8a54c7ce976554","datavalue":{"value":"Turing machine","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477958$8F7C626A-28CE-4EFE-8121-473FFDBA2A38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1470c8bfaad834349d763a58fa4883455e5d1c7c","datavalue":{"value":"Incompletely Specified Automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477958$E6C0DFB1-3A72-4FE7-8AC1-AD0C7B17A6D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88b401355e6a0406716503b022caed7c26684edd","datavalue":{"value":"spectrum of a first-order sentence","type":"string"},"datatype":"string"},"type":"statement","id":"Q3477958$20E1A5C6-09E5-4060-87B0-73487C18D8E5","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":"Q3477958$6746F897-7DEA-4DE4-A52E-3D478C363D99","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"b748fc6fa2f7695a4f157b923dfdc836e6f4e77f","datavalue":{"value":"https://doi.org/10.1137/0219028","type":"string"},"datatype":"url"},"type":"statement","id":"Q3477958$C7B7E847-5594-48DF-96B6-8462B4FFD3F0","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0f76db447298bf3bc2c88c9ea991d6ec717b8f41","datavalue":{"value":"W2082154422","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3477958$3BE4A612-68A0-422C-BAC1-15C253F93FBD","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5154052ed4fb4dc326497bbd8a4fca08b1f157e","datavalue":{"value":{"entity-type":"item","numeric-id":671381,"id":"Q671381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32c6093563d2295c3836fbab1873e7286c7b394f","datavalue":{"value":{"amount":"+0.91119015","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":"Q3477958$3A2FE8DA-A7BA-4517-8788-E794A656626C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"849b290a468cad3e054403746b415b34c09bc22f","datavalue":{"value":{"entity-type":"item","numeric-id":5739002,"id":"Q5739002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f910de8d489db323cf3d9b2d19b0e3f74c01baf9","datavalue":{"value":{"amount":"+0.90344715","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":"Q3477958$28398BE1-D61F-4D74-A5AD-312E457A39CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8ea58bca280278e1ef929a5ebe56bbdeea054a12","datavalue":{"value":{"entity-type":"item","numeric-id":2720406,"id":"Q2720406"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0c23611d193971c37b2faee967c3a417111ffb50","datavalue":{"value":{"amount":"+0.87645304","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":"Q3477958$3D75EE1F-E5AE-4B05-B62E-6A7112CD4F2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"913994db7c6797fdc8751840d11261d54146992e","datavalue":{"value":{"entity-type":"item","numeric-id":955341,"id":"Q955341"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d5c7c740b281180f27a14b32786f1e64b2900998","datavalue":{"value":{"amount":"+0.87517357","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":"Q3477958$3EB77B19-E113-4A01-8C2B-ABFBA281BE61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2601df53cdb120e5c1aa1427a425ec0fe0e545cc","datavalue":{"value":{"entity-type":"item","numeric-id":3532998,"id":"Q3532998"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e7996c838afb4d5a98bc73f5f4316a11410cc225","datavalue":{"value":{"amount":"+0.8749889","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":"Q3477958$7133D18B-2F08-4404-8327-A61F4680F6C3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"699ca55f22acfad3d87663a2844e5923b9e8af54","datavalue":{"value":{"entity-type":"item","numeric-id":5002825,"id":"Q5002825"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"951c7f03d92881e7cb3271c0f744ad55a354360f","datavalue":{"value":{"amount":"+0.87385774","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":"Q3477958$79D80310-BBC2-461F-AFDE-38684BCCD987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b5e4c30941cdaaf3695d5f9b31b7c208795fbf4","datavalue":{"value":{"entity-type":"item","numeric-id":3196391,"id":"Q3196391"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f5db31c6462cedcbde248077a938872f7d524a35","datavalue":{"value":{"amount":"+0.87090635","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":"Q3477958$31FBF6AD-0227-4C61-9327-B160E757C3E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebfc322ddee1d45653c575f2af78d677f8a03db6","datavalue":{"value":{"entity-type":"item","numeric-id":3501399,"id":"Q3501399"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eeb05e6246dbb0704e688c3087110d7bb40a59b6","datavalue":{"value":{"amount":"+0.8685057","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":"Q3477958$C247CF8E-A3DC-49C6-ABF5-F4D1E230E08D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a5f4cbebd32cc301b8580605a6781f95535c2839","datavalue":{"value":{"entity-type":"item","numeric-id":553328,"id":"Q553328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"eaa4a76138373cfdfa4f54423bdac7bcc6250bbb","datavalue":{"value":{"amount":"+0.8681004","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":"Q3477958$24D3488F-29B0-4086-B375-57A54F36ABFD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f298ad9da5b44b8a210dde912ee2df7d96554e90","datavalue":{"value":{"entity-type":"item","numeric-id":3748273,"id":"Q3748273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5dc89d8e52cb82900ec184340193c9253a4a99c1","datavalue":{"value":{"amount":"+0.86800617","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":"Q3477958$2C6452AD-A71C-46E6-8AF2-6AF9525E9214","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3477958","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3477958"}}}}}