{"entities":{"Q685373":{"pageid":687222,"ns":120,"title":"Item:Q685373","lastrevid":63459654,"modified":"2026-04-11T13:18:16Z","type":"item","id":"Q685373","labels":{"en":{"language":"en","value":"Efficient constructions of test sets for regular and context-free languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 417327"}},"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":"Q685373$C622D387-5E41-4647-9E47-7F666D33935F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"2377c698a0718b7236378639e0c10760188a6c5c","datavalue":{"value":{"text":"Efficient constructions of test sets for regular and context-free languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q685373$6A184894-DD9B-4A63-A567-AB0240AAC866","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f6ad54ef5d4edb8c208e4172578d309ad90474fe","datavalue":{"value":"0793.68090","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685373$0CCFC040-9F79-40EB-9AA8-B597BE2DE119","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"014b275acda2d560528e18758398b9b09a8185cc","datavalue":{"value":"10.1016/0304-3975(93)90325-N","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685373$2EDC29BA-C45D-4817-AFE4-088EE73575BD","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"91cebe2c3862ce21207f21b89197103c43f307fb","datavalue":{"value":{"entity-type":"item","numeric-id":223814,"id":"Q223814"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$615D8A8E-C79D-42FC-B8C9-34CF9D01EF26","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"446a873621e510ca421dac98a0ecf4b1b1cd2e8d","datavalue":{"value":{"entity-type":"item","numeric-id":313971,"id":"Q313971"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$A701B9AF-0E05-4C65-B021-7624573C0781","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a9d0961cd2cf37832e04a52a9732ab94cad5dfb5","datavalue":{"value":{"entity-type":"item","numeric-id":672734,"id":"Q672734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$1A850492-E851-40B9-9371-28EC2F24D655","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":"Q685373$B8792172-A294-47E5-8C14-D21F8B70FE4E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5d02bde13d622d42f9b76cdf00d7fe9c53527b91","datavalue":{"value":{"time":"+1993-10-25T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q685373$07860D03-964B-4B41-A1FE-38E8DFD3DD4D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"22ca8fbe0741c4795748ce1052442bd9d6243b7e","datavalue":{"value":"This paper involves a nice contribution to a formal language theory. It has been known (Ehrenfeucht conjecture) that, for any language \\(L\\), there exists a finite test set \\(F_ L\\) (for each pair of morphisms, if they agree on \\(F_ L\\), then they agree on the whole set \\(L\\)). Here, a simple construction of linear size test sets for regular languages and of single exponential test sets for context-free languages is presented. This essentially improves the best known upper bounds: exponential for regular and doubly exponential for context-free languages.","type":"string"},"datatype":"string"},"type":"statement","id":"Q685373$F53F5E69-46CC-4A5A-8E2E-933F4DCAC348","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":"Q685373$EBFC25C6-D24A-468A-8F8E-EE3C6C8F8FCB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685373$753588DB-D7AA-4D39-AADF-C051C97C8075","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685373$F3185ABB-4CB4-4D71-9FD1-59FD4AD210E2","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b8b48be13cf339d90c71832886d5a512ba582742","datavalue":{"value":"417327","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685373$0B7CA2E8-81FE-4432-97F8-C1CA3F561063","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e8fe1ec072eddb82e8c6723b370c91fea5db0efe","datavalue":{"value":"finite automata","type":"string"},"datatype":"string"},"type":"statement","id":"Q685373$420356A6-EEE6-4675-9963-1D5B42FFE2E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a37f1b310a3dab2e44459244c624b1e251e5b8cd","datavalue":{"value":"context-free grammars","type":"string"},"datatype":"string"},"type":"statement","id":"Q685373$842E0735-9276-4D10-8CC8-AF25C0E0BF11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b737340a658db4117ab44a3cae85a83747ba45ca","datavalue":{"value":"formal language theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q685373$838250A2-939D-4CDE-9621-50D18340A49C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b3783df59647a950f9dab833b02656c2c8328b54","datavalue":{"value":"test sets","type":"string"},"datatype":"string"},"type":"statement","id":"Q685373$CAF39FD9-913C-49F3-ADDB-3D88BF614EA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q685373$487FFFE0-8795-444C-A144-3F8455923CAD","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":"Q685373$A4968853-8AC9-4C4F-B8F3-908AD1B56938","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"aeb07ca89a63cc1d58eddbd66f8d974a65762099","datavalue":{"value":{"entity-type":"item","numeric-id":3673125,"id":"Q3673125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$60B1204A-AA68-47BA-8E6E-666F5B08FAD0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bded8f67469698565087411d6ce4229139e7b50d","datavalue":{"value":{"entity-type":"item","numeric-id":1082090,"id":"Q1082090"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$EBAB130A-5189-4C57-BD87-7D59D703B127","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b8d7ab2f3382dac7d37a1d66689449a603719e6f","datavalue":{"value":{"entity-type":"item","numeric-id":754658,"id":"Q754658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$1742137D-A36B-4A32-99E8-AF9E8011E191","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6ef981611ae9580f5725d77e06569d41be8d877c","datavalue":{"value":{"entity-type":"item","numeric-id":3355232,"id":"Q3355232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$A8EA79C8-7E82-48E8-B90B-BA7ABAA4F44A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0dc01f3100301b38f61a7577d1472e11bbe79b2b","datavalue":{"value":{"entity-type":"item","numeric-id":1251076,"id":"Q1251076"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$0E72D2A2-2133-4B17-BF57-301EDC2A7EA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b7e6c6e76c534f7463056bc07257e9faa9fbf18e","datavalue":{"value":{"entity-type":"item","numeric-id":1148122,"id":"Q1148122"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$746B46DB-0C44-417B-9183-6681146BEEF0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9f3c4123c6f16f5598589a408c561cf8e1584d03","datavalue":{"value":{"entity-type":"item","numeric-id":1056551,"id":"Q1056551"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$C809BA65-1069-4E0C-BEE5-B11CEAA243EA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c67e7310d71a3ff5db7aa06fe30017f241c342d5","datavalue":{"value":{"entity-type":"item","numeric-id":3968472,"id":"Q3968472"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$10E6199A-7F2A-4FB9-B6C0-574A0696D807","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":"Q685373$C030E029-E59A-4433-B499-4362EDE74DBF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5bee5a181d891b451d07326284c0a19b6b74acb2","datavalue":{"value":{"entity-type":"item","numeric-id":798007,"id":"Q798007"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$5030FDF7-8F34-493E-9FAC-30F59C55DEE0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63f6e93c6ebff3e0f9f24e9852a8d52922c49014","datavalue":{"value":{"entity-type":"item","numeric-id":3769982,"id":"Q3769982"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$15415DC4-8CCF-44FD-B30F-9A970D2A2035","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d7f0cd46c1e5d12c37cd99b838114ab8ce34a158","datavalue":{"value":{"entity-type":"item","numeric-id":4125823,"id":"Q4125823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$498B1F7F-42EC-4700-917E-4BD7A3D1F1F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59f60764865641217d564887c22fdd45b8531bb7","datavalue":{"value":{"entity-type":"item","numeric-id":3948608,"id":"Q3948608"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q685373$C80EC513-02A6-4379-B3CE-738CCDF8739B","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f164dc11a9008a0886392159672c9691552806c8","datavalue":{"value":"https://doi.org/10.1016/0304-3975(93)90325-n","type":"string"},"datatype":"url"},"type":"statement","id":"Q685373$90D720E1-3B03-4E97-833A-6F2BA9A2FDF7","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c31cd46f4f5209eb237a78ffb273d7e698dd552c","datavalue":{"value":"W2017795761","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q685373$969D92D4-1D40-4EC9-9583-284F73162A1F","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"42dfe09d9d8eda49d5ec46f73f3f377bee256b8d","datavalue":{"value":{"entity-type":"item","numeric-id":4035247,"id":"Q4035247"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9e23bc37428720df1e8397b650671a0992172ed","datavalue":{"value":{"amount":"+0.8642673492431641","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":"Q685373$49C99646-FBA6-4436-BD0F-B78F8210ED2D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b2c2be69e1b6cceef2522a525ce26c191748c1c0","datavalue":{"value":{"entity-type":"item","numeric-id":4840153,"id":"Q4840153"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3a6f3165f9b372a5c809b27af30e633041c58774","datavalue":{"value":{"amount":"+0.8598166704177856","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":"Q685373$79F86AFD-F515-40C2-83C8-FDCB0899F20E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f252a39b7775b11274fe52b9c18237fd561735d6","datavalue":{"value":{"entity-type":"item","numeric-id":5204306,"id":"Q5204306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14b0938cd66c68829daec2afef7314431735fa02","datavalue":{"value":{"amount":"+0.8407371640205383","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":"Q685373$285E8647-1435-44A6-987A-E910D1BC763A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d1bab57a16badfe8b5ef723f46cbd0bb8b45456","datavalue":{"value":{"entity-type":"item","numeric-id":1892201,"id":"Q1892201"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48c44d0e571679b2453de1bee6a9311d904a45fe","datavalue":{"value":{"amount":"+0.8324581384658813","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":"Q685373$52E1ECFB-ECC8-4ADC-842B-16446593B5BE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a0461156abae393a6e10b63c02186cf4dc9c9d19","datavalue":{"value":{"entity-type":"item","numeric-id":3217618,"id":"Q3217618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48c44d0e571679b2453de1bee6a9311d904a45fe","datavalue":{"value":{"amount":"+0.8324581384658813","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":"Q685373$98314A15-AF26-4C4E-AE85-05A61DF7A2F5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Efficient constructions of test sets for regular and context-free languages","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Efficient_constructions_of_test_sets_for_regular_and_context-free_languages"}}}}}