# A melhor ferramenta para a sua pesquisa, trabalho e TCC!

Página 1 dos resultados de 2363 itens digitais encontrados em 0.314 segundos

## Generalization Strategies for the Verification of Infinite State Systems

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 05/10/2011
Português

Relevância na Pesquisa

1094.8716%

#Computer Science - Logic in Computer Science#Computer Science - Artificial Intelligence#Computer Science - Software Engineering#68T15 (Primary) 68N17, 68T27 (Secondary)#D.1.6#D.2.4#F.3.1#I.2.2#I.2.3

We present a method for the automated verification of temporal properties of
infinite state systems. Our verification method is based on the specialization
of constraint logic programs (CLP) and works in two phases: (1) in the first
phase, a CLP specification of an infinite state system is specialized with
respect to the initial state of the system and the temporal property to be
verified, and (2) in the second phase, the specialized program is evaluated by
using a bottom-up strategy. The effectiveness of the method strongly depends on
the generalization strategy which is applied during the program specialization
phase. We consider several generalization strategies obtained by combining
techniques already known in the field of program analysis and program
transformation, and we also introduce some new strategies. Then, through many
verification experiments, we evaluate the effectiveness of the generalization
strategies we have considered. Finally, we compare the implementation of our
specialization-based verification method to other constraint-based model
checking tools. The experimental results show that our method is competitive
with the methods used by those other tools. To appear in Theory and Practice of
Logic Programming (TPLP).; Comment: 24 pages...

Link permanente para citações:

## Ground interpolation for the theory of equality

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

1289.8539%

Theory interpolation has found several successful applications in model
checking. We present a novel method for computing interpolants for ground
formulas in the theory of equality. The method produces interpolants from
colored congruence graphs representing derivations in that theory. These graphs
can be produced by conventional congruence closure algorithms in a
straightforward manner. By working with graphs, rather than at the level of
individual proof steps, we are able to derive interpolants that are pleasingly
simple (conjunctions of Horn clauses) and smaller than those generated by other
tools. Our interpolation method can be seen as a theory-specific implementation
of a cooperative interpolation game between two provers. We present a generic
version of the interpolation game, parametrized by the theory T, and define a
general method to extract runs of the game from proofs in T and then generate
interpolants from these runs.

Link permanente para citações:

## TRX: A Formally Verified Parser Interpreter

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

992.77766%

#Computer Science - Logic in Computer Science#Computer Science - Formal Languages and Automata Theory#Computer Science - Programming Languages#D.3.4, D.2.4, F.3.1, F.4.2

Parsing is an important problem in computer science and yet surprisingly
little attention has been devoted to its formal verification. In this paper, we
present TRX: a parser interpreter formally developed in the proof assistant
Coq, capable of producing formally correct parsers. We are using parsing
expression grammars (PEGs), a formalism essentially representing recursive
descent parsing, which we consider an attractive alternative to context-free
grammars (CFGs). From this formalization we can extract a parser for an
arbitrary PEG grammar with the warranty of total correctness, i.e., the
resulting parser is terminating and correct with respect to its grammar and the
semantics of PEGs; both properties formally proven in Coq.; Comment: 26 pages, LMCS

Link permanente para citações:

## Decidability and Complexity for Quiescent Consistency and its Variations

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 26/11/2015
Português

Relevância na Pesquisa

993.329%

#Computer Science - Logic in Computer Science#Computer Science - Distributed, Parallel, and Cluster Computing#Computer Science - Data Structures and Algorithms#Computer Science - Formal Languages and Automata Theory#D.2.4#D.3.1#F.3.1#H.2.4

Quiescent consistency is a notion of correctness for a concurrent object that
gives meaning to the object's behaviours in quiescent states, i.e., states in
which none of the object's operations are being executed. Correctness of an
implementation object is defined in terms of a corresponding abstract
specification. This gives rise to two important verification questions:
membership (checking whether a behaviour of the implementation is allowed by
the specification) and correctness (checking whether all behaviours of the
implementation are allowed by the specification). In this paper, we show that
the membership problem for quiescent consistency is NP-complete and that the
correctness problem is decidable, but coNP-hard and in EXPSPACE. For both
problems, we consider restricted versions of quiescent consistency by assuming
an upper limit on the number of events between two quiescent points. Here, we
show that the membership problem is in PTIME, whereas correctness is in PSPACE.
Quiescent consistency does not guarantee sequential consistency, i.e., it
allows operation calls by the same process to be reordered when mapping to an
abstract specification. Therefore, we also consider quiescent sequential
consistency, which strengthens quiescent consistency with an additional
sequential consistency condition. We show that the unrestricted versions of
membership and correctness are NP-complete and undecidable...

Link permanente para citações:

