On the Algebraic Complexity of Sets of Functions
On the analysis of Petri nets and their synthesis from process languages
Processes in Place/Transition (P/T) nets are defined inductively by a peculiar numbering of place occurrences. Along with an associative sequential composition called catenation and a neutral process, a monoid of processes is obtained. The power algebra of this monoid contains all process languages with appropriate operations on them. Hence the problems of analysis and synthesis, analogous to those in the formal languages and automata theory, arise. Here, the analysis problem is: for a given P/T...
On the Analysis of Petri Nets and their Synthesis from Process Languages
Processes in Place/Transition (P/T) nets are defined inductively by a peculiar numbering of place occurrences. Along with an associative sequential composition called catenation and a neutral process, a monoid of processes is obtained. The power algebra of this monoid contains all process languages with appropriate operations on them. Hence the problems of analysis and synthesis, analogous to those in the formal languages and automata theory, arise. Here, the analysis problem is: for a given P/T...
On the application of parallel architectures to a class of operations research problems
On the approximability of comparing genomes with duplicates.
On the approximation of min split-coloring and min cocoloring.
On the arc length of parametric cubic curves.
On the average case complexity of some P-complete problems
On the Average Case Complexity of Some P-complete Problems
We show that some classical P-complete problems can be solved efficiently in average NC. The probabilistic model we consider is the sample space of input descriptions of the problem with the underlying distribution being the uniform one. We present parallel algorithms that use a polynomial number of processors and have expected time upper bounded by (e ln 4 + o(1))log n, asymptotically with high probability, where n is the instance size.
On the average minimal prefix-length of the generalized semi-Dycklanguage
On the average number of registers needed to evaluate a special class of backtrack trees
On the Ball Spanned by Balls.
On the Bayesian inductive processes
On the behaviour of learning algorithms in a changing environment with application to data network routing problem
On the binary expansion of irrational algebraic numbers
On the bisectors of weakly separable sets.
On the categorical semantics of elementary linear logic.
On the classes of languages accepted by limited context restarting automata
In the literature various types of restarting automata have been studied that are based on contextual rewriting. A word w is accepted by such an automaton if, starting from the initial configuration that corresponds to input w, the word w is reduced to the empty word by a finite number of applications of these contextual rewritings. This approach is reminiscent of the notion of McNaughton families of languages. Here we put the aforementioned types of restarting automata into the context of McNaughton...
On the comparison of some fuzzy clustering methods for privacy preserving data mining: Towards the development of specific information loss measures
Policy makers and researchers require raw data collected from agencies and companies for their analysis. Nevertheless, any transmission of data to third parties should satisfy some privacy requirements in order to avoid the disclosure of sensitive information. The areas of privacy preserving data mining and statistical disclosure control develop mechanisms for ensuring data privacy. Masking methods are one of such mechanisms. With them, third parties can do computations with a limited risk of disclosure....
On the complexities of selected satisfiability and equivalence queries over Boolean formulas and inclusion queries over hulls.