Instant Caching for Interactive Global Illumination

The ability to interactively render dynamic scenes with global illumination is one of the main challenges in computer graphics. The improvement in performance of interactive ray tracing brought about by significant advances in hardware and careful exploitation of coherence has rendered the potential of interactive global illumination a reality. However, the simulation of complex light transport phenomena, such as diffuse interreflections, is still quite costly to compute in real time. In this paper we present a caching scheme, termed Instant Caching, based on a combination of irradiance caching and instant radiosity. By reutilising calculations from neighbouring computations this results in a speedup over previous instant radiosity‐based approaches. Additionally, temporal coherence is exploited by identifying which computations have been invalidated due to geometric transformations and updating only those paths. The exploitation of spatial and temporal coherence allows us to achieve superior frame rates for interactive global illumination within dynamic scenes, without any precomputation or quality loss when compared to previous methods; handling of lighting and material changes are also demonstrated.     

A Sound Framework for δ-Rule Variants in Free-Variable Semantic Tableaux

We propose a generic sound δ-rule, based on a quite general method for the construction of Skolem terms, which can be used as a common framework for proving the soundness of known variants of the δ-rule, and we compare their relative effectiveness. Attempts to instantiate some of the δ-rules present in the literature within our framework allowed us to pinpoint unsoundness problems for two of them. In both cases, we propose revised versions that are proved sound by reducing them within our framework. This paper is based on results preliminarily presented in [5].     

Tableaux for logic programming

We present a logic programming language, which we call Proflog, with an operational semantics based on tableaux and a denotational semantics based on supervaluations. We show the two agree. Negation is well behaved, and semantic noncomputability issues do not arise. This is accomplished essentially by dropping a domain closure requirement. The cost is that intuitions developed through the use of classical logic may need modification, though the system is still classical at a level once removed. Implementation problems are discussed very briefly; the thrust of the paper is primarily theoretical.Research partly supported by NSF Grant CCR-9104015.     

Proxy Caching for Video-on-Demand Using Flexible Starting Point Selection

In this paper, we propose a novel proxy caching scheme for video-on-demand (VoD) services. Our approach is based on the observation that streaming video users searching for some specific content or scene pay most attention to the initial delay, while a small shift of the starting point is acceptable. We present results from subjective VoD tests that relate waiting time and starting point deviation to user satisfaction. Based on this relationship as well as the dynamically changing popularity of video segments, we propose an efficient segment-based caching algorithm, which maximizes the user satisfaction by trading off between the initial delay and the deviation of starting point. Our caching scheme supports interactive video cassette recorder (VCR) functionalities and enables cache replacement with a much finer granularity compared to previously proposed segment-based approaches. Our experimental results show a significantly improved user satisfaction for our scheme compared to conventional caching schemes.      

利用状态缓存的时序等价性验证算法

为了提高时序电路的等价性验证速度,提出一种改进的基于寄存器匹配的验证算法.除了利用原像计算避免误判之外,该算法还将可达状态和不可达状态引入到验证过程中.将仿真过程中从初始状态可以到达的状态记录为可达状态,将验证过程中确认不能从初始状态到达的状态记录为不可达状态,利用它们减少验证过程中的原像计算.基于mcnc91电路的实验数据表明,该算法有效地减少了验证时间.     

Using Tableaux to Automate the Lambek and Other Categorial Calculi

We argue that, although labeled deduction can be quite costly in general, the complexity of keeping track of the label constraints built to encode the structure of the proofs does not necessarily render the strategy impractical. The point is illustrated with LLKE, a tableaux system for specification and test of categorial grammars. The paper presents and discusses the application of theorem proving in labeled analytic tableaux to natural language processing (NLP), describes algorithms and rules for tableau generation, introduces a new label-checking strategy, and identifies places where the complexity of the task can be tamed.     

Analysis of Authentication Protocols in Agent-Based Systems Using Labeled Tableaux

