Search results for "Algorithm"

showing 10 items of 4887 documents

Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer

2007

Consider the problem of evaluating an AND-OR formula on an $N$-bit black-box input. We present a bounded-error quantum algorithm that solves this problem in time $N^{1/2+o(1)}$. In particular, approximately balanced formulas can be evaluated in $O(\sqrt{N})$ queries, which is optimal. The idea of the algorithm is to apply phase estimation to a discrete-time quantum walk on a weighted tree whose spectrum encodes the value of the formula.

Discrete mathematicsQuantum t-designComputational complexity theoryGeneral Computer ScienceGeneral MathematicsSpectrum (functional analysis)Value (computer science)0102 computer and information sciencesTree (graph theory)01 natural sciencesCombinatoricsTree (descriptive set theory)Discrete time and continuous time010201 computation theory & mathematics0103 physical sciencesQuantum operationQuantum phase estimation algorithmQuantum Fourier transformQuantum walkQuantum algorithm010306 general physicsMathematicsQuantum computerSIAM Journal on Computing
researchProduct

Logics for context-free languages

1995

We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.

Discrete mathematicsRange (mathematics)Class (set theory)Quantifier (logic)Symbol (programming)Context-free languageAbstract family of languagesOrder (group theory)Of the formAlgorithmMathematics
researchProduct

Circular sturmian words and Hopcroft’s algorithm

2009

AbstractIn order to analyze some extremal cases of Hopcroft’s algorithm, we investigate the relationships between the combinatorial properties of a circular sturmian word (x) and the run of the algorithm on the cyclic automaton Ax associated to (x). The combinatorial properties of words taken into account make use of sturmian morphisms and give rise to the notion of reduction tree of a circular sturmian word. We prove that the shape of this tree uniquely characterizes the word itself. The properties of the run of Hopcroft’s algorithm are expressed in terms of the derivation tree of the automaton, which is a tree that represents the refinement process that, in the execution of Hopcroft’s alg…

Discrete mathematicsReduction (recursion theory)Fibonacci numberGeneral Computer ScienceHopcroft'algorithmSturmian wordSturmian wordSturmian morphismsTheoretical Computer ScienceCombinatoricsTree (descriptive set theory)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESComputer Science::Discrete MathematicsDeterministic automatonHopcroft’s minimization algorithmCircular sturmian wordsTree automatonDeterministic finite state automataTime complexityAlgorithmComputer Science::Formal Languages and Automata TheoryWord (group theory)Computer Science(all)MathematicsTheoretical Computer Science
researchProduct

Efficient algorithm for learning simple regular expressions from noisy examples

1994

We present an efficient algorithm for finding approximate repetitions in a given sequence of characters. First, we define a class of simple regular expressions which are of star-height one and do not contain union operations, and a stochastic mutation process of a given length over a string of characters. Then, assuming that a given string of characters is obtained corrupted by the defined mutation process from some long enough word generated by a simple regular expression, we try to restore the expression. We prove that to within some reasonable accuracy it is always possible if the length of the mutation process is bounded comparing to the length of the example. We provide an algorithm by…

Discrete mathematicsRegular languageComputer scienceBounded functionString (computer science)Mutation (genetic algorithm)Edit distanceRegular expressionExpression (computer science)Time complexity
researchProduct

Locality of order-invariant first-order formulas

1998

A query is local if the decision of whether a tuple in a structure satisfies this query only depends on a small neighborhood of the tuple. We prove that all queries expressible by order-invariant first-order formulas are local.

Discrete mathematicsRelational databaseComputer Science::Information RetrievalInformationSystems_INFORMATIONSTORAGEANDRETRIEVALLocalityStructure (category theory)InformationSystems_DATABASEMANAGEMENTFirst orderComplexity classOrder (group theory)Invariant (mathematics)TupleAlgorithmComputer Science::DatabasesMathematics
researchProduct

Discrete Mathematics in Lower School Grades? Situation and Possibilities in Italy

2017

This paper presents an overview of the Italian situation in teaching discrete mathematics in primary and middle school, taking into account the national teaching guidelines and their connection with the subject. We describe research conducted with about 150 teachers, interviewed in a preliminary questionnaire. The data collected shows, for all teaching grades, interest in having more discrete mathematics in the school curriculum even if there are some difficulties in teaching it and in inserting it in the usual mathematical activities at school, mostly related to teachers’ knowledge and self-confidence about the subject. We also discuss results and future plans for a continuing research pro…

Discrete mathematicsResearch designProcess (engineering)Computational thinkingComputingMilieux_COMPUTERSANDEDUCATIONSubject (documents)Design research Computational thinking Algorithms Programming UnpluggedSettore MAT/04 - Matematiche ComplementariPsychologyCurriculum
researchProduct

