{"entities":{"Q3495661":{"pageid":5525561,"ns":120,"title":"Item:Q3495661","lastrevid":49425499,"modified":"2026-01-07T03:29:47Z","type":"item","id":"Q3495661","labels":{"en":{"language":"en","value":"A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4170118"}},"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":"Q3495661$BE4619F8-EDBB-403C-B354-AD0CF5FEF5BA","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fad2c6dda95ce6746bdafcad87d8c2b2ca86b17c","datavalue":{"value":{"text":"A Time Complexity Gap for Two-Way Probabilistic Finite-State Automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q3495661$149938E5-320B-43DC-B269-CF68E740422C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ad577319ca0a2aa280ec0c2c28d14eea06bcec16","datavalue":{"value":"0711.68075","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3495661$7DA428A6-0E0D-4100-907A-63CB2CFAC778","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"84fbf4ee8f79160ed32856b527bb5af7a952cfff","datavalue":{"value":"10.1137/0219069","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3495661$77537B31-55B6-4903-8EBD-658E8FE3D1F4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"1d320114f93a10cd6e9e2fb47fde637153845b4a","datavalue":{"value":{"entity-type":"item","numeric-id":757013,"id":"Q757013"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3495661$76523A38-AD1D-4386-B8DA-117E6F008191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"355a32c186d9586aa82df09b9eb223d278a9aacd","datavalue":{"value":{"entity-type":"item","numeric-id":1134519,"id":"Q1134519"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q3495661$325DD5AB-387F-453D-A6BB-8C76E4DBCEA0","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":"Q3495661$0578B767-E4BA-444C-8493-EE51B5D714F4","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":"Q3495661$6862B40A-EC5D-4097-808A-57B15BE2C04D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"88c54853a3a42b77970be1b82fba1c68fe1f6406","datavalue":{"value":"https://semanticscholar.org/paper/f4157a37ad43afc8f9d88a37e5e6e1ef63a8a8d9","type":"string"},"datatype":"url"},"type":"statement","id":"Q3495661$6E77325D-5F4C-4E46-9A98-A23A0129779C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3495661$65B1F79F-7727-4F87-9E3F-E84CD3A93DEF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3495661$F0CE8F81-13CA-4154-8EA2-CF72170A4D57","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"05c4a0d0f15e925c439965215a1e353d8899ede0","datavalue":{"value":"4170118","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3495661$962D1F4E-2343-4FF3-9D22-D214732D2BBE","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2d28ab0532863d1fdfbdcc9d6c397ce2e2a173c1","datavalue":{"value":"probabilistic automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q3495661$2DF3EAEF-40D2-492F-9ABA-3C8F1528BA76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"11acd2fb6ad6c566c252aa4b6fd795400412f6ca","datavalue":{"value":"complexity theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q3495661$307D3DBA-8734-4CF4-9E2F-166F2E54777E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f96ab68362ecc7785c310a8bc5d1601c40b4b65","datavalue":{"value":"finite-state automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q3495661$6A559BF1-CDA2-463E-8A97-D0C31757A994","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3a3410c5f0df3fc1d98f0819e067b85a3f6a029a","datavalue":{"value":"nonregular language","type":"string"},"datatype":"string"},"type":"statement","id":"Q3495661$1E5FBB31-DB5F-4814-99E4-B0BDF8561853","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"29907e15350a9593e575891f28d16a2ef25b8629","datavalue":{"value":"nondeterministic finite-state automaton","type":"string"},"datatype":"string"},"type":"statement","id":"Q3495661$AE6F1423-B679-4406-A510-AA85D2466A0C","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"fc561adb930c94eb89a8630f21839ff3f61fef3f","datavalue":{"value":"Q59595164","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3495661$DF66135A-6F32-4A37-88E4-D86B44C186B8","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":"Q3495661$D0D31B45-DC27-4D7D-AE06-F0A0C6C77A94","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"8f80a7dfc5e98a78a80d7031e34308d29064a080","datavalue":{"value":"W1987322712","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q3495661$A9A3411A-BCCF-4E0C-B453-E77A32A61D18","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7fa8a361f4adcd12f8657b809f8cc168dee87b5d","datavalue":{"value":{"entity-type":"item","numeric-id":4036562,"id":"Q4036562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ecd8b372516b4b1a88138862e7eab26f052e6860","datavalue":{"value":{"amount":"+0.891829252243042","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":"Q3495661$E34B3821-7CDA-4F06-8A2D-61290FF22602","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8d74da30f564ac0f02549431c7e89e6c96b3e2fc","datavalue":{"value":{"entity-type":"item","numeric-id":4388897,"id":"Q4388897"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0339c7dd8bf669333b076a86126d939cb41a5923","datavalue":{"value":{"amount":"+0.887586772441864","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":"Q3495661$A3F9092E-6440-4090-9377-813414D669D6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"05653934f9d7503c707f9053abf7a99cb122c38f","datavalue":{"value":{"entity-type":"item","numeric-id":579936,"id":"Q579936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0d9d93a766ad198f4adef4659265f170c433e08f","datavalue":{"value":{"amount":"+0.8631330132484436","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":"Q3495661$D2693E65-9B09-4165-961C-6540E8320554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2720e888ba97da74fc4e3cf8e6a66cb1c8b721e9","datavalue":{"value":{"entity-type":"item","numeric-id":4256643,"id":"Q4256643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"50165bb0685138f002936639725f4e37ddb163b8","datavalue":{"value":{"amount":"+0.8318371772766113","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":"Q3495661$D793DDFA-0D33-4730-925E-FCD4A1AF80B0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"66f8bbc48e0cd6dea702c6a4fa9ff9a3c411683d","datavalue":{"value":{"entity-type":"item","numeric-id":6487443,"id":"Q6487443"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c3e735cb117fcf5ec8b1e935f1074453e61a8e2e","datavalue":{"value":{"amount":"+0.8292882442474365","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":"Q3495661$FD61C0A9-66FF-4358-A9A8-53458E5E43FA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:3495661","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:3495661"}}}}}