{"entities":{"Q442152":{"pageid":443919,"ns":120,"title":"Item:Q442152","lastrevid":55893337,"modified":"2026-02-20T22:00:35Z","type":"item","id":"Q442152","labels":{"en":{"language":"en","value":"Nondeterministic state complexity of star-free languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6064529"}},"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":"Q442152$33E37FCA-B649-4838-9321-4DB7F24FEF25","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"5a40bba17d75f19f04e51277259fd6289e718bed","datavalue":{"value":{"text":"Nondeterministic state complexity of star-free languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q442152$233F3DCD-88A1-43CD-B291-A23BEC66D2FD","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"2b4e6de8fad907f3d1649354de9c49e0fb969766","datavalue":{"value":"1278.68135","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442152$CC0BDAC0-30FE-4D86-9B6E-C69D72BEA5A4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c1704a18cfd2f14b89a97fd334fb2dab6ea6630e","datavalue":{"value":{"entity-type":"item","numeric-id":198230,"id":"Q198230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$479143DA-7E1B-4022-9FFA-65F185FAC929","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0f3d34816c1dbe170dc863d0f4b5d14681713b90","datavalue":{"value":{"entity-type":"item","numeric-id":442150,"id":"Q442150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$C4895C9E-B608-4BC6-9448-A6922541CB69","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff590ec82783480dd60992b2c3589ca83f426f90","datavalue":{"value":{"entity-type":"item","numeric-id":442151,"id":"Q442151"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$B01E09EB-9DA4-4736-9FFD-BC4B47B27BE5","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":"Q442152$9C5E52A4-E832-4485-9C5E-2002B7100CB7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"0276b87afe391e9d9e1b89aef5cbae8088ca3cb0","datavalue":{"value":{"time":"+2012-08-09T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q442152$CF84C501-FF2F-4B4F-9B3F-7983447E7279","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"587e5c2f64101fc1378a0c55968776d5385845dc","datavalue":{"value":{"entity-type":"item","numeric-id":383364,"id":"Q383364"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$9EC12174-28FB-4415-BFC4-76BA0197E980","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442152$5495E633-B869-4C83-AF71-499952387BAE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8b0f166240d9dc937c89dbc2241079deae14191f","datavalue":{"value":"68Q19","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442152$5CA3513A-137E-4C3B-9CC3-CE0F30823397","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c63a6e5580f3507b5029de82fed3304b82446799","datavalue":{"value":"6064529","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442152$11CE7110-F4E0-47DE-BDE9-984BC34C0CC5","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"32490d15e9a9f0544e6b80bbcf0c5a6a20c3be6f","datavalue":{"value":"star-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q442152$149F71A4-9278-4C22-BD3E-5379422E112F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"135d8aedfa48efbdf272187bb5e64a07ac5bbe92","datavalue":{"value":"nondeterministic finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q442152$F61DDC83-DF21-4B21-A70E-EDED7014915E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0520a0c7c86fb98d2a19f33036ab056a56e650e9","datavalue":{"value":"operational state complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q442152$D6DB3BF4-401F-47B4-9DD2-6463A264AFB8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d6b3ac5948a51082073fe08b55937180405a1900","datavalue":{"value":"descriptional complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q442152$3F469421-D331-4D49-9F72-713701ECD29E","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":"Q442152$E97EC3F2-4768-45E4-A486-8DCC8C3DE847","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"e977baf99b5d12a36c6ab8d76241e0d861e0dc6e","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2012.04.028","type":"string"},"datatype":"url"},"type":"statement","id":"Q442152$D451682D-9412-44E9-8BB5-8701286C50A9","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"3b33af59f67864d9b05c29e6111e5f6846b62f9b","datavalue":{"value":"W2071992537","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442152$BA18E448-7DA2-4E3C-AB53-1A2565FF608B","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"e47cebc04b7eb71cacd961bf04ae46d43cff618b","datavalue":{"value":{"entity-type":"item","numeric-id":1199879,"id":"Q1199879"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$528A77FB-E687-417A-AFF8-4C58A0EDE0D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5a4301cfd9c19886d1e53746958dca45ae0df160","datavalue":{"value":{"entity-type":"item","numeric-id":2271457,"id":"Q2271457"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$88D0E7AF-1482-4A93-859B-2AC81ECD3AAC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f0bbf3a7a712378cf892898f2c61acc63f13de0","datavalue":{"value":{"entity-type":"item","numeric-id":5544298,"id":"Q5544298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$4569D965-CBB4-4929-A85D-F18883BFECAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"298750c139a34ac5aeb5647550b65fc7dba0ed39","datavalue":{"value":{"entity-type":"item","numeric-id":2819381,"id":"Q2819381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$EB2DACBE-FAC4-4993-AFB1-AC51F67C3C02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"87110dc280025f5ca6742cb0f9f98c6def17e539","datavalue":{"value":{"entity-type":"item","numeric-id":5573395,"id":"Q5573395"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$0C29D7DF-873E-423C-8B59-031AFF1A6E3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c818e587c5c6dcead707f6d4e9d0e24e72f5304","datavalue":{"value":{"entity-type":"item","numeric-id":5740416,"id":"Q5740416"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$916C260C-7F9C-445C-92DF-4F5137F92554","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6a000c56abef8bc3bca7d081b59edc1b98bdf752","datavalue":{"value":{"entity-type":"item","numeric-id":5740417,"id":"Q5740417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$27A5761C-6C29-4B8D-BD10-93D303B81738","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"972ff908209cbae1dc0a10a9462932031345a6a7","datavalue":{"value":{"entity-type":"item","numeric-id":1099644,"id":"Q1099644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$2CF92B25-AAD0-4567-BB87-F936DA9B3FC3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"74f6b3962d0b7810403b7eee71ced0a053db5765","datavalue":{"value":{"entity-type":"item","numeric-id":671381,"id":"Q671381"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$21810AD9-AE30-48CB-875D-E16B2EA60855","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1aed0b54a0552350b668339b4c3782ba029fdc6e","datavalue":{"value":{"entity-type":"item","numeric-id":4964025,"id":"Q4964025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$9F4BE3D6-AA4C-445B-8E4D-903438303214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0347f28d9efe85f23a23ba0b66052d2cc0fe5f0e","datavalue":{"value":{"entity-type":"item","numeric-id":3625777,"id":"Q3625777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$464E1E6D-804A-451E-8FF6-CD91EA036722","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c0cf3e1a07d688a4d99a934eec5b364e47efb8d","datavalue":{"value":{"entity-type":"item","numeric-id":4964015,"id":"Q4964015"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$D883424D-73FA-4D29-9CDF-376EC2F8B14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1dfc54e6aff8c95aa804578463c97592a97f101b","datavalue":{"value":{"entity-type":"item","numeric-id":5696955,"id":"Q5696955"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$BC38FCC5-4BC0-46C5-AE0B-883BAD841AB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e44657104c5ffc128aa1542b689f134dfe0cbc35","datavalue":{"value":{"entity-type":"item","numeric-id":4412108,"id":"Q4412108"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$5778DD41-2636-4EEE-8EA7-4AC123FEA793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5659e3f1fc30cf8a1aac92fd2c1ed2783063f06","datavalue":{"value":{"entity-type":"item","numeric-id":3395129,"id":"Q3395129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$CF6334D7-1CE1-4F72-8E1A-F782500DC518","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"84024d594973ff8e971980ddb8d142a5250b40e7","datavalue":{"value":{"entity-type":"item","numeric-id":3102144,"id":"Q3102144"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$194CB1EA-F3A4-476B-BDD7-0D0FC97A3388","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25671577fa4958887cecc5eb5572a0caef1b2663","datavalue":{"value":{"entity-type":"item","numeric-id":553312,"id":"Q553312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$69550D54-705A-4DA5-98FB-9E1F16BE43C4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ed3f1391c7b47b266fb8b9ff026fe5651e6dbd51","datavalue":{"value":{"entity-type":"item","numeric-id":1763716,"id":"Q1763716"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$B295D5DF-9D81-405E-831B-B138D9B5A36D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d39d7d5844678799cb08bc9d199833d1efd26f0b","datavalue":{"value":{"entity-type":"item","numeric-id":4964027,"id":"Q4964027"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$A3DFFB68-DD16-4DA9-BA4C-1B051A37526D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"758b2bbf0d8627b4c27f40efe942fb9e5daed106","datavalue":{"value":{"entity-type":"item","numeric-id":3584898,"id":"Q3584898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$977F5B0C-A7CF-4A7C-892C-BAC3C64C62D1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"735238b3e7c7f03ab1fec1b4302c31439ded9b9c","datavalue":{"value":{"entity-type":"item","numeric-id":5554980,"id":"Q5554980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$7CBC1D63-DFBF-447A-9AD1-E02DC7AB2AEA","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":"Q442152$E76BE50C-5297-458C-A75F-08F5DDA13D1B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0278800f6ef68b92b4fbe71c7deb41d4085afbe","datavalue":{"value":{"entity-type":"item","numeric-id":4503152,"id":"Q4503152"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$FB9FDFD3-AF86-4A8E-A460-8B303CC2D9B7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b17ea6ba4e4429ffb05cb421d82f8ab4f37ea19a","datavalue":{"value":{"entity-type":"item","numeric-id":2719119,"id":"Q2719119"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$8FE0A934-FE22-4466-98E5-90E2591D5071","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"71af02a11f0cbe069e4ea9beb45ae622432bd444","datavalue":{"value":{"entity-type":"item","numeric-id":5638224,"id":"Q5638224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$1CDEE378-9041-49E9-835C-0C03A8A3121E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8c91f3e531d0087256bd01284f860adad823be3","datavalue":{"value":{"entity-type":"item","numeric-id":3021944,"id":"Q3021944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$2B5BF258-D37E-4D3B-BD08-1D417259BC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8107b480decc678c92b78dee11f4a9915c90692b","datavalue":{"value":{"entity-type":"item","numeric-id":5541339,"id":"Q5541339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$BC491228-38DA-4CE8-AAEE-F04C63F75A3E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95c9edc7bffb517baa50dc0f40b7aaddce7232c2","datavalue":{"value":{"entity-type":"item","numeric-id":4390537,"id":"Q4390537"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$E821FCCA-155B-4540-A946-01AB879ABE8E","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":"Q442152$79224363-3161-4210-AC94-A15F22B7B6F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6010dfa0c0aca8170d85236d66a3acb448088bb8","datavalue":{"value":{"entity-type":"item","numeric-id":4057601,"id":"Q4057601"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$B72D40DE-37BD-42B3-9582-249A259AAC2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"794ddd2b2b6a878510a110ac293ea793899d01b0","datavalue":{"value":{"entity-type":"item","numeric-id":4775487,"id":"Q4775487"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$64380656-9BC7-4C15-9E78-4A9DED6245FE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"368a3d7512f74e3e19fb0ca700e2c9c6eb058628","datavalue":{"value":{"entity-type":"item","numeric-id":2731279,"id":"Q2731279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q442152$75A7FEB2-D1B8-4A52-9892-96AFE096F5A3","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"4227cc6903ec4dc7d7ee226c3308903ca239d297","datavalue":{"value":"10.1016/J.TCS.2012.04.028","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q442152$3134AA71-3360-4643-9FA6-F04744FB17AA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"154c1c76ac5c8abd63f4030d84face0aef60667d","datavalue":{"value":{"entity-type":"item","numeric-id":5200063,"id":"Q5200063"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0c5155ed25473626de874a58e3d09e49f73e1ba","datavalue":{"value":{"amount":"+0.8983855","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$7204A5F0-6862-4B1E-9E50-ADDCD01DCB17","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac967b2281fa3560e04744a52b7152f6cb758c7c","datavalue":{"value":{"entity-type":"item","numeric-id":4923279,"id":"Q4923279"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"932f6ca9cba954aac308a33e801f44fc77154afa","datavalue":{"value":{"amount":"+0.8601755","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$4EA805C5-2877-49FD-9CFF-96A868D84B3C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e88103f81ece85ee39db6c4cc72f7e5e9b40004d","datavalue":{"value":{"entity-type":"item","numeric-id":5740417,"id":"Q5740417"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0ccd7c9f41e764dcd5acb759052be722c1259a49","datavalue":{"value":{"amount":"+0.8600357","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$224CEC0A-3D58-449E-A115-ECEC4732EE09","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7857356d2678ebf91a6a126e135e973ee4439913","datavalue":{"value":{"entity-type":"item","numeric-id":5500696,"id":"Q5500696"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"066561d6ba2a534cb947bc44fc04dc0e005a83e6","datavalue":{"value":{"amount":"+0.85500866","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$3FF04B33-F724-409F-9183-F70CC4E4273B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0e9c6d5d16acb51bd566f14c215d97b1784031d9","datavalue":{"value":{"entity-type":"item","numeric-id":5178449,"id":"Q5178449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2a296e78ad24a4e8e149001e393efca28462b942","datavalue":{"value":{"amount":"+0.85020256","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$834879C6-E95A-4DF9-ABE0-EA52C4BD403C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b57502f86d7219309a3473ace43eda213cb8f075","datavalue":{"value":{"entity-type":"item","numeric-id":2179330,"id":"Q2179330"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45f862b1281aaca8263fab406a95e6350d6ce4e1","datavalue":{"value":{"amount":"+0.84824014","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$34186882-B21A-4188-8648-689B57448457","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1984f6e089bfc99f4e0d0745c3e8cd2c9b9c555e","datavalue":{"value":{"entity-type":"item","numeric-id":4964025,"id":"Q4964025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d995d0d1eed48f22fd2430da6238f1937fa8fb1","datavalue":{"value":{"amount":"+0.8437217","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$F91887A6-97AA-4457-842F-44FA97F6471D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"90985d9b2ceac1c0461b02fe2db49b3d8b6e37df","datavalue":{"value":{"entity-type":"item","numeric-id":3625777,"id":"Q3625777"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ed1e46c765b492662d5cdef5f345c815dd8be66","datavalue":{"value":{"amount":"+0.8398844","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$BB889B24-1E6F-479B-BED0-CA3D57E843B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69843662339f028f0f90028c30d37e44003f4d28","datavalue":{"value":{"entity-type":"item","numeric-id":3167576,"id":"Q3167576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d2bd56ee0a01a475ceba69a96acfbe4edd90462","datavalue":{"value":{"amount":"+0.8376982","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$1735FB03-CF0E-4788-A444-2E009AF7609A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8a80c0e70e777a3e5bc9dd156c3c4f1f4b71ea77","datavalue":{"value":{"entity-type":"item","numeric-id":1029324,"id":"Q1029324"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8a6a41f7fe09ed40ada8c15f264c7439e7809712","datavalue":{"value":{"amount":"+0.8362979","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q442152$26DEC6BB-B0A0-4CD0-AC99-76A0F9672D0A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"0b7ffdabaab59d53273703d080195e4fc4446ec1","datavalue":{"value":"The class of star-free languages is a relevant subclass of regular languages, which can be described in terms of regular expressions, extended to include all boolean operators, but without Kleene star. Properties of this class have been widely investigated in the literature. In particular, concerning \\textit{descriptional complexity}, the field of investigation where this paper can be classified, a recent interesting result shows that the exponential state gap between nondeterministic and deterministic finite automata can be achieved even restricting to star-free languages [\\textit{H. Bordihn}, \\textit{M. Holzer} and \\textit{M. Kutrib}, Theor.\\ Comput.\\ Sci.\\ 410, No. 35, 3209--3222 (2009; Zbl 1173.68030)].NEWLINENEWLINEThe paper investigates the nondeterministic state complexity of the basic operations on star-free languages. A similar investigation for the deterministic case has been done in [\\textit{J. Brzozowski} and \\textit{B. Liu}, Int.\\ J.\\ Found.\\ Comput.\\ Sci.\\ 23, No. 6, 1261--1276 (2012; Zbl 1272.68206)]. It is shown that the lowed bounds which are known for those operations on regular languages can be achieved even restricting to star-free languages, namely, the nondeterministic state complexities of those operations remain the same restricting to star-free languages. The case of unary star-free languages, namely, star-free languages defined over a one letter alphabet, is also considered. Only one relevant difference with respect to the general case is discovered: the complementation of unary star-free languages uses a quadratic number of states, while the same operation in the general case requires exponentially many states.","type":"string"},"datatype":"string"},"type":"statement","id":"Q442152$AF3EBF37-A2F3-4E7A-95C7-4EB7A37ECA42","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:442152","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:442152"}}}}}