Academic literature on the topic 'Z3 SMT solver'

Satisfiability modulo theories (SMT) is an area concerned with checking the satisfiability of logical formulas over one or more theories. SMT can be well tuned to solve several of the most intriguing problems in electronic design automation (EDA). Analog placers use physical constraints to automatically generate small sections of layout. The work presented in this paper shows that SMT solvers can be used for the automation of analog placement, given some physical constraints. We propose a tool that uses Microsoft Z3 SMT solver to find valid placement solutions for the given analog blocks. Accordingly, it generates multiple layouts that fulfill some given constraints and provides a variety of alternative layouts. The user has the option to choose one of the feasible solutions. The proposed system uses the quantifier-free linear real arithmetic (QFLRA), which makes the problem decidable. The proposed system is able to generate valid placement solutions for benchmarks. For benchmarks that have many constraints and few geometries, the proposed system achieves a speedup that is 10 times faster than other recently used approaches.

This paper proposes a new hybrid encoding of finite linear CSP to SAT which integrates order and log encodings. The former maintains bound consistency by unit propagation and works well for constraints consisting of small/middle sized arity and variable domains. The latter generates smaller CNF and works well for constraints consisting of larger sized arity and variable domains but its performance is not good in general because more inference steps are required to ripple carries. This paper describes the first attempt of hybridizing the order and log encodings without channeling constraints. Each variable is encoded by either the order encoding or the log encoding, and each constraint can contain both types of variables. Using the CSP solver competition benchmark consisting of 1458 instances, we made a comparison between the order, log and proposed hybrid encodings. As a result, the hybrid encoding solves the largest number of instances with the shortest CPU time. We also made a comparison with the four state-of-the-art CSP and SMT solvers Mistral, Opturion CPX, Yices, and z3. In this comparison, the hybrid encoding also shows the best performance. Furthermore, we found that the hybrid encoding is especially superior than other solvers for instances containing disjunctive constraints and global constraints — it indeed solves more instances than the virtual best solver consisting of those four state-of-the-art systems.

Software testing is an important problem in designing a large software system and this problem is difficult to be solved due to its computational complexity. We try to use program nets to approach this problem and have proposed algorithms to divide a whole program net into subnets that can structurally cover the original one based on divide-and-conquer method. This paper aims to solve the remaining task of our approach, that is how to find test input data for each subnet to be called choiceless program net. Firstly, definitions of program nets are extended and the properties of choiceless program nets are analysed. Secondly, polynomial algorithms are proposed to get all constraint conditions of any given choiceless program nets. Finally, a method to generate test input data under the obtained constraint conditions is proposed by adopting an SMT (Satisfiability Modulo Theories) solver, $Z3$ prover, and also an example is given to show the usefulness of our method.

Purpose Business process (BP) reengineering is defined as reinventing BPs either structurally or technically to achieve dramatic improvements in performance. In any business process reengineering (BPR) project, process modeling is used to reason about problems found in existing (as-is) process and helps to design target (to-be) process. BP model notation is a widely accepted standard for process modeling. “Expressiveness” and “missing formal semantics” are two problems reported to its modeling practices. In existing studies, solutions to these problems are also proposed but still have certain limitations. The paper aims to discuss this issue. Design/methodology/approach In proposed methodology, a meta-model is formally defined that is composed of commonly used modeling elements and their well-formedness rules to check for syntactic and structural correctness of process models. Proposed solution also check semantics of process models and allows to compare as-is and to-be process models for gap identification which is another important aspect of BPR. To achieve the first goal, Z specification is used to provide formal specifications of modeling constructs and their rules and Z3 (an SMT solver) is used for comparisons and verifying properties. Findings Proposed method addresses both “expressiveness” and “missing formal semantics” of BPR models. The results of its evaluation clearly indicate that using formally specified meta-model, BPR model is syntactically and structurally correct. Moreover, formal modeling of BPs in Z3 helped to compare processes and to check control flow properties. Research limitations/implications Although the proposed method is tested on an example that is widely used in BPR literature, the example is only covering modeling elements which are part of the proposed subset and are reported in literature as frequently used modeling elements. A separate detailed study is required to test it on more complex systems. Practical implications Specifying process models using Z specification and Z3 solver requires certain expertise. Originality/value The proposed method adds value to BPR body of knowledge as it proposes a method to ensure structural and syntactic correctness of models, highlighting the importance of verifying run time properties and providing a direction toward comparing process models for gap analysis.

