{"entities":{"Q1115632":{"pageid":1126381,"ns":120,"title":"Item:Q1115632","lastrevid":49246336,"modified":"2026-01-06T20:28:49Z","type":"item","id":"Q1115632","labels":{"en":{"language":"en","value":"A note on word chains and regular languages"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 4087047"}},"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":"Q1115632$B896FE97-3C46-47BB-BA2D-6CAC6B7D577B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"f2e58c7ba34eca9cd96aa78414a20f7ecb710bd6","datavalue":{"value":{"text":"A note on word chains and regular languages","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1115632$8AC7B326-F856-47ED-9923-5C52BD769CE3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ba728163a0dd5e0f30925dae8dcdbe0f95c4e7e0","datavalue":{"value":"0664.68074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115632$9F91AAA5-E755-4302-88FF-7247C88B24E1","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"95c4ef5f6aa981dd78a0b1b6ccbd0a02008cbcb4","datavalue":{"value":"10.1016/0020-0190(89)90167-1","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115632$DBC87849-DE4D-4F80-B1C6-1FF8EAB5703F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"658c7136c0391545c68b23080c38cccb4e43c874","datavalue":{"value":{"entity-type":"item","numeric-id":1115631,"id":"Q1115631"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115632$CF8A0673-D8EC-49F1-9B5B-6B3800E86FC9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"52fa7d44b58d0511cb8993765bd916aef86052d8","datavalue":{"value":{"entity-type":"item","numeric-id":63092,"id":"Q63092"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115632$727A050C-8552-49FB-83D9-919419C9D3A1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"7211ad5ca16eb0d22cd0051fff3d0f3af254ceb6","datavalue":{"value":{"time":"+1989-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":"Q1115632$98285B60-DDD2-4444-904E-7893EFC8E544","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"3e2966c26f79cb218aee26563ad9b16c9eaf857e","datavalue":{"value":"Word chains have recently obtained some attention. We present a result that connects word chains to regular languages. Namely, we derive the inequality: \\(\\ell (L_{\\leq n})/| L_{\\leq n}| \\leq 2+O(1/n),\\) where \\(L_{\\leq n}\\) denotes all words of length at most n that are members of an infinite regular language L, and \\(\\ell (L_{\\leq n})\\) is the length of a minimal word chain computing all \\(w\\in L_{\\leq n}\\). Finally, we show that even for two-letter alphabets there are words of length n that need \\(\\Omega\\) (n/log n) steps to be computed using word chains.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115632$41E8FAFB-EAB6-463A-A2AE-D015D66FD8F3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115632$8AF54F47-3931-474D-8BD2-225E5010A478","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"354ef76f1b09d44b1f855a2b1d72c7afd1ce2861","datavalue":{"value":"4087047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115632$380C064D-35A2-4715-8141-8DAF947C3BD1","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"06dfd8d897d1a8951b43e340a50e4caf09ac56ae","datavalue":{"value":"word chains","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115632$4E72C56C-A6E8-4C93-812D-220F9C5E152C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7142d39c3323636bd7cc377526eabf4365b5d436","datavalue":{"value":"regular languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q1115632$9C190271-8D84-4A01-83D9-2648293EE2E7","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":"Q1115632$6E2FF47B-92AB-4C97-BC6D-2EC743BC48BE","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"aed4071c4376216dc0de68700d35e5ded430d98d","datavalue":{"value":"https://doi.org/10.1016/0020-0190(89)90167-1","type":"string"},"datatype":"url"},"type":"statement","id":"Q1115632$7B92B454-2F1E-40EF-A12F-323A4DA087CD","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"9cbdaf9fd254140c66d20b62b0b842c8535aadda","datavalue":{"value":"W1989702828","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1115632$29DF5B8C-9BDD-4A85-AB78-03E1CAFFBBD3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"3fc22b47c42ba322f4bd830111391b026b40a348","datavalue":{"value":{"entity-type":"item","numeric-id":1108812,"id":"Q1108812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115632$B675C2E6-BA9F-4C84-8E8F-CC7DC534E150","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":"Q1115632$CD274546-ADF0-417A-A8B0-1471D356E3B9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b6d0ff209a8c00e6853b2c43b2e31810805788f0","datavalue":{"value":{"entity-type":"item","numeric-id":3935355,"id":"Q3935355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115632$C3437CEA-0C0C-4A27-BD78-9F3AE76085E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe2355482dbc37a911cde9b74ab32ffb5b6939f6","datavalue":{"value":{"entity-type":"item","numeric-id":3659988,"id":"Q3659988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1115632$3ACC0CD0-BD70-4B82-92E1-4A1B04B09B44","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e175c8f1fe687ae93bdf84a2fd46f27bef7879ec","datavalue":{"value":{"entity-type":"item","numeric-id":1108812,"id":"Q1108812"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6dab30eb5dd4fbf4283e7cb77d562448ec003bad","datavalue":{"value":{"amount":"+0.8353327512741089","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":"Q1115632$817DAEF8-7DD1-468B-A273-B8B84FA73414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8259b9dca38aa36ccdfa3451042e05b5b4838ea6","datavalue":{"value":{"entity-type":"item","numeric-id":915454,"id":"Q915454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6f0027b9111ff8d01503318b3272b59f51cea6b8","datavalue":{"value":{"amount":"+0.7935760021209717","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":"Q1115632$C087188A-418D-485E-8784-562DE83B7E4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"91f9336828fe0905620b3a193d910b95b46df855","datavalue":{"value":{"entity-type":"item","numeric-id":582129,"id":"Q582129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e30c5084e7d56c7e5093a00c6a2f77bfcc3c5b0","datavalue":{"value":{"amount":"+0.7693284153938293","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":"Q1115632$C4CD56EE-75FE-4277-8A3E-C7B6E2AE8614","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9936ca3d7567de882053b182cd3c75f417d6f622","datavalue":{"value":{"entity-type":"item","numeric-id":1201862,"id":"Q1201862"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7d5a7ca71b22c19043b813eeee7381e4b3a169aa","datavalue":{"value":{"amount":"+0.7071213722229004","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":"Q1115632$8B27ACC2-4EC6-4BB8-9CD1-42AAF807CE27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81e70565dd51c1863d3b4f1952f394c78cedcccc","datavalue":{"value":{"entity-type":"item","numeric-id":4266490,"id":"Q4266490"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd5852bc3b14873bdb080dff4156c3dc95c9d695","datavalue":{"value":{"amount":"+0.7055732607841492","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":"Q1115632$A730E0F6-33F6-46BA-9651-0CD0DD7B3E5C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1115632","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1115632"}}}}}