{"entities":{"Q1099620":{"pageid":1110372,"ns":120,"title":"Item:Q1099620","lastrevid":42877339,"modified":"2025-07-15T15:39:37Z","type":"item","id":"Q1099620","labels":{"en":{"language":"en","value":"The method of forced enumeration for nondeterministic automata"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4041272"}},"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":"Q1099620$9C9BB1A1-91D7-4339-8C94-F60129B2A7A4","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"832bf5a06b0a0d7f09165d50027587ee86fdde86","datavalue":{"value":{"text":"The method of forced enumeration for nondeterministic automata","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1099620$808EAADE-F1B6-4E03-AF75-22C44C180D03","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d04f93c701152e19d7600dca296ca2b127a14be3","datavalue":{"value":"0638.68046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$8E993362-8372-49F3-85E5-9D5D42DED328","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"461bdcbea7e5ed720964c54a4ba4a1dd7ef63c12","datavalue":{"value":"10.1007/BF00299636","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$4BC5E4BC-D520-4C3D-86CC-B71E8BCBE187","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"7d0f02e85530cd06ceb2c58a40dc9c2e0258e194","datavalue":{"value":{"entity-type":"item","numeric-id":161641,"id":"Q161641"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099620$E546F1ED-C165-4046-A9C1-A0FE5A741EE7","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"31a1937240ca4a323604b4728c31d242b5596d7c","datavalue":{"value":{"time":"+1988-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":"Q1099620$8A6DDF70-73E7-4754-8B71-E59CB69E1451","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"6f11c87dd8318425853dd2df07a024b4eb1628f1","datavalue":{"value":"The paper presents a new method of simulating nondeterministic Turing machines. The method forces every accepting computation of a nondeterministic Turing machine to examine all reachable configurations of the simulated nondeterministic Turing machine working on an input word w. It is important that the simulating machine does not use more space than the original Turing machine.    Using the new method we prove that every family of languages, recognized by nondeterministic L(n) tape-bounded Turing machines for L(n)\\(\\geq \\log n\\) is closed under complement. As a special case the closure of context- sensitive languages under complement follows.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099620$4CF22255-3494-4F83-BF3E-244EC5A014C5","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$A97DC0AF-D3F7-4A30-8F1B-D9BDD9DDB14E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"a7dde57cbaf704d564d8f981ca98d6340e3d4aaf","datavalue":{"value":"68Q05","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$4D57345D-230F-4023-BD01-86DE3633B769","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1438824e72a6ecb06a3dd6668f0bca81d088a1bc","datavalue":{"value":"4041272","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$8A5A5BD9-B8F1-4170-AEBA-AD44141917BF","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"268b03dc4e0714cef69083adf2c38b64e3ca8758","datavalue":{"value":"forced enumeration","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099620$A4E18717-C511-4B53-BE14-0620B7217987","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"6abde220793268065a5dcbf29c614de31957d669","datavalue":{"value":"nondeterministic automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099620$8352188E-8B05-45A5-9250-F58BD7986252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e110c412e54b2452c8373d9452a32c9d1288b502","datavalue":{"value":"nondeterministic Turing machines","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099620$CE306700-D78E-43EE-B14E-9FFEF70BCE0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"901c5e9b5aa7ba0172a3d2c5bc8e860560cef915","datavalue":{"value":"closure of context-sensitive languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099620$64E6CE58-A31C-425D-AF2D-0C3D3BD85483","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5609a50c85bfa2ac7f5fa4c3f0144026334fa5d6","datavalue":{"value":"complement","type":"string"},"datatype":"string"},"type":"statement","id":"Q1099620$51DA693C-DBAF-4F42-BF76-290B86F7F465","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"e5519ba29f25632418c0106c16d85fecef291745","datavalue":{"value":"Q56386805","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$2B8267B0-170B-4F88-AB44-5A3E074E1273","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":"Q1099620$25597DA7-270E-426B-B366-7E9901F3B808","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"2043397a54eaa38033021fac24881dafefacec7d","datavalue":{"value":{"entity-type":"item","numeric-id":5592246,"id":"Q5592246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099620$1654396C-775F-405B-A4E7-55BC58852D00","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"04ca7a1acbb96c14c8f84c4ce6e6462daf757716","datavalue":{"value":{"entity-type":"item","numeric-id":3773337,"id":"Q3773337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099620$E9F73E07-5DBD-4CE2-A1B1-0452D4B7C7D0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6926e920f34ad943bbe1de8ce4a6882fa67a950c","datavalue":{"value":{"entity-type":"item","numeric-id":5596812,"id":"Q5596812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099620$FCC24BC6-7C8F-4234-9B2A-DD6CC4D5B5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"67ed33de7061de4d7d8391bea59c71fda756b59c","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099620$D536EC0C-FA14-4107-A087-092C4D05AE59","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ae6fac483ebbfbd42a1a0033b4a4a0257f946fc4","datavalue":{"value":"https://doi.org/10.1007/bf00299636","type":"string"},"datatype":"url"},"type":"statement","id":"Q1099620$BCC7314F-5583-4DA5-8470-AA3600A07190","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"260710830d58a5c199e6fc4315f352f0634ef8fc","datavalue":{"value":"W1590283810","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$F1BD2C1D-0870-4E88-85E5-DC1C9799B085","rank":"normal"}],"P1635":[{"mainsnak":{"snaktype":"value","property":"P1635","hash":"62fbcef99a9a9189859d2bfb6ea68679661328a0","datavalue":{"value":"journals/acta/Szelepcsenyi88","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1099620$0CC3F86E-0270-4C4E-A2B7-2634FF8D78D2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"33351f5f691437454672a002b3588e5d83f32bc4","datavalue":{"value":{"entity-type":"item","numeric-id":3815544,"id":"Q3815544"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d440a530999121bfb704c3f67749a268e07180e","datavalue":{"value":{"amount":"+0.9486863","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":"Q1099620$A7F0E62A-716E-48EC-A4F7-EF108A5E3DBE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d45c6eb527d0d8ec5f483897262e5d11e48cb1ba","datavalue":{"value":{"entity-type":"item","numeric-id":5714672,"id":"Q5714672"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9d9a188094d9ad9084863f589744d0be7ad2353e","datavalue":{"value":{"amount":"+0.8797954","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":"Q1099620$28222875-18B9-442D-AA54-6629095A812D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fad9ffd0bc569c869168b96021d0a650a7b5d40a","datavalue":{"value":{"entity-type":"item","numeric-id":3077339,"id":"Q3077339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e5f39b059249b969333153660cbde6a9961f4862","datavalue":{"value":{"amount":"+0.8657681","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":"Q1099620$6231DB8C-5B7F-4D09-9F50-3C31DD5C633B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"efe234da41ec3523394a1a18fba18052a8887944","datavalue":{"value":{"entity-type":"item","numeric-id":2489949,"id":"Q2489949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"13171fc0a969c9c8b1843ea359910e8a9a454759","datavalue":{"value":{"amount":"+0.86459994","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":"Q1099620$F0B7EA52-2455-4117-A5DA-F6798AA520E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c5c3c0e8747f515f175d74a74e15db2d682e38cd","datavalue":{"value":{"entity-type":"item","numeric-id":995562,"id":"Q995562"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"301ca976b14d95fa33f87255edad1061372e1099","datavalue":{"value":{"amount":"+0.85623497","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":"Q1099620$6C70BD0D-2BF4-44BD-B1B4-F146BBA28881","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"aee0e95b9452e62519988efc9af1d5487024490a","datavalue":{"value":{"entity-type":"item","numeric-id":3706507,"id":"Q3706507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cf3bb3bc17b468b45fd8f6b673d645e68d1b18f","datavalue":{"value":{"amount":"+0.85561013","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":"Q1099620$B42C4B68-A495-4D19-A114-5CEC8A56CB30","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"023a5bd4d68b7050dfd8bec67f15317dda576f5c","datavalue":{"value":{"entity-type":"item","numeric-id":2454972,"id":"Q2454972"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bec6f7977df3632bdeed20029748677af19c04c4","datavalue":{"value":{"amount":"+0.848055","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":"Q1099620$443C9D07-4DB3-4913-A7DE-4B3CDD7055E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"08a7f4e6c17b6a320d0a580c840592b2ffdd9198","datavalue":{"value":{"entity-type":"item","numeric-id":1122575,"id":"Q1122575"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c6597326e7f815ea92a2db9bfab1993ed3e2c24c","datavalue":{"value":{"amount":"+0.847016","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":"Q1099620$54592E3A-67EF-4FD1-A5D4-6C048C6FB96B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"797349e4b471db4558a8365b4813be25829d0bf2","datavalue":{"value":{"entity-type":"item","numeric-id":3738563,"id":"Q3738563"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c9ef890b83549a3963c8966a849d2f23f63f76e","datavalue":{"value":{"amount":"+0.8463968","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":"Q1099620$CDABB9D5-D528-415A-84D0-3988B0062B3B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dea8b09c700d2252aef4e997782985998b96dccc","datavalue":{"value":{"entity-type":"item","numeric-id":4452093,"id":"Q4452093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8e6cc17942709db44e053e1bfd381322c894217","datavalue":{"value":{"amount":"+0.84329504","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":"Q1099620$2C596030-17F9-48EB-AE6B-6F8B80EC08A6","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6c6f11767c7298414372481fc5fbe56dd8616eec","datavalue":{"value":{"entity-type":"item","numeric-id":6482618,"id":"Q6482618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1099620$81C5B68F-2D05-4D48-8B58-C635B7D7259C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1099620","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1099620"}}}}}