{"entities":{"Q1694683":{"pageid":1705424,"ns":120,"title":"Item:Q1694683","lastrevid":72053088,"modified":"2026-04-14T02:21:09Z","type":"item","id":"Q1694683","labels":{"en":{"language":"en","value":"Universal partial words over non-binary alphabets"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6834902"}},"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":"Q1694683$E313C84E-4A0A-48B3-8B1D-4A4D56D9D0E8","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9c74303617a82eb9a5b460fefd9982d194303407","datavalue":{"value":{"text":"Universal partial words over non-binary alphabets","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1694683$48078DC2-2A07-41A6-B7B1-53DC4048E2EF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8d3bc49a408ca3ca4f477b5bbe78ec112f931dab","datavalue":{"value":"1394.68271","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1694683$6A5A84D9-4DB9-42CB-8492-0838406046AC","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"cefe7db07d3ee7f53b654ff2c45570236608e27a","datavalue":{"value":{"entity-type":"item","numeric-id":1694678,"id":"Q1694678"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$3F1D630B-292A-4C75-85D6-3489551A315F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d7a0eb0a4a77b0a75df8d553fc8098d9acb8f7be","datavalue":{"value":{"entity-type":"item","numeric-id":1625792,"id":"Q1625792"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$6C2E7568-D8C6-4EF0-85AD-060D89A58E93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2eda7681960441fa3d94dc8357319b90d163f81a","datavalue":{"value":{"entity-type":"item","numeric-id":1694679,"id":"Q1694679"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$0A5AA00D-2171-4795-80D3-E9FF7562C0AE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bced63c6ac43722e11201cc9ac85fe512b55f94d","datavalue":{"value":{"entity-type":"item","numeric-id":1694680,"id":"Q1694680"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$26F20772-298C-4D63-B208-E00233CB3C1C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"06a7aaed998aeed6d5ac2a2e1821dfb8f94f2f5a","datavalue":{"value":{"entity-type":"item","numeric-id":1694681,"id":"Q1694681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$48D9DA2F-EEE3-44D5-B303-27761492398E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0261533a389da0dd337415fcb65fc331908de3e2","datavalue":{"value":{"entity-type":"item","numeric-id":1694682,"id":"Q1694682"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$B4C0CB23-86EA-457B-A2C3-6D5E6976FA25","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ff9f8e8b5a2ea4efc4c9cfe1ca07106c666e48b3","datavalue":{"value":{"entity-type":"item","numeric-id":2073189,"id":"Q2073189"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$9C5B945A-5B6F-47A0-81C7-2B585F8BAA08","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":"Q1694683$AE7695A1-DE5F-4737-97F7-046D99B9BFD8","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a56c33c49680ed15bf9438494fe87a6286c086fc","datavalue":{"value":{"time":"+2018-02-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1694683$B29B663C-772B-43B5-8F51-75C8D571F2F4","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"183bae640d06199065f0ab8d59a4ae7cf12f9e5c","datavalue":{"value":"https://arxiv.org/abs/1611.03928","type":"string"},"datatype":"url"},"type":"statement","id":"Q1694683$ED573679-382B-4B76-8365-1951AA2891C9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"90f1a0a11827d3be2a6490bf4dd0b06349f3e14a","datavalue":{"value":"A de Bruijn word of order \\(n\\) over an alphabet \\(A\\) is a cyclic word that contains each word of length \\(n\\) over \\(A\\) as a factor exactly once. Every de Bruijn word can be linearized by appending to the right its first \\(n-1\\) characters. The resulting word is called a \\textit{universal word for \\(A^n\\)}. It is well known that de Bruijn words (and hence universal words) exist for every \\(A\\) and every \\(n\\). In this paper, the authors investigate the case of partial words. A partial word is a word over \\(A\\cup \\{\\diamond\\}\\), where \\(\\diamond\\) is a wildcard that matches any symbol of \\(A\\). A partial word \\(u\\) is a factor of a partial word \\(v\\) if \\(u\\) is a factor of \\(v\\) in the classical sense, after possibly replacing some \\(\\diamond\\) form \\(v\\) with letters of \\(A\\). For example, over \\(A=\\{0,1\\}\\), \\(01\\diamond 1\\) is a factor of \\(1\\diamond 1\\diamond 110\\).  A \\textit{universal partial word} for \\(A^n\\) is a partial word that contains each word of \\(A^n\\) as a factor exactly once. For example, \\(\\diamond \\diamond 0111\\) is a universal partial word for \\(\\{0,1\\}^3\\). This notion has been introduced in a paper of \\textit{H. Z. Q. Chen} et al. [Electron. Notes Discrete Math. 61, 231--237 (2017; Zbl 1378.05112); Discrete Math. Theor. Comput. Sci. 19, No. 1, dmtcs:3690, 19 p. (2017; \\url{doi:10.23638/DMTCS-19-1-16})].  A universal partial word is called \\textit{trivial} if either all or none of its characters are \\(\\diamond\\). The problem investigated in the paper is to determine the existence of non-trivial universal partial words for any \\(n\\). Chen et al. proved [loc. cit.] that non-trivial partial words exist for every \\(n\\) over a binary alphabet (containing a single \\(\\diamond\\)).  The authors show that for \\(|A|\\geq 2\\) and \\(2\\leq k\\leq n/2\\) no universal partial word exists for \\(A^n\\) having the form \\(u\\diamond^k v\\), for (possibly empty) words \\(u\\) and \\(v\\).  A universal partial word for \\(A^n\\) is called \\textit{cyclic} if its first and last \\(n-1\\) characters are the same and non-overlapping. The authors prove that every non-trivial non-binary partial word is cyclic (while the aforementioned word \\(\\diamond \\diamond 0111\\) is an example of a non-trivial binary universal partial word that is not cyclic).  The last main result of the paper is that for any \\(A\\) of even size, there exists a non-trivial universal partial word for \\(A^4\\), and give an explicit construction of words of this type.  The paper ends with several open questions, the main of which concerns the existence of non-trivial universal partial words over a non-binary alphabet for \\(n\\geq 5\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1694683$BCAA644D-D04B-42B8-BFBA-571B31FC1A43","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"130d97dc1ca643e8efa64f9b07a28af4e0a2454b","datavalue":{"value":{"entity-type":"item","numeric-id":243831,"id":"Q243831"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$F3E3DDCF-9AFC-4EA2-B1CF-C3346EA4486F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1694683$05116AD5-4C15-4C01-B1BF-4E3709C8DA6E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"42f84640476c1a5112c60436ed1e2d207197524e","datavalue":{"value":"6834902","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1694683$7F67DCD0-1E4E-4412-9FAC-F63B526EBA70","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8967d0a934eaa6194b5afbe1fbb4e78c8127645d","datavalue":{"value":"combinatorics on words","type":"string"},"datatype":"string"},"type":"statement","id":"Q1694683$E9B18A7F-E115-40E3-871C-DEAF7E21CF52","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8933757e6aceba07b56cec611cc92bcae172e5ae","datavalue":{"value":"universal cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q1694683$C3BA2D27-73E8-40E0-84FC-8D393140CCD6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"aa3526be5d4d54138d41c11844ac017bc2eedfdb","datavalue":{"value":"partial word","type":"string"},"datatype":"string"},"type":"statement","id":"Q1694683$2967404A-6B23-4AAC-9F60-1B5045210BAA","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"ead654dcb8d23a4f30385b8f099b2a14c639ba7e","datavalue":{"value":"Q115036507","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1694683$C932CAF7-0B43-4F2F-A6DC-EC9075DFA26E","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":"Q1694683$2072D8BE-1779-4E47-AC1B-74E44053BB9E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"70172e35d6a249422f2ddac89ee6512ecfe34a03","datavalue":{"value":"W2566543723","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1694683$6E6EC17C-1EE1-4A03-893F-B9D618F03A35","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"cbb678d5ff3df1e9de741cdb601c587a1d4e37ae","datavalue":{"value":{"entity-type":"item","numeric-id":551232,"id":"Q551232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$AAE9439A-4A44-40F4-9A3C-8BFB8B793729","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82953dad0f697c5abfeae8cd3f750bf5c4608fc1","datavalue":{"value":{"entity-type":"item","numeric-id":733729,"id":"Q733729"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$AF64C539-E41C-46C8-B1B0-0475D92A34E0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4bf60d8bf8bd6dab3ce7817079a781467c85b384","datavalue":{"value":{"entity-type":"item","numeric-id":1678101,"id":"Q1678101"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$E716A454-1822-4CD2-A43E-B58231531B80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0f4ccc384cf4cdf57fc12284b7dfb019afe5aac3","datavalue":{"value":{"entity-type":"item","numeric-id":4558959,"id":"Q4558959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$06DC2DD8-814A-42D0-93A9-70B7081141F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61d80e91c73bc0301cc40457009380a612f4a5c1","datavalue":{"value":{"entity-type":"item","numeric-id":1208348,"id":"Q1208348"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1694683$D0D49713-F1F2-4CAA-9CAC-E0F26CA225D4","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7abf9f5de6067bd312abf1e989b797442892b0a7","datavalue":{"value":"10.1016/J.TCS.2017.12.022","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1694683$CA9ADD96-624B-4B6F-97AE-7C70DB5C2F67","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9ce38ca0a622649e82db782449aa6e6c9b503f65","datavalue":{"value":{"entity-type":"item","numeric-id":1689916,"id":"Q1689916"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"14f14f911b6cd81338ff230dd847bad1212d2501","datavalue":{"value":{"amount":"+0.8464123606681824","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":"Q1694683$5FB2B3BA-3F49-47C6-99B9-13C780F59456","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d2c8cc2220734c2421aeb55b4809aadd6d00b63d","datavalue":{"value":{"entity-type":"item","numeric-id":4558959,"id":"Q4558959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b91dd3545c88166c11a819799b7385e37131a2b4","datavalue":{"value":{"amount":"+0.8461352586746216","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":"Q1694683$D230C5D0-E41E-4A3F-A223-D6479C4C059B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a38b347c7f71d27b5e46823a6d1fd48b3e83daab","datavalue":{"value":{"entity-type":"item","numeric-id":3000493,"id":"Q3000493"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"31a894b5e9c780712257119e42cdf7d53edc7062","datavalue":{"value":{"amount":"+0.845914363861084","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":"Q1694683$026D065E-6DA2-41EC-A517-2D5567F0A029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f126dbb419b5b4bd7bb8a447be977c1628a72366","datavalue":{"value":{"entity-type":"item","numeric-id":3298125,"id":"Q3298125"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"655e2898362612debb76b0ed26ce7baf715cfa17","datavalue":{"value":{"amount":"+0.8061398863792419","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":"Q1694683$7EB790F6-1337-4222-B06F-4F6280AC2C65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"69e89b75b1b76a4d8a15d9a05e5d1fba25cc375c","datavalue":{"value":{"entity-type":"item","numeric-id":948072,"id":"Q948072"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f4f3e360fd9459c7ee62472e0f0d02b06f04498","datavalue":{"value":{"amount":"+0.788905680179596","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":"Q1694683$CD70EF31-8E4F-4BCB-B1A6-452CD636F60E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Universal partial words over non-binary alphabets","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Universal_partial_words_over_non-binary_alphabets"}}}}}