Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(1)
Tree Automata
Related Publications
(30)
The program Dependence Graph and its Use in Optimization
Logical Aspects of Set Constraints
Set Constraints are the Monadic Class
Type inclusion and type inference
An Engine for Logic Program Analysis
Subscribe
Academic
Publications
Solving systems of set constraints
Solving systems of set constraints,10.1109/LICS.1992.185545,Alexander Aiken,Edward L. Wimmers
Edit
Solving systems of set constraints
(
Citations: 108
)
BibTex

RIS

RefWorks
Download
Alexander Aiken
,
Edward L. Wimmers
It is shown that systems of set constraints that use all the standard set operations, especially unrestricted union and complement, can be solved. The centerpiece of the development is an algorithm that incrementally transforms a system of constraints while preserving the set of solutions. Eventually, either the system is shown to be inconsistent or all solutions can be exhibited. Most of the work is in proving that if this algorithm does not discover an inconsistency, then the system has a solution. This is done by showing that the system of constraints generated by the algorithm can be transformed into an equivalent set of equations that are guaranteed to have a solution. These equations are essentially
tree automata
Conference:
Logic in Computer Science  LICS
, 1992
DOI:
10.1109/LICS.1992.185545
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
ieeexplore.ieee.org
)
(
ieeexplore.ieee.org
)
Citation Context
(35)
...An alternative implementation is to compute a fixpoint directly via a related constraint system [
AW92
,...
Aaron R. Bradley
,
et al.
Propertydirected incremental invariant generation
...These, almost exclusively, assu me the original program is completely untyped and employ set constraints (see [
2
, 30]) for inferring types...
Chris Male
,
et al.
Java Bytecode Verification for @NonNull Types
...SetConstraint Based Analysis Set constraintbased program analyses (see, e.g., [
2
, 1]) pose classical program analysis problems  e.g., standard datao w equations, simple type inference, and monomorphic closure analysis  as set constraint problems and then solve them...
Aaron R. Bradley
,
et al.
Verification Constraint Problems with Strengthening
...Inclusion constraint systems [
2
, 1, 23, 6] are well studied and powerful formalism for formulating and implementingflow analyses...
...The first analysis is a fieldsensitivecontextinsensitivepointsto analysis; it is built on top of the Java version of the fieldinsensitive pointsto analysis for C from [
2
, 1, 23, 6] by using appropriate annotations that model field sensitivity and virtual dispatch...
Ana Milanova
,
et al.
Annotated Inclusion Constraints for Precise Flow Analysis
...We dene a language of set constraints (essentially a subset of the full language dened in [
1
, 6]) and discuss inductive form, a graphbased representation of set constraints...
John Kodumal
,
et al.
The set constraint/CFL reachability connection in practice
References
(11)
Implementing Regular Tree Expressions
(
Citations: 51
)
Alexander Aiken
,
Brian R. Murphy
Conference:
Functional Programming Languages and Computer Architecture  FPCA
, pp. 427447, 1991
On Equations for Regular Languages, Finite Automata, and Sequential Networks
(
Citations: 53
)
Janusz A. Brzozowski
,
Ernst L. Leiss
Journal:
Theoretical Computer Science  TCS
, vol. 10, no. 1, pp. 1935, 1980
Decidability of SecondOrder Theories and Automata on Infinite Trees
(
Citations: 604
)
Michael O. Rabin
Journal:
Transactions of The American Mathematical Society  TRANS AMER MATH SOC
, vol. 141, 1969
Deciding Equivalence of Finite Tree Automata
(
Citations: 82
)
Helmut Seidl
Conference:
Symposium on Theoretical Aspects of Computer Science  STACS
, pp. 480492, 1989
Logic Programs as Types for Logic Programs
(
Citations: 112
)
Thom W. Frühwirth
,
Ehud Y. Shapiro
,
Moshe Y. Vardi
,
Eyal Yardeni
Conference:
Logic in Computer Science  LICS
, pp. 300309, 1991
Sort by:
Citations
(108)
Formalisation and implementation of an algorithm for bytecode verification of @NonNull types
Chris Male
,
David J. Pearce
,
Alex Potanin
,
Constantine Dymnikov
Journal:
Science of Computer Programming  SCP
, vol. 76, no. 7, pp. 587608, 2011
Propertydirected incremental invariant generation
(
Citations: 10
)
Aaron R. Bradley
,
Zohar Manna
Journal:
Formal Aspects of Computing  FAC
, vol. 20, no. 45, pp. 379405, 2008
Java Bytecode Verification for @NonNull Types
(
Citations: 8
)
Chris Male
,
David J. Pearce
,
Alex Potanin
,
Constantine Dymnikov
Conference:
Compiler Construction  CC
, pp. 229244, 2008
Efficient fieldsensitive pointer analysis of C
(
Citations: 10
)
David J. Pearce
,
Paul H. J. Kelly
,
Chris Hankin
Journal:
ACM Transactions on Programming Languages and Systems  TOPLAS
, vol. 30, no. 1, pp. 4es, 2007
The RTA List of Open Problems
(
Citations: 4
)
Nachum Dershowitz
,
Ralf Treinen
Published in 2007.