Interactive configuration includes the user as an essential factor in the configuration process. The two main components of an interactive configurator are a user interface at the front-end and a knowledge representation and reasoning (KRR) framework at the back-end. In this paper we discuss important requirements for the underlying KRR system to support an interactive configuration process. Representative of many reasoning systems and tools used for implementing product configurators, we selected MiniZinc, Choco, Potassco, Picat, CP-SAT solver, and Z3 for evaluation and reviewed them against the identified requirements. We observe that many of those requirements are not well supported by existing stand-alone solvers.

In this paper, we develop machinery to solve ternary Diophantine equations of the shape Ax n + By n = C z3 for various choices of coefficients (A, B, C). As a byproduct of this, we show, if p is prime, that the equation x n + y n = pz3 has no solutions in coprime integers x and y with |xy| > 1 and prime n > p4p2. The techniques employed enable us to classify all elliptic curves over $\mathbb{Q}$ with a rational 3-torsion point and good reduction outside the set {3, p}, for a fixed prime p.

The program transformation methods to simplify the deductive verification of programs with recursive data types are investigated. The list reversion program is considered as an example. A source program in the C language is translated to the cP functional language which includes no pointers. The resulting program is translated further to the WhyML language to perform deductive verification of the program. The cP language includes the same constructs of the C language except pointers. In the C program, all actions that include pointers are replaced by the equivalent fragments without pointers. These replacement are performed by the special transformations using the results of the program dataflow analysis. Three variants of deductive verification of the transformed list reverse program in the Why3 verification platform with SMT solvers (Z3 4.8.6, CVC3 2.4.1, CVC4 1.7) are performed. First, the recursive WhyML program supplied with specifications was automatically verified successfully using only SMT solvers. Second, the recursive program was translated to the P predicate language. Correctness formulae were constructed for the P program and translated further to the why3 specification language. The formulae proving correctness were easy like the first variant. But correctness formulae for the first and second variants were different. Third, the "imperative" WhyML program that included while loop with additional invariant specifications was verified. The proving was easy but not automatic. So, for deductive verification, recursive program variant appears to be more preferable against imperative program variant.

We present a visual and interactive taxonomic Artificial Intelligence (AI) tool, the Automated Taxonomic Concept Reasoner (ATCR), whose graphical web interface is under development and will also become available via an Application Programming Interface (API). The tool employs automated reasoning (Beeson 2014) to align multiple taxonomies visually, in a web browser, using user or expert-provided taxonomic articulations, i.e. "Region Connection Calculus (RCC-5) relationships between taxonomic concepts, provided in a specific logical language (Fig. 1). It does this by representing the problem of taxonomic alignment under these constraints in terms of logical inference, while performing these inferences computationally and leveraging the powerful Microsoft Z3 Satisfiability Modulo Theory (SMT) solver (de Moura and Bjørner 2008). This tool represents further development of utilities for the taxonomic concept approach, which fundamentally addresses the challenge of robust biodiversity data aggregation in light of multiple conflicting sources (and source classifications) from which primary biodiversity data almost invariably originate. The approach has proven superior to aggregation, based just on the syntax and semantics provided by the Darwin Core standard Franz and Sterner 2018). Fig. 1 provides an artificial example of such an alignment. Two taxonomies, A and B, are shown. There are five taxonomic concepts, A.One, A.Two, A.Three, B.One and B.Two. A.Two and A.Three are sub-concepts (children) of A.One, and B.Two is a sub-concept (child) of B.One. These are represented by the direction of the grey arrows. The undirected mustard-coloured lines represent relationships, i.e., the articulations referred to in the previous paragraph. These may be of five kinds: congruent (==), includes (<) and included in (>), overlap (><), and disjointness. These five relationships are known in the AI literature as the Region Connection Calculus-5 (RCC-5) (Randell et al. 1992, Bennett 1994, Bennett 1994), and taken exclusively and in conjunction with each other, have certain desirable properties with respect to the representation of spatial relationships. The provided relationship (i.e. the articulation) may also be an arbitrary disjunction of these five fundamental kinds, thus allowing for representation of some degree of logical uncertainty. Then, and under three assumptions that: "sibling" concepts are disjoint in their instances, all instances of a parent concept are instances of at least one of its child concepts, and every concept has at least one instance - the SMT-based automated reasoner is able to deduce the relationships represented by the undirected green lines. It is also able to deduce disjunctive relationships where these are logically implied. "sibling" concepts are disjoint in their instances, all instances of a parent concept are instances of at least one of its child concepts, and every concept has at least one instance - the SMT-based automated reasoner is able to deduce the relationships represented by the undirected green lines. It is also able to deduce disjunctive relationships where these are logically implied. ATCR is related to Euler/X (Franz et al. 2015), an existing tool for the same kinds of taxonomic alignment problems, which was used, for example, to obtain an alignment of two influential primate classifications (Franz et al. 2016). It differs from Euler/X in that it employs a different logical encoding that enables more efficient and more informative computational reasoning, and also in that it provides a graphical web interface, which Euler/X does not.