## Context-Bounded Analysis For Concurrent Programs With Dynamic Creation of Threads

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

987.7376%

Context-bounded analysis has been shown to be both efficient and effective at
finding bugs in concurrent programs. According to its original definition,
context-bounded analysis explores all behaviors of a concurrent program up to
some fixed number of context switches between threads. This definition is
inadequate for programs that create threads dynamically because bounding the
number of context switches in a computation also bounds the number of threads
involved in the computation. In this paper, we propose a more general
definition of context-bounded analysis useful for programs with dynamic thread
creation. The idea is to bound the number of context switches for each thread
instead of bounding the number of switches of all threads. We consider several
variants based on this new definition, and we establish decidability and
complexity results for the analysis induced by them.

Link permanente para citações:

## Practical Run-time Checking via Unobtrusive Property Caching

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

993.7254%

The use of annotations, referred to as assertions or contracts, to describe
program properties for which run-time tests are to be generated, has become
frequent in dynamic programing languages. However, the frameworks proposed to
support such run-time testing generally incur high time and/or space overheads
over standard program execution. We present an approach for reducing this
overhead that is based on the use of memoization to cache intermediate results
of check evaluation, avoiding repeated checking of previously verified
properties. Compared to approaches that reduce checking frequency, our proposal
has the advantage of being exhaustive (i.e., all tests are checked at all
points) while still being much more efficient than standard run-time checking.
Compared to the limited previous work on memoization, it performs the task
without requiring modifications to data structure representation or checking
code. While the approach is general and system-independent, we present it for
concreteness in the context of the Ciao run-time checking framework, which
allows us to provide an operational semantics with checks and caching. We also
report on a prototype implementation and provide some experimental results that
support that using a relatively small cache leads to significant decreases in
run-time checking overhead.; Comment: 30 pages...

Link permanente para citações:

## Exporting Prolog source code

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 11/07/2002
Português

Relevância na Pesquisa

989.34914%

In this paper we present a simple source code configuration tool. ExLibris
operates on libraries and can be used to extract from local libraries all code
relevant to a particular project. Our approach is not designed to address
problems arising in code production lines, but rather, to support the needs of
individual or small teams of researchers who wish to communicate their Prolog
programs. In the process, we also wish to accommodate and encourage the writing
of reusable code. Moreover, we support and propose ways of dealing with issues
arising in the development of code that can be run on a variety of like-minded
Prolog systems. With consideration to these aims we have made the following
decisions: (i) support file-based source development, (ii) require minimal
program transformation, (iii) target simplicity of usage, and (iv) introduce
minimum number of new primitives.; Comment: 8 pages; Alexandre Tessier, editor; WLPE 2002,
http://xxx.lanl.gov/abs/cs.SE/0207052

Link permanente para citações:

## Bounded LTL Model Checking with Stable Models

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 23/05/2003
Português

Relevância na Pesquisa

997.41586%

#Computer Science - Logic in Computer Science#Computer Science - Artificial Intelligence#D.2.4#D.2.2#F.4.1#I.2.4#F.3.1

In this paper bounded model checking of asynchronous concurrent systems is
introduced as a promising application area for answer set programming. As the
model of asynchronous systems a generalisation of communicating automata,
1-safe Petri nets, are used. It is shown how a 1-safe Petri net and a
requirement on the behaviour of the net can be translated into a logic program
such that the bounded model checking problem for the net can be solved by
computing stable models of the corresponding program. The use of the stable
model semantics leads to compact encodings of bounded reachability and deadlock
detection tasks as well as the more general problem of bounded model checking
of linear temporal logic. Correctness proofs of the devised translations are
given, and some experimental results using the translation and the Smodels
system are presented.; Comment: 32 pages, to appear in Theory and Practice of Logic Programming

Link permanente para citações:

## Kleene algebra with domain

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 28/10/2003
Português

Relevância na Pesquisa

987.7868%

We propose Kleene algebra with domain (KAD), an extension of Kleene algebra
with two equational axioms for a domain and a codomain operation, respectively.
KAD considerably augments the expressiveness of Kleene algebra, in particular
for the specification and analysis of state transition systems. We develop the
basic calculus, discuss some related theories and present the most important
models of KAD. We demonstrate applicability by two examples: First, an
algebraic reconstruction of Noethericity and well-foundedness; second, an
algebraic reconstruction of propositional Hoare logic.; Comment: 40 pages

Link permanente para citações:

## Bounded Model Checking of Temporal Formulas with Alloy

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

989.9413%

#Computer Science - Software Engineering#Computer Science - Logic in Computer Science#D.2.4#F.3.1#F.4.3#I.6.4#I.6.5

