Computing Simple Circuits from a Set of Line Segments.
Computing the dimension of a semi-algebraic set.
Computing the Geodesic Center of a Simple Polygon.
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 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 -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...
Concurrently controlled grammars
This paper introduces a new variant of Petri net controlled grammars, namely a concurrently controlled grammar, where the control over the application of the productions of a grammar is realized by a Petri net with different parallel firing strategies. The generative capacity of these grammars is investigated with respect to transition labeling strategies, definitions of final marking sets and parallel transition firing modes. It is shown that the labeling strategies do not effect the computational...
Conditional Lindenmayer systems with subregular conditions: The non-extended case
We consider conditional tabled Lindenmayer sytems without interaction, where each table is associated with a regular set and a table can only be applied to a sentential form which is contained in its associated regular set. We study the effect to the generative power, if we use instead of arbitrary regular languages only finite, nilpotent, monoidal, combinational, definite, ordered, union-free, star-free, strictly locally testable, commutative regular, circular regular, and suffix-closed regular...
Conditional programmed automata
Cônes rationnels commutativement clos
Congruence classes in regular varieties.
Congruence, Similarity, and Symmetries of Geometric Objects.
Congruences parfaites et quasi-parfaites