On the longest common factor problem

2008

The Longest Common Factor (LCF) of a set of strings is a well studied problem having a wide range of applications in Bioinformatics: from microarrays to DNA sequences analysis. This problem has been solved by Hui (2000) who uses a famous constant-time solution to the Lowest Common Ancestor (LCA) problem in trees coupled with use of suffix trees. A data structure for the LCA problem, although linear in space and construction time, introduces a multiplicative constant in both space and time that reduces the range of applications in many biological applications. In this article we present a new method for solving the LCF problem using the suffix tree structure with an auxiliary array that take…

Discrete mathematicsSettore INF/01 - InformaticaSuffix tree[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]Generalized suffix treeDAWGsuffix tree[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Data structureLongest common substring problemlaw.inventionCombinatoricsSet (abstract data type)Range (mathematics)lawLongest Common Factor ProblemSuffixLowest common ancestorMathematics
researchProduct

Conjunction and Disjunction Among Conditional Events

2017

We generalize, in the setting of coherence, the notions of conjunction and disjunction of two conditional events to the case of n conditional events. Given a prevision assessment on the conjunction of two conditional events, we study the set of coherent extensions for the probabilities of the two conditional events. Then, we introduce by a progressive procedure the notions of conjunction and disjunction for n conditional events. Moreover, by defining the negation of conjunction and of disjunction, we show that De Morgan’s Laws still hold. We also show that the associative and commutative properties are satisfied. Finally, we examine in detail the conjunction for a family \(\mathcal F\) of t…

Discrete mathematicsSettore MAT/06 - Probabilita' E Statistica MatematicaComputer scienceConditional events · Conditional random quantities · Con- junction · Disjunction · Negation · Quasi conjunction · Coherent previ- sion assessments · Coherent extensions · De Morgan’s Laws02 engineering and technologyCoherence (philosophical gambling strategy)Settore MAT/01 - Logica Matematica01 natural sciencesDe Morgan's lawsConjunction (grammar)Set (abstract data type)010104 statistics & probabilitysymbols.namesakeNegation0202 electrical engineering electronic engineering information engineeringsymbols020201 artificial intelligence & image processing0101 mathematicsAlgorithmCommutative propertyAssociative propertyEvent (probability theory)
researchProduct

Randomized renaming in shared memory systems.

2021

Abstract Renaming is a task in distributed computing where n processes are assigned new names from a name space of size m . The problem is called tight if m = n , and loose if m > n . In recent years renaming came to the fore again and new algorithms were developed. For tight renaming in asynchronous shared memory systems, Alistarh et al. describe a construction based on the AKS network that assigns all names within O ( log n ) steps per process. They also show that, depending on the size of the name space, loose renaming can be done considerably faster. For m = ( 1 + ϵ ) ⋅ n and constant ϵ , they achieve a step complexity of O ( log log n ) . In this paper we consider tight as well as loos…

Discrete mathematicsShared memory modelSpeedupComputer Networks and CommunicationsComputer science020206 networking & telecommunications02 engineering and technologyParallel computingTheoretical Computer ScienceRandomized algorithmTask (computing)Constant (computer programming)Shared memoryArtificial IntelligenceHardware and ArchitectureAsynchronous communicationDistributed algorithm0202 electrical engineering electronic engineering information engineeringOverhead (computing)020201 artificial intelligence & image processingSoftware
researchProduct

Minimum node weight spanning trees searching algorithm for broadcast transmission in sensor networks

2017

A minimum node weight spanning tree in a weighted, directed graph is a tree whose node with maximum out-weight is minimal among all spanning trees. This type of trees are important because they appear in the solutions of the maximum lifetime broadcasting problem in wireless sensor networks. In a complete graph build of N nodes there are NN-2 spanning trees and to find such trees it is necessary to perform more than O(NN-2) operations. In this paper we propose an algorithm for searching the minimum node weight spanning trees in the graph. In the proposed algorithm, instead of calculating the symbolic determinant of the generalized Laplacian matrix, numerical operations on its exponents are p…

Discrete mathematicsSpanning treeComputer sciencegraph theory010401 analytical chemistryDecision treeComplete graph020206 networking & telecommunications02 engineering and technologyDirected graphspanning trees01 natural sciences0104 chemical sciencessensor networksSearch algorithm0202 electrical engineering electronic engineering information engineeringGraph (abstract data type)Algorithm designLaplacian matrixdata broadcasting2017 Twelfth International Conference on Digital Information Management (ICDIM)
researchProduct