{"entities":{"Q1104111":{"pageid":1114863,"ns":120,"title":"Item:Q1104111","lastrevid":49176883,"modified":"2026-01-06T17:22:54Z","type":"item","id":"Q1104111","labels":{"en":{"language":"en","value":"Rational index of context-free languages in exp \\(\\Theta(^ p\\sqrt{n})\\) and \\(n^{\\Theta((\\ln n)^{1/p})}\\)"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4055077"}},"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":"Q1104111$4EBBF517-8CEE-4686-ADE0-C847ADA9DE79","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eac38c11bde73e9e8823ad5e7152795e37f3be6a","datavalue":{"value":{"text":"Rational index of context-free languages in exp \\(\\Theta(^ p\\sqrt{n})\\) and \\(n^{\\Theta((\\ln n)^{1/p})}\\)","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1104111$7920D949-D2C5-4D58-BA86-8FB3AFBDD452","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"cfb17789bf5f8a22c8239b4e50ffbfe460cb4165","datavalue":{"value":"0646.68091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104111$968B1C67-8E7F-4796-88D6-6A439920E01D","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e96dee54a27f662569a19c0dcdf331309f995b5","datavalue":{"value":"10.1016/0304-3975(88)90038-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104111$E766D01B-45FE-4CC2-906E-2BEB9F89D553","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d3b8793ccb6de74c6dbc3b24cea8b3d2ca44dc5","datavalue":{"value":{"entity-type":"item","numeric-id":1020638,"id":"Q1020638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104111$CC410F5C-E0CD-4E35-89FE-17E35B95F720","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"da1e6db76af31c409fabe4fd53ecae531c40350e","datavalue":{"value":{"entity-type":"item","numeric-id":1104110,"id":"Q1104110"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104111$A89C6E78-34B4-43F4-829C-6B5E3BBA8BCD","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":"Q1104111$9EB742F1-92B6-49E3-AF56-F1C179A33CAD","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":"Q1104111$FDFD4C97-59A3-45A2-90F8-AF5989EAD4EC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ba88cc4a2de58df50632bef80afa2c90d28f5a05","datavalue":{"value":"There are many ways to measure the complexity of languages. Rational index, introduced by \\textit{L. Boasson} and \\textit{M. Nivat} [C. R. Acad. Sci., Paris, S\u00e9r. A 284, 559-562, 625-628, 703-705 (1977; Zbl 0359.68095, Zbl 0359.68096, Zbl 0354.68107)], is one of them and behaves well when combined with rational transductions: if \\(L\\geq L'\\) (i.e., there exists a rational transduction \\(\\tau\\) such that \\(\\tau(L)=L')\\), then the rational index \\(\\rho_ L\\) of L provides an upper bound on \\(\\rho_{L'}\\) since  \\[  \\exists c\\in {\\mathbb{N}}^*\\quad \\forall n\\in {\\mathbb{N}}^*: cn(\\rho_ L(cn)+1)\\geq \\rho_{L'}(n).  \\]  Thus we define the family \\underbar{Pol} of languages whose rational indexes grow less than polynomial, and the family \\(\\overline{Exp}\\) of languages whose rational indexes grow more than exponential functions.    It was conjectured by \\textit{L. Boasson, B. Courcelle} and \\textit{M. Nivat} [SIAM J. Comput. 10, 284-296 (1981; Zbl 0469.68083)], that all context- free languages belong to \\underbar{Pol} or \\(\\overline{Exp}\\). The aim of this paper is to show context-free languages whose rational indexes are exp \\(\\Theta(^ p\\sqrt{n})\\) and \\(n^{\\Theta ((\\ln n)^{1/p})}\\) proving thereby that this conjecture is false. The results and most of the proofs appearing in this paper are those of the authors' thesis (Univ. Paris VI, 1981).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104111$9C3EED25-5099-4D2C-A3A7-F2BE9430FECA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104111$DCCC157F-5E37-45DA-B5D5-84AA7706B22B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"fdd9498216d1fd2eff80e5a7d18782b649eb7b2f","datavalue":{"value":"68Q25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104111$095C034A-2455-4B42-A64A-9E93B7A44A95","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"f5048756bb678ef8ce2f9df89a9ef2aacc36f033","datavalue":{"value":"4055077","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104111$6EB5F8D2-3EE4-469A-83F3-0266E0B0208E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60ba0285a0ebf2b2f7ee81aae5f6587c1e83c216","datavalue":{"value":"complexity of languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104111$20BA1535-F17F-4FB1-B5AB-255713626809","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"795414f846fccd6517b35b46d219d01dfd08d3da","datavalue":{"value":"context-free languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104111$25F8B813-482F-4440-84A6-390BA973AD6E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a43c1244bff3c576688b1ee66f7cc7cae8669503","datavalue":{"value":"rational indexes","type":"string"},"datatype":"string"},"type":"statement","id":"Q1104111$E70D2BF2-A774-45AF-8D58-55BF7591CF59","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":"Q1104111$CB611702-303B-4D4C-8D00-1FDDF01C1A55","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"6fab7bf9fe20ef6c013fa3827a7ee0f4f8043641","datavalue":{"value":"https://doi.org/10.1016/0304-3975(88)90038-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1104111$C5E0618B-6002-4057-AC3B-E066E4AC2722","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"cb19accb9836fe2f7899ab33e9f49b27e661038c","datavalue":{"value":"W1967175417","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1104111$2BC41994-6F87-41D9-BCE8-91A423E898E2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3632afaf7c9124694de853efafd5cd84e2a50881","datavalue":{"value":{"entity-type":"item","numeric-id":3859267,"id":"Q3859267"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104111$B24AF593-9636-4DD3-85FD-4B1BEB303108","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"eabb396d9f70544bae83f5e9c56b9001e98bfc53","datavalue":{"value":{"entity-type":"item","numeric-id":3686060,"id":"Q3686060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104111$6BE25B92-CF02-40B5-BF34-C530EB183A63","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"66795201b183e6e2001097075f54c3307f8e48be","datavalue":{"value":{"entity-type":"item","numeric-id":4125811,"id":"Q4125811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104111$6C76843E-A55C-4A47-B2A5-97AFAA6A24BB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7161b0f708680544b5d12f51c9eb1272320ec640","datavalue":{"value":{"entity-type":"item","numeric-id":3923626,"id":"Q3923626"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1104111$A713D045-209A-4378-A113-870332DB19B0","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1d7dd307bb806098c1bf955ae7d55b531e949e74","datavalue":{"value":{"entity-type":"item","numeric-id":3479535,"id":"Q3479535"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aac7e0988d45d9600b5949b8ea22366ec250ded5","datavalue":{"value":{"amount":"+0.9004983305931091","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":"Q1104111$11A0994E-2790-418F-95C2-9588F282298C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"980014ffe0ab5ced3ab486bfcc2f9a34d1593965","datavalue":{"value":{"entity-type":"item","numeric-id":1184983,"id":"Q1184983"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"169e36785b69ebbe2e9d47609056569905e240a9","datavalue":{"value":{"amount":"+0.8830979466438293","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":"Q1104111$CDC61C78-C82F-426A-83A9-D88C11361DDC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7bc3fc53988381691400b375d262c44703b775ba","datavalue":{"value":{"entity-type":"item","numeric-id":327306,"id":"Q327306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1894ec0771102d59d60bbc148e7194702a7dee2d","datavalue":{"value":{"amount":"+0.8784698247909546","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":"Q1104111$3DDF982F-663D-492E-80E0-8716191BFC12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"31ea660b16d6983d804fa363a1c5756e9c77a9cf","datavalue":{"value":{"entity-type":"item","numeric-id":1095670,"id":"Q1095670"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cdca122584a53b8a6807bd4b55173b3453728cf2","datavalue":{"value":{"amount":"+0.8418951630592346","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":"Q1104111$024E3EFC-69CC-47DE-94AA-5B2943F2FB86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a749d794caf5490e72a5f343bcd4620ee0da9f1b","datavalue":{"value":{"entity-type":"item","numeric-id":1823002,"id":"Q1823002"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1ca86eebcfb59757b35fb5304723ccfd4abeca75","datavalue":{"value":{"amount":"+0.7979421019554138","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":"Q1104111$6B927164-8900-49D7-B181-7FE360D40255","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1104111","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1104111"}}}}}