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
Convolutional neural networks (CNNs) and self-attention (SA) have demonstrated remarkable success in low-level vision tasks, such as image super-resolution, deraining, and dehazing. The former excels in acquiring loca...
详细信息
Requirement engineering is a major phase of software development process. A project's success mainly depends on an efficient and effective requirement engineering process. Practices have been defined to ensure suc...
详细信息
Context-aware fire detection is a significant task in the era of new urban monitoring. Severe damage might result from fire events. To minimize the occurrence of these events, timely detection of fire accidents is nec...
详细信息
Traditional Wireless Sensor Networks(WSNs)comprise of costeffective sensors that can send physical parameters of the target environment to an intended *** the evolution of technology,multimedia sensor nodes have becom...
详细信息
Traditional Wireless Sensor Networks(WSNs)comprise of costeffective sensors that can send physical parameters of the target environment to an intended *** the evolution of technology,multimedia sensor nodes have become the hot research topic since it can continue gathering multimedia content and scalar from the target *** existence of multimedia sensors,integrated with effective signal processing and multimedia source coding approaches,has led to the increased application of Wireless Multimedia Sensor Network(WMSN).This sort of network has the potential to capture,transmit,and receive multimedia *** energy is a major source in WMSN,novel clustering approaches are essential to deal with adaptive topologies of WMSN and prolonged network *** this motivation,the current study develops an Enhanced Spider Monkey Optimization-based Energy-Aware Clustering Scheme(ESMO-EACS)for *** proposed ESMO-EACS model derives ESMO algorithm by incorporating the concepts of SMO algorithm and quantum *** proposed ESMO-EACS model involves the design of fitness functions using distinct input parameters for effective construction of clusters.A comprehensive experimental analysis was conducted to validate the effectiveness of the proposed ESMO-EACS technique in terms of different performance *** simulation outcome established the superiority of the proposed ESMO-EACS technique to other methods under various measures.
Remaining Useful Life (RUL) prediction is crucial for prognostics and health management (PHM) in industrial applications, as it helps to reduce unexpected maintenance and downtime costs. This study introduces AttNet, ...
详细信息
This paper has introduced studies on applying reinforcement learning to MAC protocols in wireless networks to enhance network performance. As services and users demanding improved network performance increase, using r...
详细信息
As the importance of sustainable practices in the automobile sector grows, it's critical to anticipate motorcycle prices and offerings. With so many variables to consider when buying a secondhand motorcycle-condit...
详细信息
Illegible handwriting on medical prescriptions poses a significant challenge, often leading to the misinterpretation of drug names and dosages. This issue primarily stems from doctors' use of Latin abbreviations, ...
详细信息
Representation learning on spatial networks is emerging as a distinct area in machine learning and is attracting much attention in diverse domains. Some applications include molecular graphs for drug discovery and scr...
详细信息
暂无评论