Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPoliteness and Stable Infiniteness: Stronger Together
64
0
0.0
(
0
)
Added by
Yoni Zohar
Publication date
2021
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
We make two contributions to the study of polite combination in satisfiability modulo theories. The first contribution is a separation between politeness and strong politeness, by presenting a polite theory that is not strongly polite. This result shows that proving strong politeness (which is often harder than proving politeness) is sometimes needed in order to use polite combination. The second contribution is an optimization to the polite combination method, obtained by borrowing from the Nelson-Oppen method. In its non-deterministic form, the Nelson-Oppen method is based on guessing arrangements over shared variables. In contrast, polite combination requires an arrangement over emph{all} variables of the shared sort (not just the shared variables). We show that when using polite combination, if the other theory is stably infinite with respect to a shared sort, only the shared variables of that sort need be considered in arrangements, as in the Nelson-Oppen method. Reasoning about arrangements of variables is exponential in the worst case, so reducing the number of variables that are considered has the potential to improve performance significantly. We show preliminary evidence for this in practice by demonstrating a speed-up on a smart contract verification benchmark.
rate research
Read More
We prove that if A is a sigma-unital exact C*-algebra of real rank zero, then every state on K_0(A) is induced by a 2-quasitrace on A. This yields a generalisation of Rainones work on pure infiniteness and stable finiteness of crossed products to the non-unital case. It also applies to k-graph algebras associated to row-finite k-graphs with no sources. We show that for any k-graph whose C*-algebra is unital and simple, either every twisted C*-algebra associated to that k-graph is stably finite, or every twisted C*-algebra associated to that k-graph is purely infinite. Finally we provide sufficient and necessary conditions for a unital simple k-graph algebra to be purely infinite in terms of the underlying k-graph.
We introduce an approach that aims to combine the usage of satisfiability modulo theories (SMT) solvers with the Combinatory Logic Synthesizer (CL)S framework. (CL)S is a tool for the automatic composition of software components from a user-specified repository. The framework yields a tree grammar that contains all composed terms that comply with a target type. Type specifications for (CL)S are based on combinatory logic with intersection types. Our approach translates the tree grammar into SMT functions, which allows the consideration of additional domain-specific constraints. We demonstrate the usefulness of our approach in several experiments.
We define a notion of stable and measurable map between cones endowed with measurability tests and show that it forms a cpo-enriched cartesian closed category. This category gives a denotational model of an extension of PCF supporting the main primitives of probabilistic functional programming, like continuous and discrete probabilistic distributions, sampling, conditioning and full recursion. We prove the soundness and adequacy of this model with respect to a call-by-name operational semantics and give some examples of its denotations.
We present two extensions of the LF Constructive Type Theory featuring monadic locks. A lock is a monadic type construct that captures the effect of an external call to an oracle. Such calls are the basic tool for gluing together diverse Type Theories and proof development environments. The oracle can be invoked either to check that a constraint holds or to provide a suitable witness. The systems are presented in the canonical style developed by the CMU School. The first system, CLLFP, is the canonical version of the system LLFP, presented earlier by the authors. The second system, CLLFP?, features the possibility of invoking the oracle to obtain a witness satisfying a given constraint. We discuss encodings of Fitch-Prawitz Set theory, call-by-value lambda-calculi, and systems of Light Linear Logic. Finally, we show how to use Fitch-Prawitz Set Theory to define a type system that types precisely the strongly normalizing terms.
We introduce filling families with matrix diagonalization as a refinement of the work by R{o}rdam and the first named author. As an application we improve a result on local pure infiniteness and show that the minimal tensor product of a strongly purely infinite $C^*$-algebra and a exact $C^*$-algebra is again strongly purely infinite. Our results also yield a sufficient criterion for the strong pure infiniteness of crossed products $Artimes_varphi mathbb{N}$ by an endomorphism $varphi$ of $A$ (cf. Theorem 7.6). Our work confirms that the special class of nuclear Cuntz-Pimsner algebras constructed by Harnisch and the first named author consist of strongly purely infinite $C^*$-algebras, and thus absorb $mathcal{O}_infty$ tensorially.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
