Search results for "A* algorithm"

showing 10 items of 2538 documents

Ultrametric Finite Automata and Turing Machines

2013

We introduce a notion of ultrametric automata and Turing machines using p-adic numbers to describe random branching of the process of computation. These automata have properties similar to the properties of probabilistic automata but complexity of probabilistic automata and complexity of ultrametric automata can differ very much.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceComputer scienceSuper-recursive algorithmProbabilistic Turing machineDescription numberNonlinear Sciences::Cellular Automata and Lattice GasesTuring machinesymbols.namesakeTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring completenesssymbolsQuantum finite automataAutomata theoryTwo-way deterministic finite automatonComputer Science::Formal Languages and Automata TheoryMathematicsofComputing_DISCRETEMATHEMATICS
researchProduct

How to simulate free will in a computational device

1999

Since we believe that human brain is not a purely deterministic device merely reacting to the environment but rather it is capable to a free will, Theoretical Computer Science has also tried to develop a system of notions generalizing determinism. Nondeterministic and probabilistic algorithms were the first generalizations. Nondeterministic machines constitute an important part of the Theory of Computation. Nondeterminism is a useful way to describe possible choices. In real life there are many regulations restricting our behavior. These regulations nearly always leave some freedom for us how to react. Such regulations are best described in terms of nondeterministic algorithms. Nondetermini…

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceProperty (philosophy)General Computer ScienceComputer scienceProbabilistic logicDeterminismTheoretical Computer ScienceMoment (mathematics)Nondeterministic algorithmTuring machinesymbols.namesakeTheory of computationsymbolsProbabilistic analysis of algorithmsACM Computing Surveys
researchProduct

Quantum Real - Time Turing Machine

2001

The principles of quantum computation differ from the principles of classical computation very much. Quantum analogues to the basic constructions of the classical computation theory, such as Turing machine or finite 1-way and 2-ways automata, do not generalize deterministic ones. Their capabilities are incomparable. The aim of this paper is to introduce a quantum counterpart for real - time Turing machine. The recognition of a special kind of language, that can't be recognized by a deterministic real - time Turing machine, is shown.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineDTIMEComputer scienceProbabilistic Turing machine2-EXPTIMESuper-recursive algorithmComputationDescription numberDSPACElaw.inventionsymbols.namesakeTuring machineTuring completenessNon-deterministic Turing machinelawAlgorithm characterizationsQuantumPSPACEQuantum computerFinite-state machineTuring machine examplesNSPACETheoryofComputation_GENERALAutomatonTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESTuring reductionTheory of computationsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineComputer Science::Formal Languages and Automata TheoryRegister machine
researchProduct

Space-Efficient 1.5-Way Quantum Turing Machine

2001

1.5QTM is a sort of QTM (Quantum Turing Machine) where the head cannot move left (it can stay where it is and move right). For computations is used other - work tape. In this paper will be studied possibilities to economize work tape space more than the same deterministic Turing Machine can do (for some of the languages). As an example language (0i1i|i ≥ 0) is chosen, and is proved that this language could be recognized by deterministic Turing machine using log(i) cells on work tape , and 1.5QTM can recognize it using constant cells quantity.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESTheoretical computer scienceQuantum Turing machineSuper-recursive algorithmComputer scienceProbabilistic Turing machineComputationDescription numberMultitape Turing machineDSPACElaw.inventionTuring machinesymbols.namesakeNon-deterministic Turing machinelawAlgorithm characterizationsPSPACEWolfram's 2-state 3-symbol Turing machineTuring machine examplesNSPACETuring reductionsymbolsUniversal Turing machineTime hierarchy theoremAlternating Turing machineRegister machine
researchProduct

Automata and forbidden words

1998

Abstract Let L ( M ) be the (factorial) language avoiding a given anti-factorial language M . We design an automaton accepting L ( M ) and built from the language M . The construction is effective if M is finite. If M is the set of minimal forbidden words of a single word ν, the automaton turns out to be the factor automaton of ν (the minimal automaton accepting the set of factors of ν). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a nontrivial upper bound on the number of minimal forbidden words of a word.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Büchi automaton0102 computer and information sciences02 engineering and technologyω-automaton01 natural sciencesTheoretical Computer ScienceCombinatoricsDeterministic automaton0202 electrical engineering electronic engineering information engineeringTwo-way deterministic finite automatonNondeterministic finite automatonMathematicsPowerset constructionLevenshtein automaton020206 networking & telecommunicationsComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)Nonlinear Sciences::Cellular Automata and Lattice GasesComputer Science ApplicationsTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematicsSignal ProcessingProbabilistic automatonComputer Science::Programming LanguagesComputer Science::Formal Languages and Automata TheoryInformation Systems
researchProduct

Minimal forbidden words and factor automata

1998

International audience; Let L(M) be the (factorial) language avoiding a given antifactorial language M. We design an automaton accepting L(M) and built from the language M. The construction is eff ective if M is finite. If M is the set of minimal forbidden words of a single word v, the automaton turns out to be the factor automaton of v (the minimal automaton accepting the set of factors of v). We also give an algorithm that builds the trie of M from the factor automaton of a single word. It yields a non-trivial upper bound on the number of minimal forbidden words of a word.

