Search results for "abstract"
showing 10 items of 1959 documents
Exact affine counter automata
2017
We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k-counter automata. We also show that a certain promise problem, which is conjectured not to be solved by two-way quantum finite automata in polynomial time, can be solved by Las Vegas affine finite automata. Lastly, we show that how a counter helps for affine finite automata by showing that the language MANYTWINS, which is conjectured not to be recognized by affin…
Finite automata with advice tapes
2013
We define a model of advised computation by finite automata where the advice is provided on a separate tape. We consider several variants of the model where the advice is deterministic or randomized, the input tape head is allowed real-time, one-way, or two-way access, and the automaton is classical or quantum. We prove several separation results among these variants, demonstrate an infinite hierarchy of language classes recognized by automata with increasing advice lengths, and establish the relationships between this and the previously studied ways of providing advice to finite automata.
Time and space efficient quantum algorithms for detecting cycles and testing bipartiteness
2016
We study space and time efficient quantum algorithms for two graph problems -- deciding whether an $n$-vertex graph is a forest, and whether it is bipartite. Via a reduction to the s-t connectivity problem, we describe quantum algorithms for deciding both properties in $\tilde{O}(n^{3/2})$ time and using $O(\log n)$ classical and quantum bits of storage in the adjacency matrix model. We then present quantum algorithms for deciding the two properties in the adjacency array model, which run in time $\tilde{O}(n\sqrt{d_m})$ and also require $O(\log n)$ space, where $d_m$ is the maximum degree of any vertex in the input graph.
Measuring Semantic Coherence of a Conversation
2018
Conversational systems have become increasingly popular as a way for humans to interact with computers. To be able to provide intelligent responses, conversational systems must correctly model the structure and semantics of a conversation. We introduce the task of measuring semantic (in)coherence in a conversation with respect to background knowledge, which relies on the identification of semantic relations between concepts introduced during a conversation. We propose and evaluate graph-based and machine learning-based approaches for measuring semantic coherence using knowledge graphs, their vector space embeddings and word embedding models, as sources of background knowledge. We demonstrat…
Determinantal sets, singularities and application to optimal control in medical imagery
2016
International audience; Control theory has recently been involved in the field of nuclear magnetic resonance imagery. The goal is to control the magnetic field optimally in order to improve the contrast between two biological matters on the pictures. Geometric optimal control leads us here to analyze mero-morphic vector fields depending upon physical parameters , and having their singularities defined by a deter-minantal variety. The involved matrix has polynomial entries with respect to both the state variables and the parameters. Taking into account the physical constraints of the problem, one needs to classify, with respect to the parameters, the number of real singularities lying in som…
General framework for testing Poisson-Voronoi assumption for real microstructures
2020
Modeling microstructures is an interesting problem not just in Materials Science but also in Mathematics and Statistics. The most basic model for steel microstructure is the Poisson-Voronoi diagram. It has mathematically attractive properties and it has been used in the approximation of single phase steel microstructures. The aim of this paper is to develop methods that can be used to test whether a real steel microstructure can be approximated by such a model. Therefore, a general framework for testing the Poisson-Voronoi assumption based on images of 2D sections of real metals is set out. Following two different approaches, according to the use or not of periodic boundary conditions, thre…
Acoustic Su-Schrieffer-Heeger lattice: Direct mapping of acoustic waveguides to the Su-Schrieffer-Heeger model
2021
Topological physics strongly relies on prototypical lattice model with particular symmetries. We report here on a theoretical and experimental work on acoustic waveguides that is directly mapped to the one-dimensional Su-Schrieffer-Heeger chiral model. Starting from the continuous two dimensional wave equation we use a combination of monomadal approximation and the condition of equal length tube segments to arrive at the wanted discrete equations. It is shown that open or closed boundary conditions topological leads automatically to the existence of edge modes. We illustrate by graphical construction how the edge modes appear naturally owing to a quarter-wavelength condition and the conserv…
Quotients of Fermat curves and a Hecke character
2005
AbstractWe explicitly identify infinitely many curves which are quotients of Fermat curves. We show that some of these have simple Jacobians with complex multiplication by a non-cyclotomic field. For a particular case we determine the local zeta functions with two independent methods. The first uses Jacobi sums and the second applies the general theory of complex multiplication, we verify that both methods give the same result.
On Pareto optima, the Fermat-Weber problem, and polyhedral gauges
1990
This paper deals with multiobjective programming in which the objective functions are nonsymmetric distances (derived from different gauges) to the points of a fixed finite subset of ℝn. It emphasizes the case in which the gauges are polyhedral. In this framework the following result is known: if the gauges are polyhedral, then each Pareto optimum is the solution to a Fermat—Weber problem with strictly positive coefficients. We give a new proof of this result, and we show that it is useful in finding the whole set of efficient points of a location problem with polyhedral gauges. Also, we characterize polyhedral gauges in terms of a property of their subdifferential.
Minimal change list for Lucas strings and some graph theoretic consequences
2005
AbstractWe give a minimal change list for the set of order p length-n Lucas strings, i.e., the set of length-n binary strings with no p consecutive 1's nor a 1ℓ prefix and a 1m suffix with ℓ+m⩾p. The construction of this list proves also that the order p n-dimensional Lucas cube has a Hamiltonian path if and only if n is not a multiple of p+1, and its second power always has a Hamiltonian path.