{"entities":{"Q2763598":{"pageid":2774337,"ns":120,"title":"Item:Q2763598","lastrevid":79217033,"modified":"2026-05-06T13:24:40Z","type":"item","id":"Q2763598","labels":{"en":{"language":"en","value":"Regular expression star-freeness is PSPACE-complete"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1692648"}},"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":"Q2763598$6382E47E-D038-4B35-91B1-D48F99D3EB7D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cfcf4ed9ddf648dd4eaba4729e06e69d0f7a483a","datavalue":{"value":"0979.68048","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2763598$813F6F18-3050-4924-A066-C5277801F184","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2f93d777c3762d228287eeaa71d795f6f09ad77f","datavalue":{"value":{"entity-type":"item","numeric-id":674337,"id":"Q674337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2763598$48E1AB38-2717-48D1-99DE-C28D1371265D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"eafb9fa4931b16419fb1b5bcacfcea6ff21e7b8a","datavalue":{"value":{"time":"+2002-01-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":"Q2763598$E43D9A73-0F8F-4904-8467-6295735AC2A0","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"b4346faa01bb5fb0576370374d6456afd58d5666","datavalue":{"value":"68Q15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2763598$2B579937-E2EC-4C10-AEE5-0863A4DC6FFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"d7656d1c841701431b0b3d99d23720089a267cbb","datavalue":{"value":"03D15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2763598$8F8F4B51-8F4B-47EE-BEDB-7CF96FF1373B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2763598$6F053EB0-9D10-4FC8-AAB0-D40BDBDEADD5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d33b57f833a9a5597fc11f94d2ff18bce3a90f48","datavalue":{"value":"1692648","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2763598$7562240B-23D2-4941-AEB5-C42A3BD93EAC","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4369065edf6d8d2db82064ebbf82bc692ed5b6f","datavalue":{"value":"regular expression","type":"string"},"datatype":"string"},"type":"statement","id":"Q2763598$D13226C5-A15E-4C4E-ACB7-A59655693958","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53bdfb6af04f8c9f5906a0ff7ad737be573370f4","datavalue":{"value":"star-free language","type":"string"},"datatype":"string"},"type":"statement","id":"Q2763598$DCD759FD-10DA-43DC-9ED2-5E7C493D5747","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a05cfd9da536bc8387292ab9359d3f7e9902a360","datavalue":{"value":"PSPACE-complete","type":"string"},"datatype":"string"},"type":"statement","id":"Q2763598$A1CC98F6-97EA-4A44-8E66-4A3A821F2D18","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":"Q2763598$0E4C333D-D0BF-402A-84FC-E08149A6A923","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"41ba70f2f9a11d473176b09c22cc2ab99e3a113e","datavalue":{"value":{"text":"Regular expression star-freeness is PSPACE-complete","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2763598$19322DC8-D179-4249-AFBE-EDC6EA6896B0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"cb6f7b70ace46f7df4ae0a783d8a60c3adf62b33","datavalue":{"value":"Star-free languages form a subclass of regular languages: They are obtained from the finite languages by a finite number of applications of the operations of union, complement and product. By Sch\u00fctzenberger's theorem [\\textit{M. P. Sch\u00fctzenberger}, J. Inf. Control 8, 190-194 (1965; Zbl 0131.02001)] a regular expression is star-free iff it is recognized by an aperiodic DFA (deterministic finite automaton). [\\textit{J. Stern}, J. Inf. Control 66, 163-176 (1985; Zbl 0603.68059)] proved that the problem of deciding whether a DFA is aperiodic is \\textbf{Co-NP}-hard and belongs to \\textbf{PSPACE}. [\\textit{S.~Cho} and \\textit{D.~T.~Huynh}, Theor. Comput. Sci. 88, 99-116 (1991; Zbl 0733.68038)] strengthened Stern's result by showing that this problem is in fact \\textbf{PSPACE}-complete. Here it is proved that the problem of deciding if a regular expression denotes a star-free language is \\textbf{PSPACE}-complete.NEWLINENEWLINEFor the entire collection see [Zbl 0977.00022].","type":"string"},"datatype":"string"},"type":"statement","id":"Q2763598$9D037F32-FE54-4DF0-B1F3-C2C0BA467CD4","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":"c7c23b263d73d61b42391e4dc9f50897ed387625","datavalue":{"value":{"amount":"+0.9383977651596068","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":"Q2763598$AD8C642C-F0F3-4D08-806B-A71085881DED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"acc19528984774226fc2bde7dc275dc5539155ff","datavalue":{"value":{"entity-type":"item","numeric-id":809608,"id":"Q809608"},"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":"Q2763598$76307713-23D3-4891-818E-A95820A52F71","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b6758146fa92769e68d6717eb1847318c39b36e4","datavalue":{"value":{"entity-type":"item","numeric-id":4737154,"id":"Q4737154"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a47fb2f67ddc36fa1384f1661d7a26bb08e9be04","datavalue":{"value":{"amount":"+0.780492901802063","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":"Q2763598$83A6BA1A-8415-40AD-94FB-E75412849966","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70e07ca98430ea0f67988363309b9e28969d4e3b","datavalue":{"value":{"entity-type":"item","numeric-id":2361347,"id":"Q2361347"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"137d0601329ae5287826b4d8445bd6db9faac314","datavalue":{"value":{"amount":"+0.7715950012207031","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":"Q2763598$7817C57F-1922-4222-8DC1-05472F59150D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"80d7744612015955ba512201d56c92484288ea88","datavalue":{"value":{"entity-type":"item","numeric-id":1575674,"id":"Q1575674"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c187f3c9941d5648bd2233ed3babb5ab0e5bca0","datavalue":{"value":{"amount":"+0.7699084281921387","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":"Q2763598$7F3C35F7-7BB4-445D-8616-6244A1B22DFA","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Regular expression star-freeness is PSPACE-complete","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Regular_expression_star-freeness_is_PSPACE-complete"}}}}}