The study of multiagent systems (MASs) focuses on systems in which many intelligent agents interact with each other using communication protocols. For example, an authentication protocol is used to verify and authorize agents acting on behalf of users to protect restricted data and information. After authentication, two agents should be entitled to believe that they are communicating with each other and not with intruders. For specifying and reasoning about the security properties of authentication protocols, many researchers have proposed the use of belief logics. Since authentication protocols are designed to operate in dynamic environments, it is important to model the evolution of authentication systems through time in a systematic way. We advocate the systematic combinations of logics of beliefs and time for modeling and reasoning about evolving agent beliefs in MASs. In particular, we use a temporal belief logic called TML$^{+}$ for establishing trust theories for authentication systems and also propose a labeled tableau system for this logic. To illustrate the capabilities of TML$^{+}$, we present trust theories for several well-known authentication protocols, namely, the Lowe modified wide-mouthed frog protocol, the amended Needham–Schroeder symmetric key protocol, and Kerberos. We also show how to verify certain security properties of those protocols. With the logic TML$^{+}$ and its associated modal tableaux, we are able to reason about and verify authentication systems operating in dynamic environments.      

A Statistical Admission Control Scheme for Continuous Media Servers Using Caching

In continuous media servers, disk load can be reduced by using buffer cache. In order to utilize the saved disk bandwidth by caching, a continuous media server must employ an admission control scheme to decide whether a new client can be admitted for service without violating the requirements of clients already being serviced. A scheme providing deterministic QoS guarantees in servers using caching has already been proposed. Since, however, deterministic admission control is based on the worst case assumption, it causes the wastage of the system resources. If we can exactly predict the future available disk bandwidth, both high disk utilization and hiccup-free service are achievable. However, as the caching effect is not analytically determined, it is difficult to predict the disk load without substantial computation overhead. In this paper, we propose a statistical admission control scheme for continuous media servers where caching is used to reduce disk load. This scheme improves disk utilization and allows more streams to be serviced while maintaining near-deterministic service. The scheme, called Shortsighted Prediction Admission Control (SPAC), combines exact prediction through on-line simulation and statistical estimation using a probabilistic model of future disk load in order to reduce computation overhead. It thereby exploits the variation in disk load induced by VBR-encoded objects and the decrease in client load by caching. Through trace-driven simulations, it is demonstrated that the scheme provides near-deterministic QoS and keeps disk utilization high.     

Integrating Web Prefetching and Caching Using Prediction Models

Web caching and prefetching have been studied in the past separately. In this paper, we present an integrated architecture for Web object caching and prefetching. Our goal is to design a prefetching system that can work with an existing Web caching system in a seamless manner. In this integrated architecture, a certain amount of caching space is reserved for prefetching. To empower the prefetching engine, a Web-object prediction model is built by mining the frequent paths from past Web log data. We show that the integrated architecture improves the performance over Web caching alone, and present our analysis on the tradeoff between the reduced latency and the potential increase in network load.     

Superposition-based Equality Handling for Analytic Tableaux

We present a variant of the basic ordered superposition rules to handle equality in an analytic free-variable tableau calculus. We prove completeness of this calculus by an adaptation of the model generation technique commonly used for completeness proofs of superposition in the context of resolution calculi. The calculi and the completeness proof are compared to earlier results of Degtyarev and Voronkov. Some variations and refinements are discussed.     

Single Step Tableaux for Modal Logics

Single Step Tableaux (SST) are the basis of a calculus for modal logics that combines different features of sequent and prefixed tableaux into a simple, modular, strongly analytic, and effective calculus for a wide range of modal logics.The paper presents a number of the computational results about SST (confluence, decidability, space complexity, modularity, etc.) and compares SST with other formalisms such as translation methods, modal resolution, and Gentzen-type tableaux. For instance, it discusses the feasibility and infeasibility of deriving decision procedures for SST and translation-based methods by replacing loop checking techniques with simpler termination checks.The complexity of searching for validity and logical consequence with SST and other methods is discussed. Minimal conditions on SST search strategies are proven to yield Pspace (and NPtime for S5 and KD45) decision procedures. The paper also presents the methodology underlying the construction of the correctness and completeness proofs.     

Caching for Web Searching

Abstract. We study Web Caching when the input sequence is a depth first search traversal of some tree. There are at least two good motivations for investigating tree traversal as a search technique on the WWW: First, empirical studies of people browsing and searching the WWW have shown that user access patterns commonly are nearly depth first traversals of some tree. Secondly (as we will show in this paper), the problem of visiting all the pages on some WWW site using anchor clicks (clicks on links) and back button clicks—by far the two most common user actions—reduces to the problem of how best to cache a tree traversal sequence (up to constant factors). We show that for tree traversal sequences the optimal offline strategy can be computed efficiently. In the bit model, where the access time of a page is proportional to its size, we show that the online algorithm LRU is (1 + 1/ɛ) -competitive against an adversary with unbounded cache as long as LRU has a cache of size at least (1+ ɛ) times the size of the largest item in the input sequence. In the general model, where pages have arbitrary access times and sizes, we show that in order to be constant competitive, any online algorithm needs a cache large enough to store Ω(log n) pages; here n is the number of distinct pages in the input sequence. We provide a matching upper bound by showing that the online algorithm Landlord is constant competitive against an adversary with an unbounded cache if Landlord has a cache large enough to store the Ω(log n) largest pages. This is further theoretical evidence that Landlord is the ``right' algorithm for Web Caching.     

