Search results for "Algorithm"

showing 10 items of 4887 documents

Algorithms for Computing Abelian Periods of Words

2012

Constantinescu and Ilie (Bulletin EATCS 89, 167--170, 2006) introduced the notion of an \emph{Abelian period} of a word. A word of length $n$ over an alphabet of size $\sigma$ can have $\Theta(n^{2})$ distinct Abelian periods. The Brute-Force algorithm computes all the Abelian periods of a word in time $O(n^2 \times \sigma)$ using $O(n \times \sigma)$ space. We present an off-line algorithm based on a $\sel$ function having the same worst-case theoretical complexity as the Brute-Force one, but outperforming it in practice. We then present on-line algorithms that also enable to compute all the Abelian periods of all the prefixes of $w$.

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Abelian repetitionElementary abelian groupRank of an abelian groupCombinatoricsComputer Science - Data Structures and AlgorithmsFOS: MathematicsDiscrete Mathematics and CombinatoricsMathematics - CombinatoricsData Structures and Algorithms (cs.DS)Abelian groupOnline algorithmMathematicsArithmetic of abelian varietiesDiscrete mathematicsCombinatorics on wordsApplied MathematicsAbelian periodText algorithmWeak repetitionPrefixCombinatorics on wordsDesign of algorithmCombinatorics (math.CO)AlgorithmWord (computer architecture)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics
researchProduct

On Combinatorial Generation of Prefix Normal Words

2014

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present an efficient algorithm for exhaustively listing the prefix normal words with a fixed length. The algorithm is based on the fact that the language of prefix normal words is a bubble language, a class of binary languages with the property that, for any word w in the language, exchanging the first occurrence of 01 by 10 in w results in another word in the language. We prove that each prefix normal word is produced in O(n) amortized time, and conjecture, based on expe…

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Computer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)Data_CODINGANDINFORMATIONTHEORYComputer Science - Discrete Mathematics
researchProduct

Pattern detection in ordered graphs

2023

A popular way to define or characterize graph classes is via forbidden subgraphs or forbidden minors. These characterizations play a key role in graph theory, but they rarely lead to efficient algorithms to recognize these classes. In contrast, many essential graph classes can be recognized efficiently thanks to characterizations of the following form: there must exist an ordering of the vertices such that some ordered pattern does not appear, where a pattern is basically an ordered subgraph. These pattern characterizations have been studied for decades, but there have been recent efforts to better understand them systematically. In this paper, we focus on a simple problem at the core of th…

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Computer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)[INFO] Computer Science [cs]Computer Science - Discrete Mathematics
researchProduct

Algorithms for Anti-Powers in Strings

2018

Abstract A string S [ 1 , n ] is a power (or tandem repeat) of order k and period n / k if it can be decomposed into k consecutive equal-length blocks of letters. Powers and periods are fundamental to string processing, and algorithms for their efficient computation have wide application and are heavily studied. Recently, Fici et al. (Proc. ICALP 2016) defined an anti-power of order k to be a string composed of k pairwise-distinct blocks of the same length ( n / k , called anti-period). Anti-powers are a natural converse to powers, and are objects of combinatorial interest in their own right. In this paper we initiate the algorithmic study of anti-powers. Given a string S, we describe an op…

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)ComputationComputer Science - Formal Languages and Automata Theory0102 computer and information sciencesString processingInformation System01 natural sciencesUpper and lower boundsAnti-powersTheoretical Computer ScienceLemma (logic)ConverseComputer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)0101 mathematicsMathematicsCombinatorics on wordSignal processingCombinatorics on wordsComputer Science Applications1707 Computer Vision and Pattern RecognitionAnti-power16. Peace & justice113 Computer and information sciencesSubstringComputer Science Applications010101 applied mathematicsAlgorithmCombinatorics on words010201 computation theory & mathematicsSignal ProcessingAlgorithmAlgorithmsInformation SystemsComputer Science - Discrete Mathematics
researchProduct

Normal, Abby Normal, Prefix Normal

2014

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. This class of words is important in the context of binary jumbled pattern matching. In this paper we present results about the number $pnw(n)$ of prefix normal words of length $n$, showing that $pnw(n) =\Omega\left(2^{n - c\sqrt{n\ln n}}\right)$ for some $c$ and $pnw(n) = O \left(\frac{2^n (\ln n)^2}{n}\right)$. We introduce efficient algorithms for testing the prefix normal property and a "mechanical algorithm" for computing prefix normal forms. We also include games which can be played with prefix normal words. In these games Alice wishes to stay normal but Bob wants t…

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)Computer Science - Data Structures and AlgorithmsFOS: MathematicsMathematics - CombinatoricsData Structures and Algorithms (cs.DS)Computer Science - Formal Languages and Automata TheoryCombinatorics (math.CO)Data_CODINGANDINFORMATIONTHEORYComputer Science - Discrete Mathematics
researchProduct

A note on easy and efficient computation of full abelian periods of a word

