| 3 |
String Rearrangement Inequalities and a Total Order Between Primitive Words ...
|
|
|
|
Abstract:
We study the following rearrangement problem: Given $n$ words, rearrange and concatenate them so that the obtained string is lexicographically smallest (or largest, respectively). We show that this problem reduces to sorting the given words so that their repeating strings are non-decreasing (or non-increasing, respectively), where the repeating string of a word $A$ refers to the infinite string $AAA\ldots$. Moreover, for fixed size alphabet $Σ$, we design an $O(L)$ time sorting algorithm of the words (in the mentioned orders), where $L$ denotes the total length of the input words. Hence we obtain an $O(L)$ time algorithm for the rearrangement problem. Finally, we point out that comparing primitive words via comparing their repeating strings leads to a total order, which can further be extended to a total order on the finite words (or all words). ...
|
|
Keyword:
68R15; Data Structures and Algorithms cs.DS; F.2.2; FOS Computer and information sciences
|
|
URL: https://arxiv.org/abs/2204.11213
https://dx.doi.org/10.48550/arxiv.2204.11213
|
|
BASE
|
|
Hide details
|
|
|
| 4 |
Dynamic Suffix Array with Polylogarithmic Queries and Updates ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 5 |
Quantum Meets Fine-Grained Complexity: Sublinear Time Quantum Algorithms for String Problems ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 6 |
An Unsupervised Approach to Structuring and Analyzing Repetitive Semantic Structures in Free Text of Electronic Medical Records
|
|
|
|
In: Journal of Personalized Medicine; Volume 12; Issue 1; Pages: 25 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 7 |
Optimal Fuzzy Controller Design for Autonomous Robot Path Tracking Using Population-Based Metaheuristics
|
|
|
|
In: Symmetry; Volume 14; Issue 2; Pages: 202 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 8 |
Methods, Models and Tools for Improving the Quality of Textual Annotations
|
|
|
|
In: Modelling; Volume 3; Issue 2; Pages: 224-242 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 9 |
Undecidability and Complexity for Super-Turing Models of Computation
|
|
|
|
In: Proceedings; Volume 81; Issue 1; Pages: 123 (2022)
|
|
BASE
|
|
Show details
|
|
|
| 10 |
Suffix tree-based linear algorithms for multiple prefixes, single suffix counting and listing problems ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 11 |
Reduction ratio of the IS-algorithm: worst and random cases ...
|
|
|
|
BASE
|
|
Show details
|
|
|
| 12 |
Optimal Fuzzy Controller Design for Autonomous Robot Path Tracking Using Population-Based Metaheuristics
|
|
|
|
BASE
|
|
Show details
|
|
|
| 14 |
Design and development of a lead free piezoelectric energy harvester for wideband, low frequency and low amplitude vibrations
|
|
|
|
In: Micromachines ; https://hal.archives-ouvertes.fr/hal-03549337 ; Micromachines, 2021, 12 (12), pp.1537 (2021)
|
|
BASE
|
|
Show details
|
|
|
| 15 |
Distinct signatures of subjective confidence and objective accuracy in speech prosody
|
|
|
|
In: ISSN: 0010-0277 ; EISSN: 1873-7838 ; Cognition ; https://hal.sorbonne-universite.fr/hal-03263512 ; Cognition, Elsevier, 2021, 212, pp.104661. ⟨10.1016/j.cognition.2021.104661⟩ (2021)
|
|
BASE
|
|
Show details
|
|
|
| 16 |
Critical Digital Humanities: texts, code and algorithms
|
|
|
|
In: Humanités numériques dans et sur les Amériques ; https://hal.archives-ouvertes.fr/hal-03373785 ; Humanités numériques dans et sur les Amériques, Apr 2021, Avignon, France (2021)
|
|
BASE
|
|
Show details
|
|
|
| 17 |
Chinese character decomposition for neural MT with multi-word expressions
|
|
|
|
In: Han, Lifeng orcid:0000-0002-3221-2185 , Jones, Gareth J.F. orcid:0000-0003-2923-8365 , Smeaton, Alan F. orcid:0000-0003-1028-8389 and Bolzoni, Paolo (2021) Chinese character decomposition for neural MT with multi-word expressions. In: 23rd Nordic Conference on Computational Linguistics (NoDaLiDa 2021), 31 May- 2 June 2021, Reykjavik, Iceland (Online). (In Press) (2021)
|
|
BASE
|
|
Show details
|
|
|
| 18 |
cushLEPOR uses LABSE distilled knowledge to improve correlation with human translation evaluations
|
|
|
|
In: Erofeev, Gleb, Sorokina, Irina, Han, Lifeng orcid:0000-0002-3221-2185 and Gladkoff, Serge (2021) cushLEPOR uses LABSE distilled knowledge to improve correlation with human translation evaluations. In: Machine Translation Summit 2021, 16-20 Aug 2021, USA (online). (In Press) (2021)
|
|
BASE
|
|
Show details
|
|
|
| 19 |
Monte Carlo modelling of confidence intervals in translation quality evaluation (TQE) and post-editing dstance (PED) measurement
|
|
|
|
In: Alekseeva, Alexandra orcid:0000-0002-7990-4592 , Gladkoff, Serge, Sorokina, Irina and Han, Lifeng orcid:0000-0002-3221-2185 (2021) Monte Carlo modelling of confidence intervals in translation quality evaluation (TQE) and post-editing dstance (PED) measurement. In: Metrics 2021: Workshop on Informetric and Scientometric Research (SIG-MET), 23-24 Oct 2021, Online. (2021)
|
|
BASE
|
|
Show details
|
|
|
| 20 |
Meta-evaluation of machine translation evaluation methods
|
|
|
|
In: Han, Lifeng orcid:0000-0002-3221-2185 (2021) Meta-evaluation of machine translation evaluation methods. In: Workshop on Informetric and Scientometric Research (SIG-MET), 23-24 Oct 2021, Online. (2021)
|
|
BASE
|
|
Show details
|
|
|
|
|
