Search for Articles:
Title / Keyword
Author / Affiliation / Email
Journal
Article Type
 
 
Advanced Search
 
Section
Special Issue
Volume
Issue
Number
Page
 
3.5
2.4
Journals
Mathematics
Special Issues
Analysis of One-Dimensional Regularities
share announcement

Analysis of One-Dimensional Regularities

A special issue of Mathematics (ISSN 2227-7390). This special issue belongs to the section "Mathematics and Computer Science".

Deadline for manuscript submissions: closed (20 November 2022) | Viewed by 4070

Special Issue Editor

Dr. Dominik Köppl

E-Mail Website
Guest Editor
M&D Data Science Center, Tokyo Medical and Dental University, Tokyo 113-8510, Japan
Interests: data structures; string algorithms; combinatorics on words
Special Issues, Collections and Topics in MDPI journals

Special Issue Information

Dear Colleagues,

The analysis of one-dimensional regularities lies at the intersection of discrete mathematics, algorithms and data structures. This field is still gaining momentum due to the rapid and ever-accelerating pace at which data are collected, supported by modern storage architectures and network infrastructures.

Advancements in this field, involving combinatorial aspects as well as the mathematical analysis of algorithmic complexities, help us address the vital question of how to process large datasets efficiently. With a better understanding of one-dimensional regularities, in particular in strings, we can leverage those regularities not only to compress textual data but also to query the data more efficiently. Such benefits are not limited to strings, but also give rise to the design of more efficient algorithms and data structures for trees, graphs and so on.

We cordially invite you to submit your research results to this Special Issue. The key areas of interest include, but are not limited to, the following:

  •  Working with general text data;
  •  String algorithms (such as string processing or pattern matching in strings);
  •  Searching and indexing strings;
  •  Lossless compression of strings (algorithms and compression schemes);
  •  Succinct or compressed data structures for strings.

Both theoretical and experimental contributions are welcome. 

Please be aware that submissions for which there exists a conflict of interest (CoI), including joint publications with the Guest Editor, cannot be considered for this Special Issue.

For the sake of high-quality reviewing, we appreciate recommendations of reviewers without CoIs with authors.

Dr. Dominik Köppl
Guest Editor

Manuscript Submission Information

Manuscripts should be submitted online at www.mdpi.com by registering and logging in to this website. Once you are registered, click here to go to the submission form. Manuscripts can be submitted until the deadline. All submissions that pass pre-check are peer-reviewed. Accepted papers will be published continuously in the journal (as soon as accepted) and will be listed together on the special issue website. Research articles, review articles as well as short communications are invited. For planned papers, a title and short abstract (about 100 words) can be sent to the Editorial Office for announcement on this website.

Submitted manuscripts should not have been published previously, nor be under consideration for publication elsewhere (except conference proceedings papers). All manuscripts are thoroughly refereed through a single-blind peer-review process. A guide for authors and other relevant information for submission of manuscripts is available on the Instructions for Authors page. Mathematics is an international peer-reviewed open access semimonthly journal published by MDPI.

Please visit the Instructions for Authors page before submitting a manuscript. The Article Processing Charge (APC) for publication in this open access journal is 2600 CHF (Swiss Francs). Submitted papers should be well formatted and use good English. Authors may use MDPI's English editing service prior to publication or during author revisions.

Keywords

  • compressed and space-efficient data structures
  • lossless data compression
  • string processing
  • combinatorics on words
  • text indexing

Published Papers (3 papers)

Download All Papers
Order results
Result details
Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:

Research

9 pages, 360 KiB  
Article
Practical Evaluation of Lyndon Factors via Alphabet Reordering
by Marcelo K. Albertini and Felipe A. Louza
Mathematics 2023, 11(1), 139; https://0-doi-org.brum.beds.ac.uk/10.3390/math11010139 - 27 Dec 2022
Cited by 1 | Viewed by 947
Abstract
We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with Pizza&Chili datasets show that for most alphabet reorderings, the number of Lyndon factors is usually small, and the length of the longest Lyndon factor can be [...] Read more.
We evaluate the influence of different alphabet orderings on the Lyndon factorization of a string. Experiments with Pizza&Chili datasets show that for most alphabet reorderings, the number of Lyndon factors is usually small, and the length of the longest Lyndon factor can be as large as the input string, which is unfavorable for algorithms and indexes that depend on the number of Lyndon factors. We present results with randomized alphabet permutations that can be used as a baseline to assess the effectiveness of heuristics and methods designed to modify the Lyndon factorization of a string via alphabet reordering. Full article
(This article belongs to the Special Issue Analysis of One-Dimensional Regularities)
►▼ Show Figures

Figure 1

27 pages, 420 KiB  
Article
Almost Optimal Searching of Maximal Subrepetitions in a Word
by Roman Kolpakov
Mathematics 2022, 10(19), 3569; https://0-doi-org.brum.beds.ac.uk/10.3390/math10193569 - 30 Sep 2022
Viewed by 937
Abstract
For some fixed δ such that 0<δ<1, a δ-subrepetition in a word is a factor whose exponent is less than 2 but is not less than 1+δ (the exponent of the factor is the ratio [...] Read more.
For some fixed δ such that 0<δ<1, a δ-subrepetition in a word is a factor whose exponent is less than 2 but is not less than 1+δ (the exponent of the factor is the ratio of the factor length to its minimal period). The δ-subrepetition is maximal if it cannot be extended to the left or to the right by at least one letter while preserving its minimal period. In the paper, we propose an algorithm for searching all maximal δ-subrepetitions in a word of length n in O(nδlog1δ) time (the lower bound for this time is Ω(nδ)). It improves the previous known time complexity bounds for solving this problem. Full article
(This article belongs to the Special Issue Analysis of One-Dimensional Regularities)
►▼ Show Figures

Figure 1

10 pages, 300 KiB  
Article
An Improved Order-Preserving Pattern Matching Algorithm Using Fingerprints
by Youngjoon Kim, Youngho Kim and Jeong Seop Sim
Mathematics 2022, 10(12), 1954; https://0-doi-org.brum.beds.ac.uk/10.3390/math10121954 - 07 Jun 2022
Cited by 1 | Viewed by 1258
Abstract
Two strings of the same length are order isomorphic if their relative orders are the same. The order-preserving pattern matching problem is to find all substrings of text T that are order isomorphic to pattern P when [...] Read more.
Two strings of the same length are order isomorphic if their relative orders are the same. The order-preserving pattern matching problem is to find all substrings of text T that are order isomorphic to pattern P when T(|T|=n) and P(|P|=m) are given. An O(mn+nqlogq+q!)-time algorithm using the O(m+q!) space for the order-preserving pattern matching problem has been proposed utilizing fingerprints of q-grams based on the factorial number system and the bad character heuristic. In this paper, we propose an O(mn+2q)-time algorithm using the O(m+2q) space for the order-preserving pattern matching problem, but utilizing fingerprints of q-grams converted to binary numbers. A comparative experiment using three types of time series data demonstrates that the proposed algorithm is faster than existing algorithms because it reduces the number of order isomorphism tests. Full article
(This article belongs to the Special Issue Analysis of One-Dimensional Regularities)
►▼ Show Figures

Figure 1

Show export options expand_more Show export options expand_less
Select all
Export citation of selected articles as:
 
Displaying articles 1-3
Back to TopTop