Search results for "Algorithm"

showing 10 items of 4887 documents

Abelian Powers and Repetitions in Sturmian Words

2016

Richomme, Saari and Zamboni (J. Lond. Math. Soc. 83: 79-95, 2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $\alpha$. vAs an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_\alpha)$ of a Sturmian word $s_\alpha$ of angle $\alpha$ as the quantity $A(s_\a…

FOS: Computer and information sciencesFibonacci numberGeneral Computer ScienceDiscrete Mathematics (cs.DM)Formal Languages and Automata Theory (cs.FL)[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Computer Science - Formal Languages and Automata Theory0102 computer and information sciences01 natural sciencesTheoretical Computer ScienceCombinatoricsFOS: MathematicsMathematics - Combinatorics[INFO]Computer Science [cs]Number Theory (math.NT)0101 mathematicsAbelian groupContinued fractionFibonacci wordComputingMilieux_MISCELLANEOUSQuotientMathematicsMathematics - Number Theoryta111010102 general mathematicsComputer Science (all)Sturmian wordSturmian wordAbelian period; Abelian power; Critical exponent; Lagrange constant; Sturmian word; Theoretical Computer Science; Computer Science (all)Abelian periodLagrange constantCritical exponentAbelian power010201 computation theory & mathematicsBounded functionExponentCombinatorics (math.CO)Computer Science::Formal Languages and Automata TheoryComputer Science - Discrete Mathematics
researchProduct

The Descriptive Complexity Approach to LOGCFL

1998

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free proj…

FOS: Computer and information sciencesFinite model theoryUnary operationComputer Networks and Communicationsautomata and formal languages0102 computer and information sciencesComputational Complexity (cs.CC)Computer Science::Computational ComplexityArityDescriptive complexity theory01 natural sciencesTheoretical Computer ScienceComputer Science::Logic in Computer ScienceNondeterministic finite automaton0101 mathematicsLOGCFLMathematicsDiscrete mathematicscomputational complexityApplied Mathematics010102 general mathematicsdescriptive complexityNondeterministic algorithmComputer Science - Computational Complexityfinite model theoryQuantifier (logic)Computational Theory and Mathematics010201 computation theory & mathematicsF.1.3Journal of Computer and System Sciences
researchProduct

Online Computation of Abelian Runs

2015

Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. We give an algorithm that finds all the abelian runs of period $\mathcal{P}$ in a word of length $n$ in time $O(n\times |\mathcal{P}|)$ and space $O(\sigma+|\mathcal{P}|)$.

FOS: Computer and information sciencesFormal Languages and Automata Theory (cs.FL)Abelian run[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS][INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Computer Science - Formal Languages and Automata Theory0102 computer and information sciences02 engineering and technology[INFO] Computer Science [cs]01 natural sciencesOnline computationTheoretical Computer ScienceCombinatoricsComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringData Structures and Algorithms (cs.DS)[INFO]Computer Science [cs]Abelian groupComputingMilieux_MISCELLANEOUSMathematicsCombinatorics on wordDiscrete mathematicsComputer Science (all)020206 networking & telecommunicationsAbelian periodText algorithm16. Peace & justiceSubstringCombinatorics on words010201 computation theory & mathematicsWord (group theory)Computer Science::Formal Languages and Automata Theory
researchProduct

A Fast Algorithm Finding the Shortest Reset Words

2012

In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is exponential. Yet, it is faster than the algorithms used so far and it works well in practice. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare resulted subsets. We give both theoretical and practical arguments showing that the branching factor is reduced efficiently. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with $n$ states and 2 input letters. We follow Skvorsov and Tipikin, who have performed such a s…

FOS: Computer and information sciencesFormal Languages and Automata Theory (cs.FL)Computer Science - Data Structures and AlgorithmsData Structures and Algorithms (cs.DS)Computer Science - Formal Languages and Automata TheoryComputer Science::Formal Languages and Automata Theory
researchProduct

Fast computation of abelian runs

2016

Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. Our main result is an online algorithm that, given a word $w$ of length $n$ over an alphabet of cardinality $\sigma$ and a Parikh vector $\mathcal{P}$, returns all the abelian runs of period $\mathcal{P}$ in $w$ in time $O(n)$ and space $O(\sigma+p)$, where $p$ is the norm of $\mathcal{P}$, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm $p$ in $w$ in time $O(np)$, for any given norm $p$. Finally, we give an $O(n^2)$-time offline randomi…

FOS: Computer and information sciencesGeneral Computer ScienceComputationAbelian run[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Elementary abelian group0102 computer and information sciences02 engineering and technology01 natural sciencesRank of an abelian groupTheoretical Computer ScienceCombinatoricsComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringData Structures and Algorithms (cs.DS)[INFO]Computer Science [cs]Online algorithmAbelian groupComputingMilieux_MISCELLANEOUSMathematicsCombinatorics on wordDiscrete mathematicsComputer Science (all)Abelian periodText algorithm16. Peace & justiceSubstringRandomized algorithmCombinatorics on words010201 computation theory & mathematics020201 artificial intelligence & image processingComputer Science::Formal Languages and Automata Theory
researchProduct

Generating a Gray code for prefix normal words in amortized polylogarithmic time per word

2020

A prefix normal word is a binary word with the property that no substring has more $1$s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length $n$ as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in $\Oh(\log^2 n)$ amortized time per word, while the best generation algorithm hitherto has $\Oh(n)$ running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages.

FOS: Computer and information sciencesGeneral Computer ScienceFormal Languages and Automata Theory (cs.FL)Property (programming)combinatorial Gray codeComputer Science - Formal Languages and Automata TheoryData_CODINGANDINFORMATIONTHEORY0102 computer and information sciences02 engineering and technologyCharacterization (mathematics)01 natural sciencesTheoretical Computer ScienceCombinatoricsSet (abstract data type)Gray codeComputer Science - Data Structures and Algorithms0202 electrical engineering electronic engineering information engineeringData Structures and Algorithms (cs.DS)MathematicsAmortized analysisSettore INF/01 - Informaticaprefix normal wordsSubstringcombinatorial generationPrefixjumbled pattern matching010201 computation theory & mathematics020201 artificial intelligence & image processingbinary languagesprefix normal words binary languages combinatorial Gray code combinatorial generation jumbled pattern matchingWord (computer architecture)Theoretical Computer Science
researchProduct

Sparsity-Driven Digital Terrain Model Extraction

2020

We here introduce an automatic Digital Terrain Model (DTM) extraction method. The proposed sparsity-driven DTM extractor (SD-DTM) takes a high-resolution Digital Surface Model (DSM) as an input and constructs a high-resolution DTM using the variational framework. To obtain an accurate DTM, an iterative approach is proposed for the minimization of the target variational cost function. Accuracy of the SD-DTM is shown in a real-world DSM data set. We show the efficiency and effectiveness of the approach both visually and quantitatively via residual plots in illustrative terrain types.

FOS: Computer and information sciencesHardware_MEMORYSTRUCTURES010504 meteorology & atmospheric sciencesIterative methodComputer scienceComputer Vision and Pattern Recognition (cs.CV)0211 other engineering and technologiesComputer Science - Computer Vision and Pattern RecognitionTerrain02 engineering and technologyFunction (mathematics)Hardware_PERFORMANCEANDRELIABILITYComputerSystemsOrganization_PROCESSORARCHITECTURES01 natural sciencesData setHardware_INTEGRATEDCIRCUITSExtraction (military)Digital elevation modelAlgorithm021101 geological & geomatics engineering0105 earth and related environmental sciences
researchProduct

Joint Gaussian Processes for Biophysical Parameter Retrieval

2017

Solving inverse problems is central to geosciences and remote sensing. Radiative transfer models (RTMs) represent mathematically the physical laws which govern the phenomena in remote sensing applications (forward models). The numerical inversion of the RTM equations is a challenging and computationally demanding problem, and for this reason, often the application of a nonlinear statistical regression is preferred. In general, regression models predict the biophysical parameter of interest from the corresponding received radiance. However, this approach does not employ the physical information encoded in the RTMs. An alternative strategy, which attempts to include the physical knowledge, co…

FOS: Computer and information sciencesHyperparameter010504 meteorology & atmospheric sciencesComputer scienceRemote sensing application0211 other engineering and technologiesMachine Learning (stat.ML)Regression analysis02 engineering and technologyInverse problem01 natural sciencesMachine Learning (cs.LG)Data modelingNonparametric regressionComputer Science - Learningsymbols.namesakeStatistics - Machine LearningRadiative transfersymbolsGeneral Earth and Planetary SciencesElectrical and Electronic EngineeringGaussian processAlgorithm021101 geological & geomatics engineering0105 earth and related environmental sciencesIEEE Transactions on Geoscience and Remote Sensing
researchProduct

Randomized Rx For Target Detection

2018

This work tackles the target detection problem through the well-known global RX method. The RX method models the clutter as a multivariate Gaussian distribution, and has been extended to nonlinear distributions using kernel methods. While the kernel RX can cope with complex clutters, it requires a considerable amount of computational resources as the number of clutter pixels gets larger. Here we propose random Fourier features to approximate the Gaussian kernel in kernel RX and consequently our development keep the accuracy of the nonlinearity while reducing the computational cost which is now controlled by an hyperparameter. Results over both synthetic and real-world image target detection…

FOS: Computer and information sciencesHyperparameter020301 aerospace & aeronauticsComputer Science - Machine LearningComputer scienceComputer Vision and Pattern Recognition (cs.CV)0211 other engineering and technologiesComputer Science - Computer Vision and Pattern RecognitionMultivariate normal distribution02 engineering and technologyObject detectionMachine Learning (cs.LG)symbols.namesakeKernel (linear algebra)Kernel method0203 mechanical engineeringKernel (statistics)Gaussian functionsymbolsClutterAnomaly detectionAlgorithm021101 geological & geomatics engineering
researchProduct

CLEAR: Covariant LEAst-Square Refitting with Applications to Image Restoration

2017

International audience; In this paper, we propose a new framework to remove parts of the systematic errors affecting popular restoration algorithms, with a special focus for image processing tasks. Generalizing ideas that emerged for $\ell_1$ regularization, we develop an approach re-fitting the results of standard methods towards the input data. Total variation regularizations and non-local means are special cases of interest. We identify important covariant information that should be preserved by the re-fitting method, and emphasize the importance of preserving the Jacobian (w.r.t. the observed signal) of the original estimator. Then, we provide an approach that has a ``twicing'' flavor a…

FOS: Computer and information sciencesInverse problemsMathematical optimization[ INFO.INFO-TS ] Computer Science [cs]/Signal and Image ProcessingComputer Vision and Pattern Recognition (cs.CV)General MathematicsComputer Science - Computer Vision and Pattern RecognitionMachine Learning (stat.ML)Mathematics - Statistics TheoryImage processingStatistics Theory (math.ST)02 engineering and technologyDebiasing[ INFO.INFO-CV ] Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV]01 natural sciencesRegularization (mathematics)Boosting010104 statistics & probabilitysymbols.namesake[INFO.INFO-TS]Computer Science [cs]/Signal and Image Processing[STAT.ML]Statistics [stat]/Machine Learning [stat.ML]Variational methods[MATH.MATH-ST]Mathematics [math]/Statistics [math.ST]Statistics - Machine LearningRefittingMSC: 49N45 65K10 68U10[ INFO.INFO-TI ] Computer Science [cs]/Image ProcessingFOS: Mathematics0202 electrical engineering electronic engineering information engineeringCovariant transformation[ MATH.MATH-ST ] Mathematics [math]/Statistics [math.ST]0101 mathematicsImage restoration[ STAT.ML ] Statistics [stat]/Machine Learning [stat.ML]MathematicsApplied Mathematics[INFO.INFO-CV]Computer Science [cs]/Computer Vision and Pattern Recognition [cs.CV]EstimatorInverse problem[INFO.INFO-TI]Computer Science [cs]/Image Processing [eess.IV]Jacobian matrix and determinantsymbolsTwicing020201 artificial intelligence & image processingAffine transformationAlgorithm
researchProduct