{"entities":{"Q809608":{"pageid":811456,"ns":120,"title":"Item:Q809608","lastrevid":64539108,"modified":"2026-04-11T20:34:02Z","type":"item","id":"Q809608","labels":{"en":{"language":"en","value":"Finite-automaton aperiodicity is PSPACE-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4213449"}},"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":"Q809608$D5596623-6DA0-485C-8625-C51422102943","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"174c3ee648517d4d1e4b73da6938f009c942a148","datavalue":{"value":{"text":"Finite-automaton aperiodicity is PSPACE-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q809608$548C94D3-CAF8-42E2-BBDD-1EE2C581D708","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"48686c3ead1db49edac754f825a440a7ebf845d2","datavalue":{"value":"0733.68038","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809608$BA47D542-E977-4639-B92A-7A92C84A103B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"35b349bee5dd16bada642420b7cebba6c212570b","datavalue":{"value":"10.1016/0304-3975(91)90075-D","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809608$6482145A-A08D-4FF7-A5A3-654556E52973","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"77ffddd258152338da5cc01c34750ffd5ad04d31","datavalue":{"value":{"entity-type":"item","numeric-id":809607,"id":"Q809607"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$CC32B234-0CB3-4BBF-A8AF-9232919AB249","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f11d29d2cbdb03c4d5ff90d92cbc2f1d658ba97d","datavalue":{"value":{"entity-type":"item","numeric-id":391197,"id":"Q391197"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$0B8A8495-3584-4520-A905-592BF0E9CFCF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f3c424cd94a60f9664f9fb69cc6027e75cc7ff3f","datavalue":{"value":{"entity-type":"item","numeric-id":123643,"id":"Q123643"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$903C3858-EE01-466E-909D-E8626A881048","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"391107ffc7a24346d69c573e292e4ff4587e3aaa","datavalue":{"value":{"time":"+1991-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":"Q809608$32E97CDF-4A1F-403F-8F1B-1CEBFC65F214","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"500c267420f0b20523b02415bc5f987f18d089bf","datavalue":{"value":"The following three algorithmical problems are investigated. Given a minimum-state deterministic finite automaton M, is the language L(M)    1) a star-free language (a language expressible through regular expressions without *-operation)? 2) a dot-depth language? 3) a piecewise testable language? It is shown that Problem 1 is PSPACE-complete, and Problems 2 and 3 are logspace complete for NLOG. This solves the open problem from \\textit{J. Stern} [Inf. Control 66, 163-176 (1985; Zbl 0603.68059)], where a polynomial space algorithm for Problem 1 and polynomial time algorithms for Problems 2 and 3 are presented.","type":"string"},"datatype":"string"},"type":"statement","id":"Q809608$6B3E5FD7-9E5D-4637-8B76-4001392B9810","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809608$7F4D6AFA-48C7-4E1E-A7C2-219AFB6614A2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809608$A7C50E21-6515-490E-BB86-DF68A089B0FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809608$7D2720DB-E0CB-4596-B769-A9A587DD365D","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"db717dac295c8748445b25ee349a972cd80537d2","datavalue":{"value":"4213449","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q809608$B3129E91-9D63-489E-AE48-18AEE4B2F0C8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q809608$088DEA57-C43E-44CC-9217-DF93391753DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27638d630e18a79d37aae3ab247a2d08a15508a4","datavalue":{"value":"decision problems","type":"string"},"datatype":"string"},"type":"statement","id":"Q809608$E2D90C37-81F2-4E34-B7FC-5D718CB8D2BE","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"633fdcabf2e644e3cc3929da0924cb1d112f41ed","datavalue":{"value":{"entity-type":"item","numeric-id":208754,"id":"Q208754"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$28B0951E-54D4-4450-B19C-2B422A4C3F5F","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":"Q809608$FA59691A-93D0-444C-8ADF-A17E1E680C36","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"a3baa15d3ebc8f013bb1c5bad57c1b9f6aadaf95","datavalue":{"value":{"entity-type":"item","numeric-id":1186807,"id":"Q1186807"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$2C570CFF-16E7-4C73-A9B7-D044114B99FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb40aa93777a7cd41d54dcf43b55867cf1b75c38","datavalue":{"value":{"entity-type":"item","numeric-id":5772619,"id":"Q5772619"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$CAE20D57-B903-452C-AB4D-CDF58E976856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b1758902a66e2332f9d1d0268ecf38eeeb4d377f","datavalue":{"value":{"entity-type":"item","numeric-id":3862379,"id":"Q3862379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$B3E3B1CA-59BE-456F-8B94-FC2244C62A10","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c767919e94a3332b8d198174b1921d5e4026fe","datavalue":{"value":{"entity-type":"item","numeric-id":3821586,"id":"Q3821586"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$AB93A925-E0C9-4353-AD68-DD3E0843915A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"736a1d463d18d2f300e2b9600c3f86eae2986ef8","datavalue":{"value":{"entity-type":"item","numeric-id":2537313,"id":"Q2537313"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$380582AC-44A6-4443-9BEB-E69FEEC9134E","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":"Q809608$17F7F9F2-F7BF-45F3-9F52-7E5117DDF791","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99c71bf5594d80706e33dcbc13841c2d147bc380","datavalue":{"value":{"entity-type":"item","numeric-id":4077455,"id":"Q4077455"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q809608$904F0D87-C66C-458A-8AA9-A9ED4474F381","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":"Q809608$B050B5AA-B093-4FE9-9469-257C870EDE6C","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fa3a4dd3784f7a5bf3d4af61b22bc947bdea045b","datavalue":{"value":{"entity-type":"item","numeric-id":4382097,"id":"Q4382097"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c1d0491e71b3027968e9106de0712e1754041849","datavalue":{"value":{"amount":"+0.8800041079521179","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":"Q809608$439B0E18-BADD-43E3-8B3D-ACFB76F28F18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"179f563cb3d55277b9a8d0dc36096cd94eabbe77","datavalue":{"value":{"entity-type":"item","numeric-id":2763598,"id":"Q2763598"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22fa70e856c0107de22dae5994129156b6817939","datavalue":{"value":{"amount":"+0.870557427406311","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":"Q809608$446EBAD8-CCD0-4AE7-AE01-25FA77301562","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9cd1cff9f96fff406310a106fb71beaa2d2dbff7","datavalue":{"value":{"entity-type":"item","numeric-id":4227133,"id":"Q4227133"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"22fa70e856c0107de22dae5994129156b6817939","datavalue":{"value":{"amount":"+0.870557427406311","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":"Q809608$21373ABE-5DF1-4631-A9F1-F3D17A5DA381","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9c97609134cede3c6678a323c6dfcf68d967f6c2","datavalue":{"value":{"entity-type":"item","numeric-id":3740247,"id":"Q3740247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1483e2bc8d06c1eef2e26d81a844e36bbda56528","datavalue":{"value":{"amount":"+0.8137040138244629","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":"Q809608$3A8DA09F-449F-4382-85B9-8D8C11F2B2E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8b4400bbdc0cbcab79d68b21692c317a6fb06b48","datavalue":{"value":{"entity-type":"item","numeric-id":4032922,"id":"Q4032922"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1e90ebc35aab7e39ab18e1af4f0979520963f905","datavalue":{"value":{"amount":"+0.8071275949478149","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":"Q809608$4911664D-68F8-4C60-AB14-942A504FBE5B","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Finite-automaton aperiodicity is PSPACE-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Finite-automaton_aperiodicity_is_PSPACE-complete"}}}}}