Search results for "Computation theory"
showing 10 items of 336 documents
Estimation of the photon production rate using imaginary momentum correlators
2023
The thermal photon emission rate is determined by the spatially transverse, in-medium spectral function of the electromagnetic current. Accessing the spectral function using Euclidean data is, however, a challenging problem due to the ill-posed nature of inverting the Laplace transform. In this contribution, we present the first results on implementing the proposal of directly computing the analytic continuation of the retarded correlator at fixed, vanishing virtuality of the photon via the calculation of the appropriate Euclidean correlator at imaginary spatial momentum. We employ two dynamical O(a)-improved Wilson fermions at a temperature of 250 MeV.
How Low Can Approximate Degree and Quantum Query Complexity Be for Total Boolean Functions?
2012
It has long been known that any Boolean function that depends on n input variables has both degree and exact quantum query complexity of Omega(log n), and that this bound is achieved for some functions. In this paper we study the case of approximate degree and bounded-error quantum query complexity. We show that for these measures the correct lower bound is Omega(log n / loglog n), and we exhibit quantum algorithms for two functions where this bound is achieved.
Worst Case Analysis of Non-local Games
2013
Non-local games are studied in quantum information because they provide a simple way for proving the difference between the classical world and the quantum world. A non-local game is a cooperative game played by 2 or more players against a referee. The players cannot communicate but may share common random bits or a common quantum state. A referee sends an input x i to the i th player who then responds by sending an answer a i to the referee. The players win if the answers a i satisfy a condition that may depend on the inputs x i .
Modular Strategies for Recursive Game Graphs
2006
AbstractMany problems in formal verification and program analysis can be formalized as computing winning strategies for two-player games on graphs. In this paper, we focus on solving games in recursive game graphs which can model the control flow in sequential programs with recursive procedure calls. While such games can be viewed as the pushdown games studied in the literature, the natural notion of winning in our framework requires the strategies to be modular with only local memory; that is, resolution of choices within a module does not depend on the context in which the module is invoked, but only on the history within the current invocation of the module. While reachability in (global…
Learning by the Process of Elimination
2002
AbstractElimination of potential hypotheses is a fundamental component of many learning processes. In order to understand the nature of elimination, herein we study the following model of learning recursive functions from examples. On any target function, the learning machine has to eliminate all, save one, possible hypotheses such that the missing one correctly describes the target function. It turns out that this type of learning by the process of elimination (elm-learning, for short) can be stronger, weaker or of the same power as usual Gold style learning.While for usual learning any r.e. class of recursive functions can be learned in all of its numberings, this is no longer true for el…
A Pragmatic Characterization of Concept Algebra
2017
Taking into account the framework of denotational mathematics as seen by Yingxu Wang, in this paper the author wishes to implement a possible further pragmatic (context-depend) dimension into the algebraic structure of concept algebra. One of the main problems of software science is that regarding context-depend question of a programming language. Indeed, attention has been paid above all to syntactic and semantic dimensions of a programming language, neglecting the pragmatic one concerning context. The author has tried to face this question providing a first denotational mathematics structure taking into account a possible pragmatic dimension.
Concurrent Computing with Shared Replicated Memory
2019
Any concurrent system can be captured by a concurrent Abstract State Machine (cASM). This remains valid, if different agents can only interact via messages. It even permits a strict separation between memory managing agents and other agents that can only access the shared memory by sending query and update requests. This paper is dedicated to an investigation of replicated data that is maintained by a memory management subsystem, where the replication neither appears in the requests nor in the corresponding answers. We specify the behaviour of a concurrent system with such memory management using concurrent communicating ASMs (ccASMs), provide several refinements addressing different replic…
A Restricted-Weakly Connected Dominating Set for Role Assignment in a Multichannel MAC for Wireless Mesh Network
2009
International audience; We propose an efficient way of constructing the wireless mesh structure associated with Molecular MAC, a multichannel access method designed for efficient packet forwarding. We base our role assignment on a restricted Weakly Connected Dominating Set structure. After presenting a formal definition of the role assignment problem, we prove its NP-completeness. Then, we propose a centralized 2-approximation algorithm that maximizes the sum of radio link capacities in the molecular structure. Finally, we extend this protocol so that it can operate in a distributed way still providing the same guarantee. This distributed protocol is self-stabilizing thus robust to topology…
The promise of spintronics for unconventional computing
2021
Novel computational paradigms may provide the blueprint to help solving the time and energy limitations that we face with our modern computers, and provide solutions to complex problems more efficiently (with reduced time, power consumption and/or less device footprint) than is currently possible with standard approaches. Spintronics offers a promising basis for the development of efficient devices and unconventional operations for at least three main reasons: (i) the low-power requirements of spin-based devices, i.e., requiring no standby power for operation and the possibility to write information with small dynamic energy dissipation, (ii) the strong nonlinearity, time nonlocality, and/o…
Object-Oriented Operational Semantics
2016
Operational semantics is one way of providing meaning to an executable language. On a high level of abstraction, operational semantics means to define an interpreter or an abstract machine for the language. In this article, we review the concept of operational semantics in the scope of meta-model-based language definitions and identify challenges and issues. We provide a clean conceptual approach using an object-oriented runtime environment and state change operations, which relies on an underlying abstract virtual machine. We present the approach using a sample language.