Computing the dimension of a semi-algebraic set.
Computing the discrete compactness of orthogonal pseudo-polytopes via their D-EVM representation.
Computing the Ehrhart Polynomial of a Convex Lattice Polytope.
Computing the Geodesic Center of a Simple Polygon.
Computing the integral closure of an affine semigroup.
Computing the jth solution of a first-order query
We design algorithms of “optimal" data complexity for several natural problems about first-order queries on structures of bounded degree. For that purpose, we first introduce a framework to deal with logical or combinatorial problems R ⊂ I x O whose instances x ∈ I may admit of several solutions R(x) = {y ∈ O : (x,y) ∈ R}. One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution y ∈ R(x); enumerate without repetition each solution...
Computing the Link Center of a Simple Polygon.
Computing the period of an Ehrhart quasi-polynomial.
Computing the prefix of an automaton
Computing the prefix of an automaton
We present an algorithm for computing the prefix of an automaton. Automata considered are non-deterministic, labelled on words, and can have ε-transitions. The prefix automaton of an automaton has the following characteristic properties. It has the same graph as . Each accepting path has the same label as in . For each state q, the longest common prefix of the labels of all paths going from q to an initial or final state is empty. The interest of the computation of the prefix of an...
Computing the Rabin index of a parity automaton
Computing the Rabin Index of a Parity Automaton
The Rabin index of a rational language of infinite words given by a parity automaton with n states is computable in time O(n2c) where c is the cardinality of the alphabet. The number of values used by a parity acceptance condition is always greater than the Rabin index and conversely, the acceptance condition of a parity automaton can always be replaced by an equivalent acceptance condition whose number of used values is exactly the Rabin index. This new acceptance condition can also be...
Computing the Volume, Counting Integral Points, and Exponential Sums.
Computing the Volume is Difficult.
Computing with words and life data
The problem of statistical inference on the mean lifetime in the presence of vague data is considered. Situations with fuzzy lifetimes and an imprecise number of failures are discussed.
Computing with words with the use of inverse RDM models of membership functions
Computing with words is a way to artificial, human-like thinking. The paper shows some new possibilities of solving difficult problems of computing with words which are offered by relative-distance-measure RDM models of fuzzy membership functions. Such models are based on RDM interval arithmetic. The way of calculation with words was shown using a specific problem of flight delay formulated by Lotfi Zadeh. The problem seems easy at first sight, but according to the authors' knowledge it has not...
Computing -free NFA from regular expressions in time
Computing ϵ-Free NFA from Regular Expressions in O(n log2(n)) Time
The standard procedure to transform a regular expression of size n to an ϵ-free nondeterministic finite automaton yields automata with O(n) states and O(n2) transitions. For a long time this was supposed to be also the lower bound, but a result by Hromkovic et al. showed how to build an ϵ-free NFA with only O(n log2(n)) transitions. The current lower bound on the number of transitions is Ω(n log(n)). A rough running time estimation for the common follow sets (CFS) construction proposed...
Concentration of measure and isoperimetric inequalities in product spaces
Concept approximations based on rough sets and similarity measures
The formal concept analysis gives a mathematical definition of a formal concept. However, in many real-life applications, the problem under investigation cannot be described by formal concepts. Such concepts are called the non-definable concepts (Saquer and Deogun, 2000a). The process of finding formal concepts that best describe non-definable concepts is called the concept approximation. In this paper, we present two different approaches to the concept approximation. The first approach is based...