Search results for "Efficient algorithm"

showing 3 items of 13 documents

Multiple Hypotheses Testing

1993

The paper is mainly concerned with multiple testing procedures which control a given multiple level α. General concepts for this purpose are the closure test and a modification which is independent of the special structure of hypotheses and tests. We consider improvements of this modification using information about the logical dependences (redundancies) within the system of hypotheses and present an efficient algorithm. Finally, we discuss some problems which are specific for hierarchical systems of hypotheses, e.g. in model search.

Structure (mathematical logic)Theoretical computer scienceEfficient algorithmComputer scienceMultiple comparisons problemMultiple hypothesesClosure (topology)Control (linguistics)Test (assessment)
researchProduct

Efficient evaluation for a subset of recursive queries

1991

Abstract We consider the efficient evaluation of recursive queries in logic databases where the queries are expressed using a Datalog program (function-free Horn-clause program) that contains only regularly or linearly recursive predicates. Using well-known results on graph traversal, we develop an efficient algorithm for evaluating relations defined by a binary-chain program. We also present a transformation by which the evaluation of a subset of queries involving nonbinary relations can be reduced to the evaluation of binary-chain queries. This transformation is guided by the choice of bound arguments in the query, and the bindings are propagated through the program so that in the evaluat…

Theoretical computer scienceComputer scienceLogic0102 computer and information sciences02 engineering and technologycomputer.software_genre01 natural sciencesDatalogSet (abstract data type)020204 information systemsGraph traversal0202 electrical engineering electronic engineering information engineeringComputer Science::Databasescomputer.programming_languageMathematicsDiscrete mathematicsProgramming languageBinary relationEfficient algorithmInformationSystems_DATABASEMANAGEMENT16. Peace & justiceTransformation (function)TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGESrestrict010201 computation theory & mathematicscomputerProceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems - PODS '87
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 \(\textit{pnw}(n)\) of prefix normal words of length n, showing that \(\textit{pnw}(n) =\Omega\left(2^{n - c\sqrt{n\ln n}}\right)\) for some c and \(\textit{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 t…

binary jumbled pattern matchingEfficient algorithmmembership testBinary numberContext (language use)Prefix Normal Word AlgorithmData_CODINGANDINFORMATIONTHEORYprefix normal wordsOmegaSubstringenumerationCombinatoricsPrefixprefix normal words; binary jumbled pattern matching; normal forms; enumeration; membership test; binary languagesEnumerationnormal formsbinary languagesWord (group theory)Mathematics
researchProduct