Search results for "Computation theory"
showing 10 items of 336 documents
Two-variable logics with counting and semantic constraints
2018
In this article we discuss fragments and extensions of two-variable logics motivated by practical applications. We outline the decidability frontier, describing some of the techniques developed for deciding satisfiability and finite satisfiability, as well as characterizing their complexity.
Data Quality Model-based Testing of Information Systems: the Use-case of E-scooters
2020
The paper proposes a data quality model-based testing methodology aimed at improving testing methodology of information systems (IS) using previously proposed data quality model. The solution supposes creation of a description of the data to be processed by IS and the data quality requirements used for the development of the tests, followed by performing an automated test of the system on the generated tests verifying the correctness of data to be entered and stored in the database. The generation of tests for all possible data quality conditions creates a complete set of tests that verify the operation of the IS under all possible data quality conditions. The proposed solution is demonstra…
CODING PARTITIONS OF REGULAR SETS
2009
A coding partition of a set of words partitions this set into classes such that whenever a sequence, of minimal length, has two distinct factorizations, the words of these factorizations belong to the same class. The canonical coding partition is the finest coding partition that partitions the set of words in at most one unambiguous class and other classes that localize the ambiguities in the factorizations of finite sequences. We prove that the canonical coding partition of a regular set contains a finite number of regular classes and we give an algorithm for computing this partition. From this we derive a canonical decomposition of a regular monoid into a free product of finitely many re…
The Many Faces of a Translation
2000
First-order translations have recently been characterized as the maps computed by aperiodic single-valued nondeterministic finite transducers (NFTs). It is shown here that this characterization lifts to "V-translations" and "V-single-valued-NFTs", where V is an arbitrary monoid pseudovariety. More strikingly, 2-way V-machines are introduced, and the following three models are shown exactly equivalent to Eilenberg's classical notion of a bimachine when V is a group variety or when V is the variety of aperiodic monoids: V-translations, V-single-valued-NFTs and 2-way V-transducers.
Suffix Array Construction on Multi-GPU Systems
2019
Suffix arrays are prevalent data structures being fundamental to a wide range of applications including bioinformatics, data compression, and information retrieval. Therefore, various algorithms for (parallel) suffix array construction both on CPUs and GPUs have been proposed over the years. Although providing significant speedup over their CPU-based counterparts, existing GPU implementations share a common disadvantage: input text sizes are limited by the scarce memory of a single GPU. In this paper, we overcome aforementioned memory limitations by exploiting multi-GPU nodes featuring fast NVLink interconnects. In order to achieve high performance for this communication-intensive task, we …
Dimension enrichment with factual data during the design of multidimensional models: application to bird biodiversity
2015
20 pages; International audience; Data warehouses (DW) and OLAP systems are technologies allowing the on-line analysis of huge volume of data according to decision-makers’ needs. Designing DW involves taking into account functional requirements and data sources (mixed design methodology) [1]. But, for complex applications, existing automatic design methodologies seem inefficient. In some cases, decision-makers need querying, as a dimension, data which have been defined as facts by actual automatic mixed approachs. Therefore, in this paper, we offer a new mixed refinement methodology relevant to constellation multidimensional schema. The proposed methodolgy allows to decision-makers to enric…
Validation of indicators for implementing an adaptive platform for MOOCs
2017
Personalization techniques are a classic solution recommended by many experts for improving learning. Information and communication technologies and online courses have helped reduce the difficulties teachers face with a diversity of student profiles and a large number of students in a classroom. When these factors are extreme, like in a Massive Open Online Course (MOOC), those techniques may be the solution. However, even the most sophisticated technologies have not solved all the challenges posed by personalized learning, and in cases where teachers are not skilled in the technology they must use, the adaptive systems have only complicated the implementation of online courses. Therefore, …
Complexity of operations on cofinite languages
2010
International audience; We study the worst case complexity of regular operation on cofinite languages (i.e., languages whose complement is finite) and provide algorithms to compute efficiently the resulting minimal automata.
Quantum algorithms for search with wildcards and combinatorial group testing
2012
We consider two combinatorial problems. The first we call "search with wildcards": given an unknown n-bit string x, and the ability to check whether any subset of the bits of x is equal to a provided query string, the goal is to output x. We give a nearly optimal O(sqrt(n) log n) quantum query algorithm for search with wildcards, beating the classical lower bound of Omega(n) queries. Rather than using amplitude amplification or a quantum walk, our algorithm is ultimately based on the solution to a state discrimination problem. The second problem we consider is combinatorial group testing, which is the task of identifying a subset of at most k special items out of a set of n items, given the…
Object Migration Automata for Non-equal Partitioning Problems with Known Partition Sizes
2021
Part 4: Automated Machine Learning; International audience; Solving partitioning problems in random environments is a classic and challenging task, and has numerous applications. The existing Object Migration Automaton (OMA) and its proposed enhancements, which include the Pursuit and Transitivity phenomena, can solve problems with equi-sized partitions. Currently, these solutions also include one where the partition sizes possess a Greatest Common Divisor (GCD). In this paper, we propose an OMA-based solution that can solve problems with both equally and non-equally-sized groups, without restrictions on their sizes. More specifically, our proposed approach, referred to as the Partition Siz…