TheoryofComputation_COMPUTATIONBYABSTRACTDEVICESfailure functionfactor code[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Büchi automatonComputerApplications_COMPUTERSINOTHERSYSTEMS[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]0102 computer and information sciencesavoiding a wordω-automaton01 natural sciencesfactorial languageReversible cellular automatonCombinatoricsDeterministic automatonanti-factorial languageNondeterministic finite automaton0101 mathematicsMathematicsfactor automatonPowerset constructionLevenshtein automaton010102 general mathematicsforbidden wordComputer Science::Computation and Language (Computational Linguistics and Natural Language and Speech Processing)16. Peace & justiceNonlinear Sciences::Cellular Automata and Lattice GasesTheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES010201 computation theory & mathematicsProbabilistic automatonPhysics::Accelerator PhysicsComputer Science::Programming LanguagesHigh Energy Physics::ExperimentComputer Science::Formal Languages and Automata Theory
researchProduct

A novel mutation (Thr116IIe) in the presenilin 1 gene in a patient with early-onset Alzheimer's disease

2004

We report a novel presenilin 1 (PSN1) mutation (Thr116Ile) in a woman with early onset Alzheimer's disease (AD). This mutation was not found in 100 healthy controls, indicating that this is not a common polymorphism. The patient presented with forgetfulness at age 45, followed over the next 3 years by a worsening of the memory loss and frequent episodes of confusion and spatial disorientation. Neuroimaging studies were consistent with AD. The analysis of the family's pedigree showed that the proband was apparently the only member affected. Because the early death of several close relatives (i.e. the mother and the grandmother) and the demonstration that the father is not a mutation carrier,…

ThreonineProbandDNA Mutational AnalysisDiseaseBioinformaticsGenetic analysisPresenilinMutation CarrierAlzheimer DiseasePolymorphism (computer science)Presenilin-1medicineHumansEarly-onset Alzheimer's diseaseIsoleucineGeneticsbusiness.industryMembrane ProteinsMiddle Agedmedicine.diseaseNeurologyMutationMutation (genetic algorithm)FemaleSettore MED/26 - NeurologiaNeurology (clinical)businessAlzheimer's Disease Novel mutation Presenilin 1
researchProduct

Worldwide burden of LDL cholesterol: Implications in cardiovascular disease

2020

Abstract Background and aim an increased value of low-density lipoprotein cholesterol (LDL-C) is now universally considered a major cardiovascular disease (CVD) risk factor. LDL-C is included in the vast majority of worldwide cardiovascular risk prediction algorithms, as well as in the guidelines for cardiovascular risk prevention. We aimed to provide an overview of the worldwide adverse healthcare impact of low-density lipoprotein cholesterol (LDL-C). Methods and results Data on the epidemiologic burden of LDL-C >1.3 mmol/L were retrieved from Global Health Data Exchange (GHDx) registry. The current burden is 94.92 million disability-adjusted life years (DALYs), with an exponential increas…

Time FactorsDatabases FactualHealth StatusEndocrinology Diabetes and MetabolismMedicine (miscellaneous)030209 endocrinology & metabolismDisease030204 cardiovascular system & hematologyGlobal HealthRisk Assessment03 medical and health scienceschemistry.chemical_compound0302 clinical medicineRisk FactorsEnvironmental healthHealth careGlobal healthHumansMedicineRegistriesRisk factorEpidemicsAtherosclerosis; Cardiovascular disease; Cholesterol; Low-density lipoproteinsDyslipidemiasLdl cholesterolNutrition and Dieteticsbusiness.industryCholesterolCholesterol LDLAtherosclerosisCardiovascular diseaseUp-RegulationPrediction algorithmsCholesterolchemistryCardiovascular DiseasesLow-density lipoproteinslipids (amino acids peptides and proteins)Risk preventionQuality-Adjusted Life YearsCardiology and Cardiovascular MedicinebusinessBiomarkersNutrition, Metabolism and Cardiovascular Diseases
researchProduct

Discrete Tomography Reconstruction Through a New Memetic Algorithm

2008

Discrete tomography is a particular case of computerized tomography that deals with the reconstruction of objects made of just one homogeneous material, where it is sometimes possible to reduce the number of projections to no more than four. Most methods for standard computerized tomography cannot be applied in the former case and ad hoc techniques must be developed to handle so few projections.

Tomographic reconstructionSettore INF/01 - Informaticabusiness.industryBinary imageGenetic algorithmInstrumental noiseMemetic algorithmComputer visionTomographyArtificial intelligenceDiscrete Tomography Memetic Algorithms Evolutionary methods.businessDiscrete tomographyMathematics
researchProduct

Multi-label Classification Using Stacked Hierarchical Dirichlet Processes with Reduced Sampling Complexity

2018

Nonparametric topic models based on hierarchical Dirichlet processes (HDPs) allow for the number of topics to be automatically discovered from the data. The computational complexity of standard Gibbs sampling techniques for model training is linear in the number of topics. Recently, it was reduced to be linear in the number of topics per word using a technique called alias sampling combined with Metropolis Hastings (MH) sampling. We propose a different proposal distribution for the MH step based on the observation that distributions on the upper hierarchy level change slower than the document-specific distributions at the lower level. This reduces the sampling complexity, making it linear i…

Topic modelComputational complexity theoryComputer science02 engineering and technologyLatent Dirichlet allocationDirichlet distributionsymbols.namesakeArtificial Intelligence020204 information systems0202 electrical engineering electronic engineering information engineeringMathematicsMulti-label classificationbusiness.industrySampling (statistics)Pattern recognitionHuman-Computer InteractionDirichlet processMetropolis–Hastings algorithmHardware and ArchitectureTest setsymbols020201 artificial intelligence & image processingArtificial intelligencebusinessAlgorithmSoftwareInformation SystemsGibbs sampling2017 IEEE International Conference on Big Knowledge (ICBK)
researchProduct