In Mardi and a Voyage Thither, novelist Herman Melville writes of the peculiar and startling confluence of memory, objects, valuation, and disfigurement that mark the collector of obsoletia. The story’s antiquary is the picture of perverse depletion, with a body “crooked, and dwarfed, and surmounted by a hump, that sat on his back like a burden” (328), his hut in shambles, and “the precious antiques, and curios, and obsoletes”—the objects of his collection—“strewn about, all dusty and disordered” (329). This unkempt display cum impromptu museum turns out to present a mere fraction of the curator’s collection, the rest of which is host to countless subtle molds and ravenous worms in a vast catacomb below ground. Traversing this darkened vault, one visitor says, is “like going down to posterity” (332). As inveterate accumulators ourselves, we can certainly relate to Mardi’s "extraordinary antiquarian": pursuing obsolete things has transformed us too (though hopefully not quite so hideously), as well as the work we do and the spaces we do it in. Since 1999, we have been collecting—and subsequently lending out to scholars the world over—computer games, systems, and game-related paraphernalia. By recent estimates, our Learning Games Initiative Archive contains more than 20,000 artifacts, from Venezuelan Pong clones to Mario-themed lollipops. Archival work at this scale and with this diversity is not easy, and it constantly butts up against a host of intractable questions. For example, what does it mean to isolate a thing that no longer has its original value but has taken on a new one? When researchers hold such transmuted artifacts up for inspection, what are they looking for and how might archivists help them to find it? Is the primary work of computer game archivists (and indeed archivists of all types) to protect artifacts from the elements, to enjoin them upon their kin, and to guard over the collection for the sake of some abstract posterity, or is it something more collaborative and communal? Finally, is it possible for research-oriented collectors to engage the process of collection without suffering the deformations of skin and soul (not to mention pocketbook) that often plague the more solipsistic acquirer? We offer this article as an entrée to these questions, as a way to begin to attend to some of the theoretical and practical complexities of obsolescence and its negotiation. We do so primarily by focusing on where those complexities intersect with computer games, the new media we collect and study. Circuitous Obsolescence Melville finished Mardi in 1849, almost fifty years after Joseph Marie Jacquard invented the programmable loom and twelve years after Charles Babbage theorised the possibility of a programmable mechanical computer. The subsequent history of the development of the modern computer and its applications (including computer games) typically gets told as a narrative of technological novelty followed by ineluctable obsolescence—Herman Hollerith’s tabulator to Konrad Zuse’s Z3 to the US Army’s Electronic Numerical Integrator and Computer (ENIAC) and so on. This kind of monumentalised and narrativised history exemplifies an onward march much fetishised by the marketplace: once introduced, a given technology will be developed then updated, upgraded, and improved, inevitably producing a staggering wake of tired-and-true archaeological assemblages. These cast-offs, however, are only useless to those who prefer to consume at the cutting edge, and even that is an illusory experience. Like a well-designed knife whose business end is supported by the stout spine behind it, the edgiest of today’s computer games and peripherals—from the most non-directive sandbox titles to the most obscene add-ons—are merely vanguards to a half-century of industrial history. In etymological terms, “obsolete” captures the conundrum well. A combination of ob (away) and solere (to be used to, accustomed), the word “obsolete” has at least four distinct meanings: “no longer used or practiced”; “worn away, dilapidated, atrophied”; “indistinct, hardly perceptible, vestigial”; and as a noun, “A thing which is out of date or has fallen into disuse.” In each usage, present and past are both integral and palpable. As archivists, we appreciate this temporal distillation because it illustrates how seamless yet discernable is the paradoxical binding between old and new. “Obsolescence” thus functions like a rhetorical ouroboros, ensuring that reflection on the antique reveals the avant-garde and vice-versa. Consider, for example, the Atari 2600 paddle. Compared to a PlayStation 3 controller, with its variety of buttons, sticks, and pads—and the re-mapability of all these input elements—the single potentiometer and button of the paddle seem downright antiquated. Moreover, because Atari hardware in general has largely faded from mainstream use (though it has a remarkable half-life in collectible markets), the paddle is mostly neglected by contemporary players and pundits alike, in the process revealing another obsolescence: the static state that accompanies disuse—the waiting nonlife of discarded technology. The paddle's first obsolescence—the supplantation of the state of the art—signifies a moment of loss. An obsolete computer game controller is one that no longer holds or is capable of provoking the novelty necessary to stake a claim on wonder, or at least that part of wonder engendered in the playing of the newest game on the newest console—the farthest distance from technological obsolescence. The paddle's second obsolescence—disuse—signifies potential: when a newer system (e.g., PlayStation 3) supersedes an older one (e.g., Atari 2600), the older one will often sit like a fact in benighted spaces such as attics, thrift stores, garages, and closets—all prime hunting grounds for computer game collectors. The ephemera that for most people drift toward oblivion get picked up by archivists and cleaned off, catalogued, stored, studied, used, and reused. Trash becomes treasure, obsolescence newness and utility. And yet, obsolescence is not solely in the eye of the beholder, as it were; it is also in the hand, which further complicates the concept. Because obsolescence calls on the familiar in a pejorative sense—the obsolete thing has become too familiar (it now lacks novelty and surprise)—it is easy to overlook the necessity of familiarity (and thus obsolescence) to computer game development and play. After all, play demands familiarity as well as novelty; deeply complex and satisfying tasks—the kind the best play sets out and rewards generously—can only be accomplished with a level of mastery, of skill born of familiarity born of practice. Just as metaphors, in order to be successful, must merge the known with the unknown in an instantaneous insight that reveals fresh understanding, so too must computer games blend the tried and true with a twist to provoke profound and prolonged play. Computer games must always be the same, only different, familiar enough to be recognisable as forms, but new enough to create wonder as ludica. In the elegant prose of game scholar Roger Caillois, [games] must be like the leaves on the trees which survive from one season to the next and remain identical. Games must be ever similar to animal skins, the design on butterfly wings, and the spiral curves of shell fish which are transmitted unchanged from generation to generation. However, games do not have this hereditary sameness. They are innumerable and changeable. They are clad in thousands of unequally distributed shapes, just as vegetable species are, but infinitely more adaptable, spreading and acclimating themselves with disconcerting ease. (81) All this is what makes computer games so difficult to collect and study, to preserve and produce. They are always already both obsolete and pioneering. Memory as the Arbiter of Obsolescence Despite its plasticity, the concept of obsolescence offers a kind of security to its invoker: in theory, functionality and use follow a clean, linear progression. Accordingly, obsolescence can be seen not only as a thin pretext to justify a rabid consumerist desire for newness, but also as a brief memorial, a marker of passing, one that reaffirms an orderly universe and transfers a degree of security to those who witness its passing. As Aristotle explains, “the criterion of ‘security’ is the ownership of property in such places and under such conditions that the use of it is in our power; and it is ‘our own’ if it is in our power to dispose of it or keep it” (1341). Security is thus the power of alienation, and calling on the concept of obsolescence encourages the exercise of that power. Indeed, as theorist and collector Walter Benjamin argues, “The most profound enchantment for the collector is the locking of individual items within a magic circle in which they are fixed as the final thrill, the thrill of acquisition, passes over them” (62). This magic circle is really no different from the one play sociologist Johann Huizinga uses to describe the “temporary worlds” that can be carved out of the workaday one, worlds created and encapsulated by the rules and possibilities of play. There is, in fact, a powerful parallel between play and collecting, with each territorialising and deterritorialising the practice of materiality and its pleasures. For the collector, the magic circle not only encompasses the library or archive, but potentially the world, harboring as it does the possibility of a "complete collection," however obscured or damaged such a collection might be. This magic circle can also be constructed anywhere, and out of anything because the collector is a playful, nearly absurd, hunter of things whose best work occurs on the road: “I have made my most memorable purchases on trips, as a transient. Property and possession belong to the tactical sphere” (Benjamin 64). For computer game collectors especially, the circumference of the magic circle grows not with the size of a collection but with the imaginative ability to learn how to unsee what she or he has been taught to see as obsolete by industry and popular culture both: industrial, ludic, aesthetic, narratological, and ideological design. It is thus memory—in its alembic ability to make and unmake, to be made and unmade—that is the ultimate arbiter of obsolescence. From this perspective, all that is obsolete fashions a kind of infinite immemorial compendium of “what has been” that makes “what is” possible. Benjamin calls this a “magic encyclopedia,” an expansive tome for the archivist that contains “The period, the region, the craftsmanship, the former ownership—for a true collector the whole background of an item” that constitutes its being both in and beyond its present time and place (62). Vivacious Obsolescence Memory notwithstanding, the crux of computer game collection—the problematic that makes both body and mind “crooked and dwarfed”—is the timelessness of play itself. What is "old" play, for example? The kind found in Missile Command (Atari, 1980) or other golden age arcade game? Perhaps, but is this play still old when it is brought to a new platform and new audiences (e.g., http://macmost.com/iphonegames/MissileCommand.html)? What of the computer game consoles that facilitate play? Surely they grow obsolete, replaced every several years by newer, more advanced incarnations. And yet in the homebrew, retro, and collectible markets, it is the new things, the new playables that are strangely obsolete and undesirable. They are merely extant, whereas reconfigurations of old machines require imaginative new remediations in order to work and to satisfy. Older technologies and the play they enable are what are very much alive and on the cusp; these things, not their newer cousins, are the source of interest, value, experimentation, discourse, and play, that is, they are the cutting edge. So what, then, does it mean to collect and study obsoletia when the play intrinsic to them thwarts obsolescence at every turn? For computer game collectors, the answer is that ultimately there can be no difference between fad and fashion, prototype and stereotype. Obsolescence is a dynamic and incomplete designation because computer games do not age in quite the same way as do other things. The power and potential of a game archive is therefore overwhelming as well as invigorating, offering the rare but challenging chance not only to tame something wild (temporarily at least), but also to perform resurrections, bringing the old dead into new life. Computer game archivists thus trade daily in vivacious obsolescence, reveling in the defiance of moribundity in which their artifacts partake. Still, this liveliness creates other problems. How, for instance, does one organise the contents of an archive that can be categorised in so many ways (e.g., age, developer, play styles, content genres, system, audio-visual aesthetic, and so on)? What is the appropriate taxonomic way of seeing technological and ludic history when the artifacts that embody this history are constantly being made and remade, not only by scholars and historians, but also by subcultures, franchise agents, and myriad avenues of pop culture reappropriation? What does it mean for knowledge work when newness and obsolescence persist in equal measure in the same artifact? The answers to such questions are, of course, only ever temporary and never more than rickety. In the words of Benjamin, “[T]his or any other procedure is merely a dam against the springtide of memories which surges toward any collector as he contemplates his possessions” (61). The art of collection itself is one of defiance in the face of insurmountable complexity and multiplying articulations, which in the end is perhaps the real pleasure of collecting. The trial before computer game collectors is to have a sturdy boat at the ready, one capable of enduring that surging springtide to which Benjamin refers, when the well-disciplined dam of categorical judgments and explanatory structures—itself always already obsolete—inevitably breaks apart.References Aristotle. Rhetoric. Trans. W. Rhys Roberts. In The Basic Works of Aristotle. Ed. Richard McKeon. New York: Random House, 2001. 1325-1451. Benjamin, Walter. Illuminations. London: Pimlico: 1999. Caillois, Roger. Man, Play and Games. Urbana: University of Illinois, 2001. Huizinga, Johan. Homo Ludens: A Study of the Play Element in Culture. Boston: Beacon, 1955. Melville, Herbert. Mardi and a Voyage Thither. Ed. Nathalia Wright. Putney: Hendricks House, 1990.

Many problems in nature can be represented as some kind of a satisfiability problem. Several SAT solvers and SMT solvers have been developed in the last decade with the goal of checking the satisfiability of different SAT problems. An all-solution satisfiability modulo theories on top of the Z3 SMT solver is presented that uses the clause blocking algorithm to find all the solution sets of a SAT problem. Then, an incremental All-SMT solver has been presented based on the all-SMT solver which is able to find the satisfiable answers of an incremental SMT problem based on the solution set of the original problem.

Prioritization of software requirements is an important part of the requirements engineering process within the industry of software development. There are many different methods for achieving the most optimal order of software requirements, a list that shows in what order the requirements should be implemented. This degree project utilizes the SMT-based solver Z3 for an interactive prioritization algorithm. Previous studies have shown good results with another SMT-based solver called Yices. With the newer Z3 from Microsoft, the results have been improved further, and the tool is based on Python, and the framework for Z3 is called Z3PY. Experiments have been conducted on a set of different software requirements derived from a project in the healthcare industry and show that the Z3 solution is, in general, improving the requirements prioritization compared to other mentioned solutions in the study that has been tested on the same set of requirements. Results show that the Z3 solution outperformed the other SMT-based solution Yices by 2-4% regarding disagreement and by 3% regarding average distance. The results are significantly improved based on an ANOVA test with a p-value <= 0.05.

AbstractWe present a novel length-aware solving algorithm for the quantifier-free first-order theory over regex membership predicate and linear arithmetic over string length. We implement and evaluate this algorithm and related heuristics in the Z3 theorem prover. A crucial insight that underpins our algorithm is that real-world regex and string formulas contain a wealth of information about upper and lower bounds on lengths of strings, and such information can be used very effectively to simplify operations on automata representing regular expressions. Additionally, we present a number of novel general heuristics, such as the prefix/suffix method, that can be used to make a variety of regex solving algorithms more efficient in practice. We showcase the power of our algorithm and heuristics via an extensive empirical evaluation over a large and diverse benchmark of 57256 regex-heavy instances, almost 75% of which are derived from industrial applications or contributed by other solver developers. Our solver outperforms five other state-of-the-art string solvers, namely, CVC4, OSTRICH, Z3seq, Z3str3, and Z3-Trau, over this benchmark, in particular achieving a speedup of 2.4$$\times $$ × over CVC4, 4.4$$\times $$ × over Z3seq, 6.4$$\times $$ × over Z3-Trau, 9.1$$\times $$ × over Z3str3, and 13$$\times $$ × over OSTRICH.

AbstractA smart contract is a program executed on a blockchain, based on which many cryptocurrencies are implemented, and is being used for automating transactions. Due to the large amount of money that smart contracts deal with, there is a surging demand for a method that can statically and formally verify them.This tool paper describes our type-based static verification tool Helmholtz for Michelson, which is a statically typed stack-based language for writing smart contracts that are executed on the blockchain platform Tezos. Helmholtz is designed on top of our extension of Michelson’s type system with refinement types. Helmholtz takes a Michelson program annotated with a user-defined specification written in the form of a refinement type as input; it then typechecks the program against the specification based on the refinement type system, discharging the generated verification conditions with the SMT solver Z3. We briefly introduce our refinement type system for the core calculus Mini-Michelson of Michelson, which incorporates the characteristic features such as compound datatypes (e.g., lists and pairs), higher-order functions, and invocation of another contract. Helmholtz successfully verifies several practical Michelson programs, including one that transfers money to an account and that checks a digital signature.