Narrow Results

A border of a string is a prefix of the string that is simultaneously its suffix. It is one of the basic stringology keystones used as a part of many algorithms in pattern matching, molecular biology, computer-assisted music analysis and others.

The paper offers the automata-theoretical description of Iliopoulos's ALL_BORDERS algorithm. The algorithm finds all borders of a string with don't care symbols. We show that ALL_BORDERS algorithm is an implementation of a finite state transducer of specific form. We describe how such a transducer can be constructed and what should be the input string like. The described transducer finds a set of lengths of all borders.

Last but not least, we define approximate borders and show how to find all approximate borders of a string when we concern Hamming distance definition. Our solution of this problem is based on transducers again. This allows us to use analogy with automata-based pattern matching methods. Finally we discuss conditions under which the same principle can be used for other distance measures.

We say a family of strings over an alphabet is an UMFF if every string has a unique maximal factorization over . Foundational work by Chen, Fox and Lyndon established properties of the Lyndon circ-UMFF, which is based on lexicographic ordering. Commencing with the circ-UMFF related to V-order, we then proved analogous factorization families for a further 32 Block-like binary orders. Here we distinguish between UMFFs and circ-UMFFs, and then study the structural properties of circ-UMFFs. These properties give rise to the complete construction of any circ-UMFF. We prove that any circ-UMFF is a totally ordered set and a factorization over it must be monotonic. We define atom words and initiate a study of u, v-atoms. Applications of circ-UMFFs arise in string algorithmics.

A closed string contains a proper factor occurring as both a prefix and a suffix but not elsewhere in the string. Closed strings were introduced by Fici (WORDS 2011) as objects of combinatorial interest. This paper addresses a new problem by extending the closed string problem to the $k$-closed string problem, for which a level of approximation is permitted up to a number of Hamming distance errors, set by the parameter $k$.

We address the problem of deciding whether or not a given string of length $n$ over an integer alphabet is $k$-closed and additionally specifying the border resulting in the string being $k$-closed. Specifically, we present an ${𝒪}(kn)$-time and ${𝒪}(n)$-space algorithm to achieve this along with the pseudocode of an implementation and proof-of-concept experimental results.

The U.S.-Mexico border region has two important but often overlooked characteristics. First, it is the physical place of most of the integration between the United States and Mexico, including market driven integration such as trade flows, migration, and investment as well as policy driven integration such as security cooperation, infrastructure development, and emergency response. Second, the border region has a growing transnational population that lives, works, goes to school, and participates in family and social networks on both sides of the border. Recent U.S. policy has hardened the border in response to concerns about terrorism, drug and human trafficking, undocumented migration, and arms smuggling. The consequences of these policies include disruption of the on-going economic integration, large external costs imposed on the growing transnational population, and barriers to progress on a number of issues of national importance, including dispute resolution, migration, and environmental management, among others. The paper identifies and discusses the advantages of the three different definitions of the border in current usage: counties and municipios that touch the border; the 100 kilometer boundary first set by the La Paz Agreement and later amended to 300 kilometers in Mexico and 100 in the U.S.; and the ten states that are along the border. The hardening of the border is partly the result of a lack of border institutions and the inability of border residents to speak in a common voice when they talk to their capitals. This is changing, however, as new institutions such as the Border Governors Conference take on a more active role in promoting the interests of border states and border regions. An examination of a recent Delphi survey of border decision-makers shows a high degree of cross border agreement on the goals and needs of the region in key areas such as competitiveness, security, and sustainability.

The 1906 Convention and the 1944 Treaty establish the distribution of surface water of the Rio Grande (RG), Colorado, and Tijuana Rivers between the United States and Mexico. Neither of these treaties addresses groundwater management. Only Minute 242 to the 1944 Treaty, regulates salinity for groundwater. Specifically, Minute 242.5 establishes that there is a lack of “conclusion by the Governments of the United States and Mexico for a comprehensive agreement on groundwater in the border areas.” The lack of regulation has contributed to overdraft and degradation of the water quality in several aquifers along the US–Mexico border. Recommendations for an institutional and legal framework under an umbrella agreement, addressing water bank as allocation tool, attempt to fill the legal vacuum of international and interstate groundwater management in the US–Mexico border region. In addition, these recommendations can be adapted to other transboundary basins around the world.