Search results for "Algorithm"

showing 10 items of 4887 documents

The Descriptive Complexity Approach to LOGCFL

1999

Building upon the known generalized-quantifier-based firstorder 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 contextfree language" is LOGCFL-complete under quantifier-free BIT-free interpre…

Discrete mathematicsUnary operationComputer science0102 computer and information sciences02 engineering and technologyComputer Science::Computational ComplexityArityDescriptive complexity theory01 natural sciencesNondeterministic algorithm010201 computation theory & mathematicsDeterministic automatonBIT predicate0202 electrical engineering electronic engineering information engineering020201 artificial intelligence & image processingNondeterministic finite automatonLOGCFL
researchProduct

Frequency Assignment and Multicoloring Powers of Square and Triangular Meshes

2005

The static frequency assignment problem on cellular networks can be abstracted as a multicoloring problem on a weighted graph, where each vertex of the graph is a base station in the network, and the weight associated with each vertex represents the number of calls to be served at the vertex. The edges of the graph model interference constraints for frequencies assigned to neighboring stations. In this paper, we first propose an algorithm to multicolor any weighted planar graph with at most $\frac{11}{4}W$ colors, where W denotes the weighted clique number. Next, we present a polynomial time approximation algorithm which garantees at most 2W colors for multicoloring a power square mesh. Fur…

Discrete mathematicsVertex (graph theory)Frequency assignmentUpper and lower boundsPlanar graphCombinatoricssymbols.namesakeDistributed algorithmTriangle meshCellular networksymbolsPolygon meshMathematicsofComputing_DISCRETEMATHEMATICSComputingMethodologies_COMPUTERGRAPHICSMathematics
researchProduct

Numerical approximation of mixed models for digital integrated circuits

1991

To analyse an electrical network many CAD (Computer Aided Design) circuit simulators are available today. The most well-known is probably SPICE -Nagel [1975]. Although this type of simulator is able to precisely compute the transient performances (as delay time), the usage of complete models of devices implies an extremely high time consumption. So, the circuit simulators are unappropriate for the initial stage of VLSI design where a high speed timing analyser (“timing simulator”) is required. To this goal, alternative approaches using either simpler device models or simpler numerical algorithms or easily computable formulae for delay time approximation, have been developed in the past deca…

Discrete mathematicsVery-large-scale integrationComputer scienceSpiceAnalyserCADcomputer.software_genrelaw.inventionTree (data structure)lawElectrical networkComputer Aided DesignTransient (computer programming)Algorithmcomputer
researchProduct

Online Scheduling of Task Graphs on Heterogeneous Platforms

2020

Modern computing platforms commonly include accelerators. We target the problem of scheduling applications modeled as task graphs on hybrid platforms made of two types of resources, such as CPUs and GPUs. We consider that task graphs are uncovered dynamically, and that the scheduler has information only on the available tasks, i.e., tasks whose predecessors have all been completed. Each task can be processed by either a CPU or a GPU, and the corresponding processing times are known. Our study extends a previous $4\sqrt{m/k}$ 4 m / k -competitive online algorithm by Amaris et al. [1] , where $m$ m is the number of CPUs and $k$ k the number of GPUs ( $m\geq k$ m ≥ k ). We prove that no online…

Discrete mathematics[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]020203 distributed computingScheduleCompetitive analysisComputer scienceHeuristicSchedulingOnline algorithmsProcessor schedulingSymmetric multiprocessor system02 engineering and technologyUpper and lower boundsGraphScheduling (computing)Computational Theory and MathematicsHardware and ArchitectureSignal Processing0202 electrical engineering electronic engineering information engineeringTask analysisTask graphsHeterogeneous computingOnline algorithm[INFO.INFO-DC]Computer Science [cs]/Distributed Parallel and Cluster Computing [cs.DC]
researchProduct

New Encodings of Pseudo-Boolean Constraints into CNF

2009

International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.