2016

Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement $O(n\log\log n)$-time algorithm for computing all the full Abelian periods of a word of length $n$ over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the $O(n)$ algorithm proposed by Kociumaka et al. (Proc. of STACS, 245-256, 2013) for the same problem.

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Elementary abelian groupComputer Science - Formal Languages and Automata Theory0102 computer and information sciences02 engineering and technology[INFO] Computer Science [cs]01 natural sciencesRank of an abelian groupCombinatoricsSimple (abstract algebra)Computer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringDiscrete Mathematics and CombinatoricsData Structures and Algorithms (cs.DS)[INFO]Computer Science [cs]Abelian groupHidden subgroup problemDiscrete Mathematics and CombinatoricComputingMilieux_MISCELLANEOUSMathematicsCombinatorics on wordDiscrete mathematicsApplied Mathematics020206 networking & telecommunicationsAbelian periodText algorithmWeak repetitionFree abelian groupAbelian powerCombinatorics on wordsDesign of algorithm010201 computation theory & mathematicsWord (computer architecture)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics
researchProduct

A subquadratic algorithm for minimum palindromic factorization

2014

We give an $\mathcal{O}(n \log n)$-time, $\mathcal{O}(n)$-space algorithm for factoring a string into the minimum number of palindromic substrings. That is, given a string $S [1..n]$, in $\mathcal{O}(n \log n)$ time our algorithm returns the minimum number of palindromes $S_1,\ldots, S_\ell$ such that $S = S_1 \cdots S_\ell$. We also show that the time complexity is $\mathcal{O}(n)$ on average and $\Omega(n\log n)$ in the worst case. The last result is based on a characterization of the palindromic structure of Zimin words.

FOS: Computer and information sciencesDiscrete Mathematics (cs.DM)PalindromeCharacterization (mathematics)Binary logarithmOmegaSubstringTheoretical Computer ScienceString algorithmComputational Theory and MathematicsFactorizationComputer Science - Data Structures and AlgorithmsC++ string handlingPalindromeDiscrete Mathematics and CombinatoricsData Structures and Algorithms (cs.DS)FactorizationTime complexityAlgorithmMathematicsComputer Science - Discrete Mathematics
researchProduct

Optimal one-shot quantum algorithm for EQUALITY and AND

2017

We study the computation complexity of Boolean functions in the quantum black box model. In this model our task is to compute a function $f:\{0,1\}\to\{0,1\}$ on an input $x\in\{0,1\}^n$ that can be accessed by querying the black box. Quantum algorithms are inherently probabilistic; we are interested in the lowest possible probability that the algorithm outputs incorrect answer (the error probability) for a fixed number of queries. We show that the lowest possible error probability for $AND_n$ and $EQUALITY_{n+1}$ is $1/2-n/(n^2+1)$.

FOS: Computer and information sciencesDiscrete mathematicsOne shotQuantum PhysicsGeneral Computer ScienceProbabilistic logicFOS: Physical sciencesFunction (mathematics)Computational Complexity (cs.CC)Computer Science - Computational ComplexityProbability of errorComputation complexityQuantum algorithmQuantum Physics (quant-ph)Boolean functionQuantumMathematics
researchProduct

On the Power of Non-adaptive Learning Graphs

2012

We introduce a notion of the quantum query complexity of a certificate structure. This is a formalisation of a well-known observation that many quantum query algorithms only require the knowledge of the disposition of possible certificates in the input string, not the precise values therein. Next, we derive a dual formulation of the complexity of a non-adaptive learning graph, and use it to show that non-adaptive learning graphs are tight for all certificate structures. By this, we mean that there exists a function possessing the certificate structure and such that a learning graph gives an optimal quantum query algorithm for it. For a special case of certificate structures generated by cer…

FOS: Computer and information sciencesDiscrete mathematicsQuantum PhysicsTheoretical computer scienceComputational complexity theoryComputer scienceGeneral MathematicsExistential quantificationFOS: Physical sciencesGraph theoryString searching algorithmComputational Complexity (cs.CC)Query optimizationCertificateUpper and lower boundsTheoretical Computer ScienceComputational MathematicsComputer Science - Computational ComplexityComputational Theory and MathematicsBounded functionAdaptive learningSpecial caseQuantum Physics (quant-ph)Quantum computerMathematics2013 IEEE Conference on Computational Complexity
researchProduct

Separations in Query Complexity Based on Pointer Functions

2015

In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error randomized query complexity is $\tilde O(\sqrt{n})$. We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadra…

FOS: Computer and information sciencesFOS: Physical sciences0102 computer and information sciencesComputational Complexity (cs.CC)01 natural sciencesCombinatoricsArtificial Intelligence0103 physical sciences0101 mathematics010306 general physicsCommunication complexityBoolean functionQuantumMathematicsDiscrete mathematicsQuantum PhysicsBinary tree010102 general mathematicsNAND logicRandomized algorithmComputer Science - Computational ComplexityHardware and ArchitectureControl and Systems Engineering010201 computation theory & mathematicsIndependent setPointer (computer programming)Quantum algorithmQuantum Physics (quant-ph)SoftwareInformation Systems
researchProduct