Alloy is formal modeling language based on first-order relational logic, with
no specific support for specifying reactive systems. We propose the usage of
temporal logic to specify such systems, and show how bounded model checking can
be performed with the Alloy Analyzer.; Comment: New version of the ABZ'14 paper that corrects a mistake in the
encoding of the the U and R temporal operators

Link permanente para citações:

## Set Theory for Verification: I. From Foundations to Functions

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 30/10/2000
Português

Relevância na Pesquisa

1082.9214%

A logic for specification and verification is derived from the axioms of
Zermelo-Fraenkel set theory. The proofs are performed using the proof assistant
Isabelle. Isabelle is generic, supporting several different logics. Isabelle
has the flexibility to adapt to variants of set theory. Its higher-order syntax
supports the definition of new binding operators. Unknowns in subgoals can be
instantiated incrementally. The paper describes the derivation of rules for
descriptions, relations and functions, and discusses interactive proofs of
Cantor's Theorem, the Composition of Homomorphisms challenge [9], and Ramsey's
Theorem [5]. A generic proof assistant can stand up against provers dedicated
to particular logics.

Link permanente para citações:

## Events in Property Patterns

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

1401.1098%

#Computer Science - Software Engineering#Computer Science - Artificial Intelligence#Computer Science - Computation and Language#Computer Science - Symbolic Computation#D.2.4#F.3.1#F.4.1#I.2.4#D.2.1

A pattern-based approach to the presentation, codification and reuse of
property specifications for finite-state verification was proposed by Dwyer and
his collegues. The patterns enable non-experts to read and write formal
specifications for realistic systems and facilitate easy conversion of
specifications between formalisms, such as LTL, CTL, QRE. In this paper, we
extend the pattern system with events - changes of values of variables in the
context of LTL.; Comment: 14 pages, 3 figures

Link permanente para citações:

## Events in Linear-Time Properties

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 28/06/1999
Português

Relevância na Pesquisa

1402.9644%

For over a decade, researchers in formal methods tried to create formalisms
that permit natural specification of systems and allow mathematical reasoning
about their correctness. The availability of fully-automated reasoning tools
enables more non-specialists to use formal methods effectively --- their
responsibility reduces to just specifying the model and expressing the desired
properties. Thus, it is essential that these properties be represented in a
language that is easy to use and sufficiently expressive.
Linear-time temporal logic is a formalism that has been extensively used by
researchers for specifying properties of systems. When such properties are
closed under stuttering, i.e. their interpretation is not modified by
transitions that leave the system in the same state, verification tools can
utilize a partial-order reduction technique to reduce the size of the model and
thus analyze larger systems. If LTL formulas do not contain the ``next''
operator, the formulas are closed under stuttering, but the resulting language
is not expressive enough to capture many important properties, e.g., properties
involving events. Determining if an arbitrary LTL formula is closed under
stuttering is hard --- it has been proven to be PSPACE-complete.
In this paper we relax the restriction on LTL that guarantees closure under
stuttering...

Link permanente para citações:

## Removing Redundant Arguments Automatically

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 10/01/2006
Português

Relevância na Pesquisa

991.7564%

The application of automatic transformation processes during the formal
development and optimization of programs can introduce encumbrances in the
generated code that programmers usually (or presumably) do not write. An
example is the introduction of redundant arguments in the functions defined in
the program. Redundancy of a parameter means that replacing it by any
expression does not change the result. In this work, we provide methods for the
analysis and elimination of redundant arguments in term rewriting systems as a
model for the programs that can be written in more sophisticated languages. On
the basis of the uselessness of redundant arguments, we also propose an erasure
procedure which may avoid wasteful computations while still preserving the
semantics (under ascertained conditions). A prototype implementation of these
methods has been undertaken, which demonstrates the practicality of our
approach.; Comment: Accepted for publication in Theory and Practice of Logic Programming

Link permanente para citações:

## Proceedings of the Eleventh Workshop on Logic Programming Environments (WLPE'01)

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

986.6772%

#Computer Science - Programming Languages#Computer Science - Software Engineering#D.1.6#D.2.5#D.2.6#F.4.1#I.2.3

