{"entities":{"Q2358680":{"pageid":2369423,"ns":120,"title":"Item:Q2358680","lastrevid":73996887,"modified":"2026-04-14T17:59:53Z","type":"item","id":"Q2358680","labels":{"en":{"language":"en","value":"Prefix-suffix square reduction"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6731755"}},"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":"Q2358680$79F297AD-D4BD-4413-9F29-A1127EAF7968","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"86a495315289060d3d1189b6287ec592aa53ada9","datavalue":{"value":{"text":"Prefix-suffix square reduction","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2358680$CA334748-FC21-47CF-848A-6E7B7CE830F8","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b7174c2c21d3abdf1cc979b6324dc69ec3d3b9bd","datavalue":{"value":"1376.68084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2358680$97B18AA8-0287-475F-8A0D-79C6CB367F97","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0fdc6a4e4203654493f4762413f833a7393c6030","datavalue":{"value":{"entity-type":"item","numeric-id":293297,"id":"Q293297"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$1291BB96-05EA-479E-9908-A9CD8350B2E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"8cca12677f2478e2b66d7a7a0ac2c7062b971caf","datavalue":{"value":{"entity-type":"item","numeric-id":234453,"id":"Q234453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$90687783-CAB9-47DF-B375-AA503C6F63F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c254a9f0ade01143226c68d37b77db15638e104d","datavalue":{"value":{"entity-type":"item","numeric-id":170454,"id":"Q170454"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$8BA576CD-FB18-4FF3-B156-F73B04E409FA","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":"Q2358680$DDC0185F-BD8E-45A8-8B2A-364723C4ABF9","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"92d82bc79e45dbea4d44c115656eba4b7d7ac07a","datavalue":{"value":{"time":"+2017-06-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2358680$36F55C63-867B-41D3-B78E-C9A12834B512","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ec52654b813775710f76e9819227fa9efb1c20e9","datavalue":{"value":"The paper introduces an operation on words called the ``prefix-suffix square reduction''. This operation could be seen as the inverse of another operation on words, already studied in the literature, known as ``prefix-suffix duplication''.  A ``square'' is a word of the form \\(uu\\) with \\(u\\) a nonempty word. A ``prefix'' (resp. ``suffix'') of a word \\(w\\) is a word \\(u\\) such that \\(w = uv\\) (resp. \\(w = vu\\)) for a certain word \\(v\\).  The ``prefix square reduction'' of a word \\(w\\) is defined as the set of all possible words obtained by replacing a prefix of \\(w\\) that is a square by one of its halves, that is,  \\[  \\{ uv \\; | \\; w = uuv \\text{ with } u \\text{ nonempty} \\}.  \\]  The ``suffix square reduction'' is defined symmetrically. The ``prefix-suffix square reduction'' of a word \\(w\\) is just the union of the two previous sets.  The authors define also the ``prefix-suffix square reduction'' of a language as the union of the prefix-square reductions of all words in the language.  Bounded versions of these operations are also defined. Namely, given a positive integer \\(p\\), the ``\\(p\\)-prefix square reduction'' of a word \\(w\\) is the set  \\[  \\{ uv \\; | \\; w = uuv \\text{ with } u \\text{ nonempty and such that } |u| \\leq p \\}.  \\]  In a similar way the authors define the ``\\(p\\)-suffix square reduction'' and the ``\\(p\\)-prefix-suffix square reduction'' of a word as well as the ``\\(p\\)-prefix-suffix square reduction'' of a language.  The authors prove several results concerning the complexity (in time and space) of the membership problem of a given language and the closure properties of some special classes of languages (regular, linear, context-free), both for the bounded and the unbounded case.  Finally, the unbounded (resp. bounded) ``primitive prefix-suffix square root'' of a word \\(w\\) is defined as the word that can be obtained from \\(w\\) by iterated unbounded (resp. bounded) prefix-suffix square reductions and is irreducible, i.e., no further prefix or suffix square reduction can be applied. It is shown that, while the language of bounded primitive prefix-suffix square roots of all words over an alphabet is always regular, for the unbounded case, this language is regular only when the alphabet contains a single letter.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2358680$73C436BD-1115-4579-B30C-3388F195A312","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"db4ce77af0a816fc29813ca08d6ee903c4d59aea","datavalue":{"value":{"entity-type":"item","numeric-id":590718,"id":"Q590718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$E282310E-602B-4038-AB72-49A08FC0CA3A","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2358680$9F8AB7E5-FE25-4A09-8E10-5D178247ECA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"23149673dde05813672617e26c3fcb130092997c","datavalue":{"value":"68R15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2358680$619AF866-18C7-41E5-848C-06842509473A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"304bb663996decadeae918c60798c938abcb8555","datavalue":{"value":"6731755","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2358680$218AF2F3-C450-43FB-8C14-0F118E18FB73","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"622c561266634915632437699421c14fc4a520d7","datavalue":{"value":"duplication","type":"string"},"datatype":"string"},"type":"statement","id":"Q2358680$2EC40CA7-C30E-4EE1-8A5A-14E2574BDB46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5fce20861a713a40d87b8fc27b250093e6eb334b","datavalue":{"value":"prefix-suffix square reduction","type":"string"},"datatype":"string"},"type":"statement","id":"Q2358680$34E513D7-6C60-494C-BA5B-3BCAA4EB758D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"00cebf5a2a0fd17847d37f542d335270128a6d24","datavalue":{"value":"primitive square reduction root","type":"string"},"datatype":"string"},"type":"statement","id":"Q2358680$D233C381-F47F-4B65-9F89-F886E7032FA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b30b88dd7d8d4d3a542dd1829bf3206a53951e76","datavalue":{"value":"formal languages","type":"string"},"datatype":"string"},"type":"statement","id":"Q2358680$C422FCBB-594F-4493-B7C8-9EBD9065C23D","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":"Q2358680$42C5F38C-2D91-4644-BEA3-C4AD6CB1302D","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1349d0f12f9dc42342cf94c59153cbd6b0926de6","datavalue":{"value":"https://doi.org/10.1016/j.tcs.2016.12.005","type":"string"},"datatype":"url"},"type":"statement","id":"Q2358680$27B013C3-AFE4-4AF7-A242-EA3F33A9AD00","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e4b266aabed1543bace88239f2102a825aa03bbd","datavalue":{"value":"W2566668411","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2358680$C12631B7-6A76-479E-8340-0E6AA2C50EE6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"70b6faaa9be35af7ac708f598fc20751dca8b76d","datavalue":{"value":{"entity-type":"item","numeric-id":840765,"id":"Q840765"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$02395D1D-0F43-4CB2-8E8D-281BB35B2FB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"83ed8fbef3d6192e25de21d5c87508bd13ee9be3","datavalue":{"value":{"entity-type":"item","numeric-id":4940888,"id":"Q4940888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$4480A78B-76FB-446B-BA89-52D5906024F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"89d0bf4c058f72232bf703fdb5c88b85f69a4c50","datavalue":{"value":{"entity-type":"item","numeric-id":3192263,"id":"Q3192263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$F141B3CF-246B-42CD-9587-24A1C340170C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"61cdbf6c3c3026f45d71516d0e1bb4b64c8f39a1","datavalue":{"value":{"entity-type":"item","numeric-id":5744129,"id":"Q5744129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$B8B6AD98-623C-4ECF-BE37-49CD91B4C575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"33af900e84f2b9a3686e17823d1d277a76892a11","datavalue":{"value":{"entity-type":"item","numeric-id":2949834,"id":"Q2949834"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$4488B3DB-8865-4B88-8AA7-9043FD7FBDB4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b9c72dc8ed66014cf9d41e6363cbe3b45a689906","datavalue":{"value":{"entity-type":"item","numeric-id":2453545,"id":"Q2453545"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$4E0B749C-A945-4975-9506-B08C5647B716","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2689b5ae4ae8f32a995c9c8ae368f0952503d536","datavalue":{"value":{"entity-type":"item","numeric-id":4808652,"id":"Q4808652"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$AB7F527F-8840-44BC-855C-B047455AD0DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1643bdee0011f32959440e35ffcb03e846ecb85b","datavalue":{"value":{"entity-type":"item","numeric-id":5696964,"id":"Q5696964"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$1FEAADEA-439A-4238-9FBE-6A37E61191BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"556cb613c7df43942109fb242317628638eae7d9","datavalue":{"value":{"entity-type":"item","numeric-id":3617061,"id":"Q3617061"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$792D39C4-F05A-4CA4-9BAE-73F6AA0B485E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2d980f88bbd6d2d964c2ce9c8b671d6556f19945","datavalue":{"value":{"entity-type":"item","numeric-id":5428240,"id":"Q5428240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$2B2A1E60-1D98-40C0-945E-B07171D05EFA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3479b1b8ce1eb8a8699c52a172d26d4d947366b0","datavalue":{"value":{"entity-type":"item","numeric-id":4298260,"id":"Q4298260"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$DB696D70-FC39-414F-887A-A678190D43EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"fe929f01fa86af5ec1780a3fd0d8f9ac3346a63b","datavalue":{"value":{"entity-type":"item","numeric-id":4714446,"id":"Q4714446"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$972E191C-5E61-4023-8D73-C3DDB3B5C9B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f5d6b0b45f53257ddbc7d644a7c4503779a6a275","datavalue":{"value":{"entity-type":"item","numeric-id":2735959,"id":"Q2735959"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2358680$5E59AA0B-52D1-4AE6-BEC3-0153F52DC148","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"91a3f42743f8565b3291dca1b9e254d042be1154","datavalue":{"value":"10.1016/J.TCS.2016.12.005","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2358680$51219C68-97D6-47CE-B556-0EBEB8530225","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1dd8bf8d95fabb0c975848a8f8d73bdbd05cb8cd","datavalue":{"value":{"entity-type":"item","numeric-id":5217116,"id":"Q5217116"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3b9899a657b3fa233ac7fbb3d373387d52f5954f","datavalue":{"value":{"amount":"+0.9157543182373048","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":"Q2358680$189114A9-B932-4985-B3F1-0A991475B55A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6b7551d0aef2d0de9edade57024bf624c1597401","datavalue":{"value":{"entity-type":"item","numeric-id":3449365,"id":"Q3449365"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7b3b2cc5be88bc3d07f08169e8c37460bdd7c8e7","datavalue":{"value":{"amount":"+0.8361426591873169","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":"Q2358680$B7A80EF7-C48D-4FA6-B0D3-38827EF6988C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f6033d9dc7b96d3526e31538770c42c4a0762b03","datavalue":{"value":{"entity-type":"item","numeric-id":5428240,"id":"Q5428240"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d09e6626e5a3a4221a17b0026f783953a922155b","datavalue":{"value":{"amount":"+0.8022946715354919","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":"Q2358680$3BCF3AAB-FC49-4057-918C-32620B3A7922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"4a99d805d30dc5ab393724381d7e47e7e9b46cf0","datavalue":{"value":{"entity-type":"item","numeric-id":5744129,"id":"Q5744129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2e7d720c2b3a74234d8af4e4a51606de47a5fda0","datavalue":{"value":{"amount":"+0.7832434773445129","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":"Q2358680$59DD74E4-4C36-4424-A35D-FA481AA7EEED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b60536368fd04db50d97706d7acbc7c1b6b8e58","datavalue":{"value":{"entity-type":"item","numeric-id":3192263,"id":"Q3192263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"32654b509951335b43f31bcf205ff6583b372c05","datavalue":{"value":{"amount":"+0.7808488011360168","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":"Q2358680$C79ED07B-242C-489C-87BA-6F12691C3E13","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Prefix-suffix square reduction","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Prefix-suffix_square_reduction"}}}}}