A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the most basic questions is how many dis...
详细信息
ISBN:
(纸本)9783959773225
A fundamental concept related to strings is that of repetitions. It has been extensively studied in many versions, from both purely combinatorial and algorithmic angles. One of the most basic questions is how many distinct squares, i.e., distinct strings of the form UU, a string of length n can contain as fragments. It turns out that this is always O(n), and the bound cannot be improved to sublinear in n [Fraenkel and Simpson, JCTA 1998]. Several similar questions about repetitions in strings have been considered, and by now we seem to have a good understanding of their repetitive structure. For higher-dimensional strings, the basic concept of periodicity has been successfully extended and applied to design efficient algorithms – it is inherently more complex than for regular strings. Extending the notion of repetitions and understanding the repetitive structure of higher-dimensional strings is however far from complete. Quartics were introduced by Apostolico and Brimkov [TCS 2000] as analogues of squares in two dimensions. Charalampopoulos, Radoszewski, Rytter, Waleń, and Zuba [ESA 2020] proved that the number of distinct quartics in an n × n 2D string is O(n2 log2 n) and that they can be computed in O(n2 log2 n) time. Gawrychowski, Ghazawi, and Landau [SPIRE 2021] constructed an infinite family of n × n 2D strings with Ω(n2 log n) distinct quartics. This brings the challenge of determining asymptotically tight bounds. Here, we settle both the combinatorial and the algorithmic aspects of this question: the number of distinct quartics in an n × n 2D string is O(n2 log n) and they can be computed in the worst-case optimal O(n2 log n) time. As expected, our solution heavily exploits the periodic structure implied by occurrences of quartics. However, the two-dimensional nature of the problem introduces some technical challenges. Somewhat surprisingly, we overcome the final challenge for the combinatorial bound using a result of Marcus and Tardos [JCTA 2004] for permuta
Recently, graph neural networks(GNNs) have played a key crucial in many recommendation situations. In particular, contrastive learning-based hypergraph neural networks (HGNNs) are gradually becoming a research focus f...
详细信息
Road network design, as an important part of landscape modeling, shows a great significance in automatic driving, video game development, and disaster simulation. To date, this task remains labor-intensive, tedious an...
详细信息
With the rapid development of blockchain and the increasing computing power, the realization of the metaverse has become possible. However, there are not yet well-regulated and standardized industry standards for the ...
详细信息
Vanilla image completion approaches exhibit sensitivity to large missing regions, attributed to the limited availability of reference information for plausible generation. To mitigate this, existing methods incorporat...
详细信息
Aiming at the low matching accuracy of existing local stereo matching algorithms in weak texture areas, a local stereo matching algorithm based on multi-matching cost fusion and guided filtering cost aggregation with ...
详细信息
With the continuous evolution of blockchain technology, cryptocurrency platforms such as Ethereum have emerged as centers for digital asset transactions and smart contracts deployment. However, this nascent financial ...
详细信息
This paper primarily explores methods for enhancing the performance of event element entity recognition tasks by enriching the positional information of vocabulary and focusing on document context. It proposes and imp...
详细信息
Pre-trained Language Models have been shown to be able to emulate deductive reasoning in natural language. However, PLMs are easily affected by irrelevant information (e.g., entity) in instance-level proofs when learn...
详细信息
The conventional Levenberg-Marquardt (LM) algorithm is a state-of-the-art trust-region optimization method for solving bundle adjustment problems in the Structure-from-Motion community, which not only takes advantage ...
详细信息
暂无评论