Search

We solve an open problem by constructing quantum walks that not only detect but also find marked vertices in a graph. The number of steps of the quantum walk is quadratically smaller than the classical hitting time of any reversible random walk P on the graph. Our approach is new, simpler and more general than previous ones. We introduce a notion of interpolation between the walk P and the absorbing walk P', whose marked states are absorbing. Then our quantum walk is simply the quantum analogue of the interpolation. Contrary to previous approaches, our results remain valid when the random walk P is not state-transitive, and in the presence of multiple marked vertices. As a consequence we make a progress on an open problem related to the spatial search on the 2D-grid. [ABSTRACT FROM AUTHOR]

To introduce a temporal dimension to a belief logic, we consider a powerful technique called fibring for combining belief logics and temporal logics. In a fibred belief logic, both temporal operators and belief operators are treated equally. This paper in particular discusses a combination of a belief logic called Typed-Modal Logic with a linear-time temporal logic. We show that, in the resulting logic, we can specify and reason about not only agent beliefs but also the timing properties of a system. With this logical system one is able to build theories of trust for the description of, and reasoning about, multi-agent systems. [ABSTRACT FROM AUTHOR]

Trust is essential to a communication channel. The trust relationships, which play an important role in Public Key Infrastructures (PKIs), need to be formalized for providing a reliable modelling methodology to support secure digital communications. In this paper, we present a typed modal logic used for specifying and reasoning about trust in PKIs. In order to study trust relationships within PKIs, we define TA (a set of trust axioms), TB (a trust base) and TC (a set of trusted certificates). In our method, the trust relation in a given PKI is formalized by trust axioms. Based on trust axioms, an agent can have its own trust base that contains all agents whom the agent trusts, and can derive and extend its trusted certificates set. The trust theory for a given PKI, which consists of our modal logic and a set of trust axioms proposed for the PKI, is the basis of the certificate verification function. [ABSTRACT FROM AUTHOR]

In this article we look at some of the problems associated with trying to provide a specification for a Public Key Infrastructure (PKI). We focus on the PKI profile that has been proposed for use with the Internet, known as PKIX (PKI using X.509 certificates), to provide a specific example. Our intention is to add value to this and other specifications by providing a more formal description and a framework in which to develop path validation procedures. We take the path validation algorithm in PKIX and give a formal description of the actions and properties it defines. In this way, the essential aspects can be captured and clearly formulated, which would facilitate the testing of implementations in a more rigorous and well defined way. [ABSTRACT FROM AUTHOR]