The Eleventh Workshop on Logic Programming Environments (WLPE'01) was one in
a series of international workshops in the topic area. It was held on December
1, 2001 in Paphos, Cyprus as a post-conference workshop at ICLP 2001. Eight
refereed papers were presented at the conference. A majority of the papers
involved, in some way, constraint logic programming and tools for software
development. Other topics areas addressed include execution visualization,
instructional aids (for learning users), software maintenance (including
debugging), and provisions for new paradigms.; Comment: 8 refereed papers; Anthony Kusalik, editor; 11WLPE, WLPE 2001

Link permanente para citações:

## Tracing and Explaining Execution of CLP(FD) Programs

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 11/07/2002
Português

Relevância na Pesquisa

989.34914%

Previous work in the area of tracing CLP(FD) programs mainly focuses on
providing information about control of execution and domain modification. In
this paper, we present a trace structure that provides information about
additional important aspects. We incorporate explanations in the trace
structure, i.e. reasons for why certain solver actions occur. Furthermore, we
come up with a format for describing the execution of the filtering algorithms
of global constraints. Some new ideas about the design of the trace are also
presented. For example, we have modeled our trace as a nested block structure
in order to achieve a hierarchical view. Also, new ways about how to represent
and identify different entities such as constraints and domain variables are
presented.; Comment: 16 pages; Alexandre Tessier, editor; WLPE 2002,
http://xxx.lanl.gov/abs/cs.SE/0207052

Link permanente para citações:

## SLT-Resolution for the Well-Founded Semantics

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

984.7335%

#Computer Science - Artificial Intelligence#Computer Science - Programming Languages#D.3.1#F.4.1#I.2.3

Global SLS-resolution and SLG-resolution are two representative mechanisms
for top-down evaluation of the well-founded semantics of general logic
programs. Global SLS-resolution is linear for query evaluation but suffers from
infinite loops and redundant computations. In contrast, SLG-resolution resolves
infinite loops and redundant computations by means of tabling, but it is not
linear. The principal disadvantage of a non-linear approach is that it cannot
be implemented using a simple, efficient stack-based memory structure nor can
it be easily extended to handle some strictly sequential operators such as cuts
in Prolog.
In this paper, we present a linear tabling method, called SLT-resolution, for
top-down evaluation of the well-founded semantics. SLT-resolution is a
substantial extension of SLDNF-resolution with tabling. Its main features
include: (1) It resolves infinite loops and redundant computations while
preserving the linearity. (2) It is terminating, and sound and complete w.r.t.
the well-founded semantics for programs with the bounded-term-size property
with non-floundering queries. Its time complexity is comparable with
SLG-resolution and polynomial for function-free logic programs. (3) Because of
its linearity for query evaluation...

Link permanente para citações:

## Model-Checking of Ordered Multi-Pushdown Automata

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

987.7376%

#Computer Science - Logic in Computer Science#Computer Science - Formal Languages and Automata Theory#D.2.4, D.3.1, F.4.3, I.2.2

We address the verification problem of ordered multi-pushdown automata: A
multi-stack extension of pushdown automata that comes with a constraint on
stack transitions such that a pop can only be performed on the first non-empty
stack. First, we show that the emptiness problem for ordered multi-pushdown
automata is in 2ETIME. Then, we prove that, for an ordered multi-pushdown
automata, the set of all predecessors of a regular set of configurations is an
effectively constructible regular set. We exploit this result to solve the
global model-checking which consists in computing the set of all configurations
of an ordered multi-pushdown automaton that satisfy a given w-regular property
(expressible in linear-time temporal logics or the linear-time \mu-calculus).
As an immediate consequence, we obtain an 2ETIME upper bound for the
model-checking problem of w-regular properties for ordered multi-pushdown
automata (matching its lower-bound).; Comment: 31 pages

Link permanente para citações:

## The Vampire and the FOOL

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Português

Relevância na Pesquisa

1295.80875%

This paper presents new features recently implemented in the theorem prover
Vampire, namely support for first-order logic with a first class boolean sort
(FOOL) and polymorphic arrays. In addition to having a first class boolean
sort, FOOL also contains if-then-else and let-in expressions. We argue that
presented extensions facilitate reasoning-based program analysis, both by
increasing the expressivity of first-order reasoners and by gains in
efficiency.

Link permanente para citações:

## Ordered Counter-Abstraction

Fonte: Universidade Cornell
Publicador: Universidade Cornell

Tipo: Artigo de Revista Científica

Publicado em 31/03/2012
Português

Relevância na Pesquisa

1091.9962%

We introduce a new symbolic representation based on an original
generalization of counter abstraction. Unlike classical counter abstraction
(used in the analysis of parameterized systems with unordered or unstructured
topologies) the new representation is tailored for proving properties of
linearly ordered parameterized systems, i.e., systems with arbitrary many
finite processes placed in an array. The relative positions in the array
capture the relative priorities of the processes. Configurations of such
systems are finite words of arbitrary lengths. The processes communicate using
global transitions constrained by their relative priorities. Intuitively, an
element of the symbolic representation has a base and a set of counters. It
denotes configurations that respect the constraints imposed by the counters and
that have the base as a sub word. We use the new representation in a uniform
and automatic Counter Example Guided Refinement scheme. We introduce a
relaxation operator that allows a well quasi ordering argument for the
termination of each iteration of the refinement loop. We explain how to refine
the relaxation to systematically prune out false positives. We implemented a
tool to illustrate the approach on a number of parameterized systems.

Link permanente para citações: