{"entities":{"Q792097":{"pageid":793945,"ns":120,"title":"Item:Q792097","lastrevid":48696601,"modified":"2026-01-05T15:42:09Z","type":"item","id":"Q792097","labels":{"en":{"language":"en","value":"Context-free complexity of finite languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 3852451"}},"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":"Q792097$16800051-7FD3-4380-AA15-B2EDCC0E2D77","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"88ca1be86710d1fe943dda1c2966ff4784a5422d","datavalue":{"value":{"text":"Context-free complexity of finite languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q792097$F19AE174-2243-425C-BCE6-AD9EF28A92D2","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"518a78be69f34417917ab4bdb2bec02f68cbb5d4","datavalue":{"value":"0536.68065","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792097$64A3725F-D28D-453C-BA48-F0C3DC9ED998","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d7efb6134be89239f8e417c865e7e760bd42fc95","datavalue":{"value":"10.1016/0304-3975(83)90024-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792097$65A83DB8-9958-4F6F-B880-BF436FB5F35A","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"7a701345616fc92cd590115d21c0168f89580e75","datavalue":{"value":{"entity-type":"item","numeric-id":787677,"id":"Q787677"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792097$223861FE-47DD-4FB6-9369-AB0E3572CA55","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41546a3a5be69a76c72642a579fbcf9b163bde60","datavalue":{"value":{"entity-type":"item","numeric-id":301899,"id":"Q301899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792097$77A3F688-99AF-4F44-9978-E7D93E6EC4F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"87b50d9d925c1d915b90d3836e3c8221c58fe283","datavalue":{"value":{"entity-type":"item","numeric-id":582130,"id":"Q582130"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792097$C1F6DC26-D8D2-4609-8735-99D9E0E07968","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":"Q792097$0E90EF9C-AAAB-43CF-B610-7A9903F65601","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2ee0f220147ae8bc749a64db56839865dbc4f127","datavalue":{"value":{"time":"+1984-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":"Q792097$17D3FEE5-EA81-4FA6-B145-AA987BF77AE3","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"fa9d29d5122e9c962c2f944694a45a3d21847f05","datavalue":{"value":"Necessary conditions are given for an infinite language to have a sublinear complexity. To achieve the main result, characterizations for the number of productions of finite languages are derived. The main result: Let L be an infinite language over \\(\\Sigma\\) with sublinear complexity. Then for all k there is an n(k) and there are words \\(x_ i\\), \\(y_ i\\), \\(z_ i\\), \\(i=1,...,k,\\) such that for all \\(n>n(k)\\) one of the following two cases holds:  \\[  (1)\\quad(x_ i,z_ i)\\neq(x_ j,z_ j),\\quad y_ i\\neq y_ j\\quad for\\quad i\\neq j\\quad and\\quad \\cup^{k}_{i=1}x_ i\\{y_ 1,...,y_ k\\}z_ i\\subseteq L_ n,  \\]   \\[  (2)\\quad x_ i\\neq y_ i\\quad for\\quad i=1,...,k\\quad and\\quad \\{x_ 1,y_ 1\\}...\\{x_ k,y_ k\\}\\subseteq L_ n.  \\]","type":"string"},"datatype":"string"},"type":"statement","id":"Q792097$061350A5-1507-4EAB-9494-968D346F9224","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792097$CCB2A88D-07C7-4785-A0D0-1E66D7407AFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792097$2F23EE5B-2257-4EB8-A5F2-C4C624D7D631","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"e3a27e485b46c4479262505ea068fc45901b28c6","datavalue":{"value":"3852451","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792097$19BDC287-5ECB-4F91-981C-4E4ECD10F947","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"53ebfa387ccc83bec4cf2d9293d7d54c9cf4fb5e","datavalue":{"value":"infinite language","type":"string"},"datatype":"string"},"type":"statement","id":"Q792097$EBC5094C-501F-4B22-8311-65A0EFB574B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4029fdf7b8da7e3f7d5cb1fb0b164c252f0b6458","datavalue":{"value":"sublinear complexity","type":"string"},"datatype":"string"},"type":"statement","id":"Q792097$550EB181-2533-468E-AC67-BDEB2D992922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d8cbdde0b26d13a3e0806bd87c89d52fe63da40b","datavalue":{"value":"number of productions","type":"string"},"datatype":"string"},"type":"statement","id":"Q792097$D9B2297E-50A9-4EBD-B414-F141EAEAA257","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"fa27dc886ab92c1e1b22587b18bf236db8545e38","datavalue":{"value":"finite languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q792097$FB633AA2-C25E-47DC-A07D-0764C2072F51","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":"Q792097$67336226-95F4-472D-9984-C844CC5B72DF","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"5ded61f5ab392ae6ce798b8cced5494cf0284355","datavalue":{"value":"https://doi.org/10.1016/0304-3975(83)90024-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q792097$128F86E8-C346-4FE8-A079-61F0A6D97543","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"4a129ccdaac2fcaa307fadaed33dbef96d01b139","datavalue":{"value":"W2023738367","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q792097$98DE6AE6-FDCC-4567-ADB2-C7C144559D42","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d1bc03f64e339122c1508a9acd09eab6a110623","datavalue":{"value":{"entity-type":"item","numeric-id":1157180,"id":"Q1157180"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792097$D2F73916-62B5-4E06-9B14-2C76AAF8BC8F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a07ca75c7a05c977511c60d16886bb9357e8a1e6","datavalue":{"value":{"entity-type":"item","numeric-id":1157179,"id":"Q1157179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792097$3CF17BD0-DE3D-4287-AF23-6C9CF953D0EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5af7139c65837eb8115c64cb4d4e1bbefc86dded","datavalue":{"value":{"entity-type":"item","numeric-id":4198075,"id":"Q4198075"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q792097$FB3C8BB0-31C7-4EE8-8B43-17B1B7FE7FCE","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"579f428a62999347c2a08ad8a8dd66d99c484a99","datavalue":{"value":{"entity-type":"item","numeric-id":1098318,"id":"Q1098318"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"832108f10d17d009158f511ce559a02b5d585ad2","datavalue":{"value":{"amount":"+0.8256669640541077","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":"Q792097$9CD56AAA-F645-4DCA-85B9-E3A86A408B15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2bff3cf03182ff81e41bba6dd9a5f0beede82629","datavalue":{"value":{"entity-type":"item","numeric-id":4937901,"id":"Q4937901"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7cfde60cea624ee6ed5235b30fc12104edd81a07","datavalue":{"value":{"amount":"+0.7946150302886963","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":"Q792097$F3DD9C05-4E65-496F-87AA-142B0A021939","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe7b260ddbb3cf7f7a0c394a722820f4cf04633d","datavalue":{"value":{"entity-type":"item","numeric-id":4581961,"id":"Q4581961"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d81d8d9062bb9a9f8a7eb9ad055af5625858124","datavalue":{"value":{"amount":"+0.7929511666297913","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":"Q792097$585FEB9C-BB89-4424-910C-C8F7934459F9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"824ebc53bf62091fc09d3134b4c9685efccebbd3","datavalue":{"value":{"entity-type":"item","numeric-id":1057070,"id":"Q1057070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac85f7751f7cf48385ea4e9ffdd6c83ea2c9da02","datavalue":{"value":{"amount":"+0.7847318649291992","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":"Q792097$A5CBE6A3-391C-4E21-8045-8BED02300241","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"360cf72050d77c757319711562a468dd562196a6","datavalue":{"value":{"entity-type":"item","numeric-id":777997,"id":"Q777997"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1111fb9954b5910a637f9a58925a5ce99ff437e7","datavalue":{"value":{"amount":"+0.7688688635826111","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":"Q792097$E5395C93-011D-48B0-9130-2E126952989E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:792097","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:792097"}}}}}