Analytic Tableaux for Higher-Order Logic with Choice

While many higher-order interactive theorem provers include a choice operator, higher-order automated theorem provers so far have not. In order to support automated reasoning in the presence of a choice operator, we present a cut-free ground tableau calculus for Church’s simple type theory with choice. The tableau calculus is designed with automated search in mind. In particular, the rules only operate on the top level structure of formulas. Additionally, we restrict the instantiation terms for quantifiers to a universe that depends on the current branch. At base types the universe of instantiations is finite. Both of these restrictions are intended to minimize the number of rules a corresponding search procedure is obligated to consider. We prove completeness of the tableau calculus relative to Henkin models.     

运用声卡的虚拟信号发生器设计

以数据分析和处理功能强大的工程实用软件LahView作为软件开发平台,采用计算机声卡代替普通采集卡作为硬件,设计了一个操作简单实用、灵活性好的信号发生器系统,实现了基本信号(如正弦波、三角波、锯齿波、方波)和公式信号的产生功能.系统性价比高、通用性强、扩展性好、界面友好,在工程测量与实验室应用中具有广阔的前景.     

Interactive Transmission of JPEG2000 Images Using Web Proxy Caching

This paper describes and analyzes JPIP-W, an innovative proposal for the interactive transmission of JPEG2000 images on the Internet. JPIP-W is an extension of JPIP, the current JPEG protocol proposed for interactive JPEG2000 image browsing. One of the JPIP characteristics of greatest interest is its ability to use the Web for retrieving images. However, JPIP is unable to exploit the large infrastructure of today's Web caching systems (proxies), used to reduce response time and network traffic. To overcome this drawback, JPIP-W defines a new server-client interaction consisting of splitting JPEG2000 images into data blocks that can be cached by the proxies. These blocks can be shared among several clients, allowing fast recovery of some portions of the images. Experimental results demonstrate that JPIP-W significantly reduces JPIP retrieving times.     

Evolutionary Techniques for Web Caching

Web caching has been proposed as an effective solution to the problems of network traffic and congestion, Web objects access and Web load balancing. This paper presents a model for optimizing Web cache content by applying either a genetic algorithm or an evolutionary programming scheme for Web cache content replacement. Three policies are proposed for each of the genetic algorithm and the evolutionary programming techniques, in relation to objects staleness factors and retrieval rates. A simulation model is developed and long term trace-driven simulation is used to experiment on the proposed techniques. The results indicate that all evolutionary techniques are beneficial to the cache replacement, compared to the conventional replacement applied in most Web cache server. Under an appropriate objective function the genetic algorithm has been proven to be the best of all approaches with respect to cache hit and byte hit ratios.     

Dual Systems of Tableaux and Sequents for PLTL

On one hand, traditional tableau systems for temporal logic (TL) generate an auxiliary graph that must be checked and (possibly) pruned in a second phase of the refutation procedure. On the other hand, traditional sequent calculi for TL make use of a kind of inference rules (mainly, invariant-based rules or infinitary rules) that complicates their automatization. A remarkable consequence of using auxiliary graphs in the tableaux framework and invariants or infinitary rules in the sequents framework is that TL fails to carry out the classical correspondence between tableaux and sequents. In this paper, we first provide a tableau method TTM that does not require auxiliary graphs to decide whether a set of PLTL-formulas is satisfiable. This tableau method TTM is directly associated to a one-sided sequent calculus called TTC. Since TTM is free from all the structural rules that hinder the mechanization of deduction, e.g. weakening and contraction, then the resulting sequent calculus TTC is also free from this kind of structural rules. In particular, TTC is free of any kind of cut, including invariant-based cut. From the deduction system TTC, we obtain a two-sided sequent calculus GTC that preserves all these good freeness properties and is finitary, sound and complete for PTL. Therefore, we show that the classical correspondence between tableaux and sequent calculi can be extended to TL. Every deduction system is proved to be complete. In addition, we provide illustrative examples of deductions in the different systems.