Conquering Uncertainty in Multiple-Valued Logic Design

In modern science, significant advances are typically made atcross-roads of disciplines. Thus, many optimization problems inMultiple-valued Logic Design have been successfullyapproached using ideas and techniques from ArtificialIntelligence. In particular, improvements in multiple-valuedlogic design have been made by exploiting information/uncertaintymeasures. In this paper, we review well-known information measuresin the multiple-valued domain and consider some methods of findinginformation measures for completely or incompletely specifiedfunctions with multiple-valued and continuous attributes. In thisrespect, the paper addresses the problem known as discretizationand introduces a method of finding an optimal representation ofcontinuous data in the multiple-valued domain. We also propose atechnique for efficient calculation of different informationmeasures using Multiple-valued Decision Diagrams. As oneapplication of our technique, we outline an approach tosynthesizing digital circuits derived from decision diagrams thatcan yield to reduction in power dissipation. The paper also showsthe impact in several important areas of multiple-valued systemdesign including (i) fuzzy logic, (ii) quantum computing systems,and (iii) data mining.     

Criteria to disprove context freeness of collage languages

Collage grammars are context-free devices which generate picture languages consisting of collages—sets of parts, where a part is a set of points in a given space. In order to show that certain collage languages cannot be generated, the well-known pumping technique turns out to be rather useless. To circumvent this difficulty, other necessary criteria for context-freeness are established in this paper. Roughly speaking, these criteria reveal that (1) the collages in a context-free collage language can be deflated stepwise in such a manner that the difference between subsequent collages in the resulting chain is small and (2) the volume of parts can grow or shrink only exponentially.     

Finite semigroup varieties defined by programs

We study the regular languages recognized by polynomial-length programs over finite semigroups belonging to product varieties V * LI, where V is a variety of finite monoids, and LI is the variety of finite locally trivial semigroups. In the case where the semigroup variety has a particular closure property with respect to programs, we are able to give precise characterizations of these regular languages. As a corollary we obtain new proofs of the results of Barrington, Compton, Straubing and Therien characterizing the regular languages in certain circuit complexity classes.     

Multi-objective shape optimization of a hydraulic turbine runner using efficiency,strength and weight criteria

An approach for multi-discipline automatic optimization of the hydraulic turbine runner shape is presented. The approach accounts hydraulic efficiency, mechanical strength and the weight of the runner. In order to effectively control the strength and weight of the runner, a new parameterization of the blade thickness function is suggested. Turbine efficiency is evaluated through numerical solution of Reynolds-averaged Navier-Stokes equations, while the finite element method is used to evaluate the von Mises stress in the runner. An objective function, being the weighted sum of maximal stress and the blade volume, is suggested to account for both the strength and weight of the runner. Multi-objective genetic algorithm is used to solve the optimization problem. The suggested approach has been applied to automatic design of a Francis turbine runner. Series of three-objective optimization runs have been carried out. The obtained results clearly indicate that simultaneous account of stress and weight objectives accompanied by thickness variation allows obtaining high efficiency, light and durable turbine runners.     

Large scale multiple sequence alignment with simultaneous phylogeny inference

Multiple sequence alignment (MSA) and phylogenetic tree reconstruction are one of the most important problems in the computational biology. While both these problems are of great practical significance, in most cases they are very computationally demanding. In this paper we propose a new approach to the MSA problem which simultaneously infers an underlying phylogenetic tree. To process large data sets we provide parallel implementation of our method, which is based on the distributed caching of intermediate results. Finally, we show a parallel server designed for grid environments, and we report results of experiments performed with actual biological data, e.g. 1000 ribosomal RNA sequences.     

Robust interactive cutting based on an adaptive octree simulation mesh

We present an adaptive octree based approach for interactive cutting of deformable objects. Our technique relies on efficient refine- and node split-operations. These are sufficient to robustly represent cuts in the mechanical simulation mesh. A high-resolution surface embedded into the octree is employed to represent a cut visually. Model modification is performed in the rest state of the object, which is accomplished by back-transformation of the blade geometry. This results in an improved robustness of our approach. Further, an efficient update of the correspondences between simulation elements and surface vertices is proposed. The robustness and efficiency of our approach is underlined in test examples as well as by integrating it into a prototype surgical simulator.     

Analyse des problemes de geometrie et apprentissage de la preuve au secondaire

Résumé

Le présent article rend compte de l'élaboration d'une grille d'analyse des problèmes de géométrie, et de sa mise à l'épreuve par la classification des problèmes et exercices de géométrie synthétique dans une collection de manuels du secondaire parmi les plus utilisées au Québec. Le cadre conceptuel sur lequel s'appuie cette élaboration s'inspire principalement des travaux de Balacheff (1987), Barbin (1988), Brousseau (1998), Hanna (1995) et Rouche (1989), et débouche sur une typologie des preuves de géométrie. La classification des problèmes à partir de cette grille et l'analyse qui en découle nous a permis de conclure sur les aspects de l'apprentissage de la preuve que nous évaluons comme mal ? gérés ? dans la collection : transition non suffisamment graduelle du sensible au formel (peu de problèmes qui sollicitent une validation hybride, niveau de formalisation trop longtemps stationnaire), prépondérance des applications directes et des déductions locales sur les séquences déductives, intérêt et mode de présentation des résultats qui ne favorisent pas une ? attitude de preuve ?.     

State space representation of routing flexibility

This paper describes a state space representation for sequencing and routing flexibility in manufacturing systems. Routing flexibility is represented using five different stages as follows: (i) Precedence Graph of Operations; (ii) State Transition Graph of Manufacturing Operation Sequences; (iii) State Transition Graph of Manufacturing Operation Routes; (iv) Disjunctive Normal Form (DNF) Representation of Manufacturing Sequences; and (v) DNF Representation of Manufacturing Routes. Each representation is able to represent sequencing and routing flexibility at different levels of detail. The third representation is capable of enumerating all possible manufacturing operation routes that can be applied to a certain part, being the most complete representation. Bounds for computation of some of the representations are presented to help users select the most suitable for a specific problem context. The efficacy of the representation is demonstrated through its application to problems such as job route selection and routing flexibility measure.     

Complete Classifications for the Communication Complexity of Regular Languages

We show that every regular language L has either constant, logarithmic or linear two-party communication complexity (in a worst-case partition sense). We prove similar classifications for the communication complexity of regular languages for the simultaneous, probabilistic, simultaneous probabilistic and Mod_p-counting models of communication.     

Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables

Abstract. We consider generalized first-order sentences over < using both ordinary and modular quantifiers. It is known that the languages definable by such sentences are exactly the regular languages whose syntactic monoids contain only solvable groups. We show that any sentence in this logic is equivalent to one using three variables only, and we prove that the languages expressible with two variables are those whose syntactic monoids belong to a particular pseudovariety of finite monoids, namely the wreath product of the pseudovariety DA (which corresponds to the languages definable by ordinary first-order two-variable sentences) with the pseudovariety of finite solvable groups. This generalizes earlier work of Thérien and Wilke on the expressive power of two-variable formulas in which only ordinary quantifiers are present. If all modular quantifiers in the sentence are of the same prime modulus, this provides an algorithm to decide if a regular language has such a two-variable definition.