Search results for "Machine"
showing 10 items of 2592 documents
Shrinking language models by robust approximation
2002
We study the problem of reducing the size of a language model while preserving recognition performance (accuracy and speed). A successful approach has been to represent language models by weighted finite-state automata (WFAs). Analogues of classical automata determinization and minimization algorithms then provide a general method to produce smaller but equivalent WFAs. We extend this approach by introducing the notion of approximate determinization. We provide an algorithm that, when applied to language models for the North American Business task, achieves 25-35% size reduction compared to previous techniques, with negligible effects on recognition time and accuracy.
Algorithmic Analysis of Programs with Well Quasi-ordered Domains
2000
AbstractOver the past few years increasing research effort has been directed towards the automatic verification of infinite-state systems. This paper is concerned with identifying general mathematical structures which can serve as sufficient conditions for achieving decidability. We present decidability results for a class of systems (called well-structured systems) which consist of a finite control part operating on an infinite data domain. The results assume that the data domain is equipped with a preorder which is a well quasi-ordering, such that the transition relation is “monotonic” (a simulation) with respect to the preorder. We show that the following properties are decidable for wel…
Quantum Computers and Quantum Automata
2000
Quantum computation is a most challenging project involving research both by physicists and computer scientists. The principles of quantum computation differ from the principles of classical computation very much. When quantum computers become available, the public-key cryptography will change radically. It is no exaggeration to assert that building a quantum computer means building a universal code-breaking machine. Quantum finite automata are expected to appear much sooner. They do not generalize deterministic finite automata. Their capabilities are incomparable.
Tabu search for the dynamic Bipartite Drawing Problem
2018
Abstract Drawings of graphs have many applications and they are nowadays well-established tools in computer science in general, and optimization in particular. Project scheduling is one of the many areas in which representation of graphs constitutes an important instrument. The experience shows that the main quality desired for drawings of graphs is readability, and crossing reduction is a fundamental aesthetic criterion to achieve it. Incremental or dynamic graph drawing is an emerging topic in this context, where we seek to preserve the layout of a graph over successive drawings. In this paper, we target the edge crossing reduction in the context of incremental graph drawing. Specifically…
Building Construction Sets by Tiling Grammar Simplification
2016
This paper poses the problem of fabricating physical construction sets from example geometry: A construction set provides a small number of different types of building blocks from which the example model as well as many similar variants can be reassembled. This process is formalized by tiling grammars. Our core contribution is an approach for simplifying tiling grammars such that we obtain physically manufacturable building blocks of controllable granularity while retaining variability, i.e., the ability to construct many different, related shapes. Simplification is performed by sequences of two types of elementary operations: non-local joint edge collapses in the tile graphs reduce the gra…
Incorporating hypothetical knowledge into the process of inductive synthesis
1996
The problem of inductive inference of functions from hypothetical knowledge is investigated in this paper. This type of inductive inference could be regarded as a generalization of synthesis from examples that can be directed not only by input/output examples but also by knowledge of, e. g., functional description's syntactic structure or assumptions about the process of function evaluation. We show that synthesis of this kind is possible by efficiently enumerating the hypothesis space and illustrate it with several examples.
Geometric and conceptual knowledge representation within a generative model of visual perception
1989
A representation scheme of knowledge at both the geometric and conceptual levels is offered which extends a generative theory of visual perception. According to this theory, the perception process proceeds through different scene representations at various levels of abstraction. The geometric domain is modeled following the CSG (constructive solid geometry) approach, taking advantage of the geometric modelling scheme proposed by A. Pentland, based on superquadrics as representation primitives. Recursive Boolean combinations and deformations are considered in order to enlarge the scope of the representation scheme and to allow for the construction of real-world scenes. In the conceptual doma…
Approximate supervised learning of quantum gates via ancillary qubits
2018
We present strategies for the training of a qubit network aimed at the ancilla-assisted synthesis of multi-qubit gates based on a set of restricted resources. By assuming the availability of only time-independent single and two-qubit interactions, we introduce and describe a supervised learning strategy implemented through momentum-stochastic gradient descent with automatic differentiation methods. We demonstrate the effectiveness of the scheme by discussing the implementation of non-trivial three qubit operations, including a Quantum Fourier Transform (QFT) and a half-adder gate.
Diffusive neural network
2002
Abstract A non-connectionist model of a neuronal network based on passive diffusion of neurotransmitters is presented as an alternative to hard-wired artificial neural networks. Classic thermodynamical approach shows that the diffusive network is capable of exhibiting asymptotic stability and a dynamics resembling that of a chaotic system. Basic computational capabilities of the net are discussed based on the equivalence with a Turing machine. The model offers a way to represent mass-sustained brain functions in terms of recurrent behaviors in the phase space.
Researching Conditional Probability Problem Solving
2014
The chapter is organized into two parts. In the first one, the main protagonist is the conditional probability problem. We show a theoretical study about conditional probability problems, identifying a particular family of problems we call ternary problems of conditional probability. We define the notions of Level, Category and Type of a problem in order to classify them into sub-families and in order to study them better. We also offer a tool we call trinomial graph that functions as a generative model for this family of problems. We show the syntax of the model that allows researchers and teachers to translate a problem in terms of the trinomial graphs language, and the consequences of th…