Discrete mathematics[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]Polynomial021103 operations researchUnit propagation[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]0211 other engineering and technologies[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]02 engineering and technologyComputer Science::Computational ComplexityExpressive powerExponential functionCombinatorics[ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC]Encoding (memory)0202 electrical engineering electronic engineering information engineeringLocal consistency020201 artificial intelligence & image processingPoint (geometry)[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC][ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Mathematics
researchProduct

A genetic system based on simulated crossover of sequences of two-bit genes

2006

AbstractWe introduce a genetic model based on simulated crossover of fixed sequences of two-bit genes. Results are(1)a lower bound on population size is exhibited such that a transition takes the stochastic finite population genetic system near the next state of the deterministic infinite population genetic system (provided both begin in the same state);(2)states and dynamics of the deterministic infinite population genetic system are derived for arbitrary (finite) fitness functions (expressed in terms of multivariate polynomials);(3)in the case of quadratic fitness defined by weight matrices with m nonnull entries it is shown that each state transition can be implemented in time O(m+l), wh…

Discrete mathematicseducation.field_of_studyGeneral Computer SciencePopulation sizeCrossoverPopulationState (functional analysis)Upper and lower boundsQuantitative Biology::GenomicsTheoretical Computer ScienceMarginal distribution genetic algorithmsChromosome (genetic algorithm)Genetic modelGenetic algorithmMax-cut problemeducationAlgorithmComputer Science(all)MathematicsTheoretical Computer Science
researchProduct

The Spanning Tree based Approach for Solving the Shortest Path Problem in Social Graphs

2016

Nowadays there are many social media sites with a very large number of users. Users of social media sites and relationships between them can be modelled as a graph. Such graphs can be analysed using methods from social network analysis (SNA). Many measures used in SNA rely on computation of shortest paths between nodes of a graph. There are many shortest path algorithms, but the majority of them suits only for small graphs, or work only with road network graphs that are fundamentally different from social graphs. This paper describes an efficient shortest path searching algorithm suitable for large social graphs. The described algorithm extends the Atlas algorithm. The proposed algorithm so…

Discrete mathematicsta113Mathematical optimizationSpanning treesocial network analysisComputer scienceAtlas algorithm020206 networking & telecommunications02 engineering and technologyLongest path problemverkostoanalyysiWidest path problemOdnoklassnikiEuclidean shortest pathShortest Path Faster Algorithmsocial graph020204 information systemsShortest path problem0202 electrical engineering electronic engineering information engineeringK shortest path routingCanadian traveller problemshortest path problemMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

Developing and Integrating Advanced Movement Features Improves Automated Classification of Ciliate Species

2015

Recent advances in tracking technologies such as GPS or video tracking systems describe the movement paths of individuals in unprecedented details and are increasingly used in different fields, including ecology. However, extracting information from raw movement data requires advanced analysis techniques, for instance to infer behaviors expressed during a certain period of the recorded trajectory, or gender or species identity in case data is obtained from remote tracking. In this paper, we address how different movement features affect the ability to automatically classify the species identity, using a dataset of unicellular microbes (i.e., ciliates). Previously, morphological attributes a…

Discrete wavelet transformAquatic OrganismsScienceMovementDecision tree1100 General Agricultural and Biological SciencesTheoretical ecologyBiologyMachine learningcomputer.software_genre1300 General Biochemistry Genetics and Molecular BiologyEnvironmental monitoringEntropy (information theory)910 Geography & travelCiliophora1000 MultidisciplinaryMultidisciplinarybusiness.industryEcologyQRWavelet transformCorrection10122 Institute of GeographyVideo trackingRemote Sensing TechnologyGlobal Positioning SystemMedicineArtificial intelligencebusinesscomputerAlgorithmsResearch ArticlePloS one
researchProduct

Data Compression Using Wavelet and Local Cosine Transforms

2015

The chapter describes an algorithm that compresses two-dimensional data arrays, which are piece-wise smooth in one direction and have oscillating events in the other direction. Seismic, hyper-spectral and fingerprints data, for example, have such a mixed structure. The transform part of the compression process is an algorithm that combines wavelet and local cosine transform (LCT). The quantization and the entropy coding parts of the compression are taken from the SPIHT codec. To efficiently apply the SPIHT codec to a mixed coefficients array, reordering of the LCT coefficients takes place. On the data arrays, which have the mixed structure, this algorithm outperforms other algorithms that a…

Discrete wavelet transformComputer scienceComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISIONWavelet transformData_CODINGANDINFORMATIONTHEORYcomputer.file_formatWavelet packet decompositionSet partitioning in hierarchical treesWaveletJPEG 2000Discrete cosine transformAlgorithmcomputerData compression
researchProduct

Automated detection and localization system of myocardial infarction in single-beat ECG using Dual-Q TQWT and wavelet packet tensor decomposition.

2019

Abstract Background and objective It is challenging to conduct real-time identification of myocardial infarction (MI) due to artifact corruption and high dimensionality of multi-lead electrocardiogram (ECG). In the present study, we proposed an automated single-beat MI detection and localization system using dual-Q tunable Q-factor wavelet transformation (Dual-Q TQWT) denoising algorithm. Methods After denoising and segmentation of ECG, a fourth-order wavelet tensor (leads × subbands × samples × beats) was constructed based on the discrete wavelet packet transform (DWPT), to represent the features considering the information of inter-beat, intra-beat, inter-frequency, and inter-lead. To red…

Discrete wavelet transformComputer scienceNoise reductionMyocardial InfarctionWavelet AnalysisHealth InformaticsHilbert–Huang transform030218 nuclear medicine & medical imaging03 medical and health sciencesAutomationElectrocardiography0302 clinical medicineWaveletHumansSegmentationPrincipal Component Analysisbusiness.industryReproducibility of ResultsPattern recognitionSignal Processing Computer-AssistedMultilinear principal component analysisComputer Science ApplicationsCase-Control StudiesArtificial intelligencebusinessClassifier (UML)030217 neurology & neurosurgerySoftwareAlgorithmsComputer methods and programs in biomedicine
researchProduct