Serveur d'exploration sur la recherche en informatique en Lorraine

Attention, ce site est en cours de développement !
Attention, site généré par des moyens informatiques à partir de corpus bruts.
Les informations ne sont donc pas validées.

Resource tableaux

Identifieur interne : 000829 ( PascalFrancis/Corpus ); précédent : 000828; suivant : 000830

Resource tableaux

Auteurs : Didier Galmiche ; Daniel Mery ; David Pym

Source :

RBID : Pascal:03-0077541

Descripteurs français

English descriptors

Abstract

The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource rich enough to provide a "pointer logic" semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, ⊥, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI: the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose, by considering partially defined monoids, a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

pA  
A01 01  1    @0 0302-9743
A05       @2 2471
A08 01  1  ENG  @1 Resource tableaux
A09 01  1  ENG  @1 CSL 2002 : computer science logic : Edinburgh, 22-25 September 2002
A11 01  1    @1 GALMICHE (Didier)
A11 02  1    @1 MERY (Daniel)
A11 03  1    @1 PYM (David)
A12 01  1    @1 BRADFIELD (Julian) @9 ed.
A14 01      @1 LORIA @2 Nancy @3 FRA @Z 1 aut. @Z 2 aut.
A14 02      @1 University of Bath @3 GBR @Z 3 aut.
A20       @1 183-199
A21       @1 2002
A23 01      @0 ENG
A26 01      @0 3-540-44240-5
A43 01      @1 INIST @2 16343 @5 354000108459080120
A44       @0 0000 @1 © 2003 INIST-CNRS. All rights reserved.
A45       @0 14 ref.
A47 01  1    @0 03-0077541
A60       @1 P @2 C
A61       @0 A
A64 01  1    @0 Lecture notes in computer science
A66 01      @0 DEU
C01 01    ENG  @0 The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource rich enough to provide a "pointer logic" semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, ⊥, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI: the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose, by considering partially defined monoids, a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.
C02 01  X    @0 001D02A02
C03 01  X  FRE  @0 Bunching @5 01
C03 01  X  ENG  @0 Bunching @5 01
C03 01  X  SPA  @0 Agrupación @5 01
C03 02  X  FRE  @0 Représentation connaissances @5 02
C03 02  X  ENG  @0 Knowledge representation @5 02
C03 02  X  SPA  @0 Representación conocimientos @5 02
C03 03  X  FRE  @0 Structure programme @5 03
C03 03  X  ENG  @0 Program structure @5 03
C03 03  X  SPA  @0 Estructura programa @5 03
C03 04  X  FRE  @0 Structure donnée @5 04
C03 04  X  ENG  @0 Data structure @5 04
C03 04  X  SPA  @0 Estructura datos @5 04
C03 05  X  FRE  @0 Démonstration théorème @5 05
C03 05  X  ENG  @0 Theorem proving @5 05
C03 05  X  SPA  @0 Demostración teorema @5 05
C03 06  X  FRE  @0 Décidabilité @5 06
C03 06  X  ENG  @0 Decidability @5 06
C03 06  X  SPA  @0 Decidibilidad @5 06
C03 07  X  FRE  @0 Algorithme recherche @5 07
C03 07  X  ENG  @0 Search algorithm @5 07
C03 07  X  SPA  @0 Algoritmo búsqueda @5 07
C03 08  X  FRE  @0 Appel procédure @5 08
C03 08  X  ENG  @0 Procedure call @5 08
C03 08  X  SPA  @0 Llamada procedimiento @5 08
C03 09  X  FRE  @0 Consistance sémantique @5 09
C03 09  X  ENG  @0 Soundness @5 09
C03 09  X  SPA  @0 Consistencia semantica @5 09
C03 10  X  FRE  @0 Sémantique @5 10
C03 10  X  ENG  @0 Semantics @5 10
C03 10  X  SPA  @0 Semántica @5 10
C03 11  X  FRE  @0 Bunched implication @4 INC @5 82
C03 12  X  FRE  @0 Pointeur @4 CD @5 96
C03 12  X  ENG  @0 Pointer @4 CD @5 96
N21       @1 041
N82       @1 PSI
pR  
A30 01  1  ENG  @1 Computer science logic. International workshop @2 16 @3 Edinburgh GBR @4 2002-09-22
A30 02  1  ENG  @1 EACSL. Annual conference @2 11 @3 Edinburgh GBR @4 2002-09-22

Format Inist (serveur)

NO : PASCAL 03-0077541 INIST
ET : Resource tableaux
AU : GALMICHE (Didier); MERY (Daniel); PYM (David); BRADFIELD (Julian)
AF : LORIA/Nancy/France (1 aut., 2 aut.); University of Bath/Royaume-Uni (3 aut.)
DT : Publication en série; Congrès; Niveau analytique
SO : Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2002; Vol. 2471; Pp. 183-199; Bibl. 14 ref.
LA : Anglais
EA : The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource rich enough to provide a "pointer logic" semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, ⊥, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI: the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose, by considering partially defined monoids, a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.
CC : 001D02A02
FD : Bunching; Représentation connaissances; Structure programme; Structure donnée; Démonstration théorème; Décidabilité; Algorithme recherche; Appel procédure; Consistance sémantique; Sémantique; Bunched implication; Pointeur
ED : Bunching; Knowledge representation; Program structure; Data structure; Theorem proving; Decidability; Search algorithm; Procedure call; Soundness; Semantics; Pointer
SD : Agrupación; Representación conocimientos; Estructura programa; Estructura datos; Demostración teorema; Decidibilidad; Algoritmo búsqueda; Llamada procedimiento; Consistencia semantica; Semántica
LO : INIST-16343.354000108459080120
ID : 03-0077541

Links to Exploration step

Pascal:03-0077541

Le document en format XML

<record>
<TEI>
<teiHeader>
<fileDesc>
<titleStmt>
<title xml:lang="en" level="a">Resource tableaux</title>
<author>
<name sortKey="Galmiche, Didier" sort="Galmiche, Didier" uniqKey="Galmiche D" first="Didier" last="Galmiche">Didier Galmiche</name>
<affiliation>
<inist:fA14 i1="01">
<s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author>
<name sortKey="Mery, Daniel" sort="Mery, Daniel" uniqKey="Mery D" first="Daniel" last="Mery">Daniel Mery</name>
<affiliation>
<inist:fA14 i1="01">
<s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author>
<name sortKey="Pym, David" sort="Pym, David" uniqKey="Pym D" first="David" last="Pym">David Pym</name>
<affiliation>
<inist:fA14 i1="02">
<s1>University of Bath</s1>
<s3>GBR</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt>
<idno type="wicri:source">INIST</idno>
<idno type="inist">03-0077541</idno>
<date when="2002">2002</date>
<idno type="stanalyst">PASCAL 03-0077541 INIST</idno>
<idno type="RBID">Pascal:03-0077541</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000829</idno>
</publicationStmt>
<sourceDesc>
<biblStruct>
<analytic>
<title xml:lang="en" level="a">Resource tableaux</title>
<author>
<name sortKey="Galmiche, Didier" sort="Galmiche, Didier" uniqKey="Galmiche D" first="Didier" last="Galmiche">Didier Galmiche</name>
<affiliation>
<inist:fA14 i1="01">
<s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author>
<name sortKey="Mery, Daniel" sort="Mery, Daniel" uniqKey="Mery D" first="Daniel" last="Mery">Daniel Mery</name>
<affiliation>
<inist:fA14 i1="01">
<s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author>
<name sortKey="Pym, David" sort="Pym, David" uniqKey="Pym D" first="David" last="Pym">David Pym</name>
<affiliation>
<inist:fA14 i1="02">
<s1>University of Bath</s1>
<s3>GBR</s3>
<sZ>3 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series>
<title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint>
<date when="2002">2002</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt>
<title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt>
</fileDesc>
<profileDesc>
<textClass>
<keywords scheme="KwdEn" xml:lang="en">
<term>Bunching</term>
<term>Data structure</term>
<term>Decidability</term>
<term>Knowledge representation</term>
<term>Pointer</term>
<term>Procedure call</term>
<term>Program structure</term>
<term>Search algorithm</term>
<term>Semantics</term>
<term>Soundness</term>
<term>Theorem proving</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr">
<term>Bunching</term>
<term>Représentation connaissances</term>
<term>Structure programme</term>
<term>Structure donnée</term>
<term>Démonstration théorème</term>
<term>Décidabilité</term>
<term>Algorithme recherche</term>
<term>Appel procédure</term>
<term>Consistance sémantique</term>
<term>Sémantique</term>
<term>Bunched implication</term>
<term>Pointeur</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front>
<div type="abstract" xml:lang="en">The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource rich enough to provide a "pointer logic" semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, ⊥, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI: the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose, by considering partially defined monoids, a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.</div>
</front>
</TEI>
<inist>
<standard h6="B">
<pA>
<fA01 i1="01" i2="1">
<s0>0302-9743</s0>
</fA01>
<fA05>
<s2>2471</s2>
</fA05>
<fA08 i1="01" i2="1" l="ENG">
<s1>Resource tableaux</s1>
</fA08>
<fA09 i1="01" i2="1" l="ENG">
<s1>CSL 2002 : computer science logic : Edinburgh, 22-25 September 2002</s1>
</fA09>
<fA11 i1="01" i2="1">
<s1>GALMICHE (Didier)</s1>
</fA11>
<fA11 i1="02" i2="1">
<s1>MERY (Daniel)</s1>
</fA11>
<fA11 i1="03" i2="1">
<s1>PYM (David)</s1>
</fA11>
<fA12 i1="01" i2="1">
<s1>BRADFIELD (Julian)</s1>
<s9>ed.</s9>
</fA12>
<fA14 i1="01">
<s1>LORIA</s1>
<s2>Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>2 aut.</sZ>
</fA14>
<fA14 i1="02">
<s1>University of Bath</s1>
<s3>GBR</s3>
<sZ>3 aut.</sZ>
</fA14>
<fA20>
<s1>183-199</s1>
</fA20>
<fA21>
<s1>2002</s1>
</fA21>
<fA23 i1="01">
<s0>ENG</s0>
</fA23>
<fA26 i1="01">
<s0>3-540-44240-5</s0>
</fA26>
<fA43 i1="01">
<s1>INIST</s1>
<s2>16343</s2>
<s5>354000108459080120</s5>
</fA43>
<fA44>
<s0>0000</s0>
<s1>© 2003 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45>
<s0>14 ref.</s0>
</fA45>
<fA47 i1="01" i2="1">
<s0>03-0077541</s0>
</fA47>
<fA60>
<s1>P</s1>
<s2>C</s2>
</fA60>
<fA61>
<s0>A</s0>
</fA61>
<fA64 i1="01" i2="1">
<s0>Lecture notes in computer science</s0>
</fA64>
<fA66 i1="01">
<s0>DEU</s0>
</fA66>
<fC01 i1="01" l="ENG">
<s0>The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource rich enough to provide a "pointer logic" semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, ⊥, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI: the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose, by considering partially defined monoids, a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.</s0>
</fC01>
<fC02 i1="01" i2="X">
<s0>001D02A02</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE">
<s0>Bunching</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG">
<s0>Bunching</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA">
<s0>Agrupación</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE">
<s0>Représentation connaissances</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG">
<s0>Knowledge representation</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA">
<s0>Representación conocimientos</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE">
<s0>Structure programme</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG">
<s0>Program structure</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA">
<s0>Estructura programa</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE">
<s0>Structure donnée</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG">
<s0>Data structure</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA">
<s0>Estructura datos</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE">
<s0>Démonstration théorème</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG">
<s0>Theorem proving</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA">
<s0>Demostración teorema</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE">
<s0>Décidabilité</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG">
<s0>Decidability</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA">
<s0>Decidibilidad</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE">
<s0>Algorithme recherche</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG">
<s0>Search algorithm</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA">
<s0>Algoritmo búsqueda</s0>
<s5>07</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE">
<s0>Appel procédure</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG">
<s0>Procedure call</s0>
<s5>08</s5>
</fC03>
<fC03 i1="08" i2="X" l="SPA">
<s0>Llamada procedimiento</s0>
<s5>08</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE">
<s0>Consistance sémantique</s0>
<s5>09</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG">
<s0>Soundness</s0>
<s5>09</s5>
</fC03>
<fC03 i1="09" i2="X" l="SPA">
<s0>Consistencia semantica</s0>
<s5>09</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE">
<s0>Sémantique</s0>
<s5>10</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG">
<s0>Semantics</s0>
<s5>10</s5>
</fC03>
<fC03 i1="10" i2="X" l="SPA">
<s0>Semántica</s0>
<s5>10</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE">
<s0>Bunched implication</s0>
<s4>INC</s4>
<s5>82</s5>
</fC03>
<fC03 i1="12" i2="X" l="FRE">
<s0>Pointeur</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="12" i2="X" l="ENG">
<s0>Pointer</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fN21>
<s1>041</s1>
</fN21>
<fN82>
<s1>PSI</s1>
</fN82>
</pA>
<pR>
<fA30 i1="01" i2="1" l="ENG">
<s1>Computer science logic. International workshop</s1>
<s2>16</s2>
<s3>Edinburgh GBR</s3>
<s4>2002-09-22</s4>
</fA30>
<fA30 i1="02" i2="1" l="ENG">
<s1>EACSL. Annual conference</s1>
<s2>11</s2>
<s3>Edinburgh GBR</s3>
<s4>2002-09-22</s4>
</fA30>
</pR>
</standard>
<server>
<NO>PASCAL 03-0077541 INIST</NO>
<ET>Resource tableaux</ET>
<AU>GALMICHE (Didier); MERY (Daniel); PYM (David); BRADFIELD (Julian)</AU>
<AF>LORIA/Nancy/France (1 aut., 2 aut.); University of Bath/Royaume-Uni (3 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2002; Vol. 2471; Pp. 183-199; Bibl. 14 ref.</SO>
<LA>Anglais</LA>
<EA>The logic of bunched implications, BI, provides a logical analysis of a basic notion of resource rich enough to provide a "pointer logic" semantics for programs which manipulate mutable data structures. We develop a theory of semantic tableaux for BI, so providing an elegant basis for efficient theorem proving tools for BI. It is based on the use of an algebra of labels for BI's tableaux to solve the resource-distribution problem, the labels being the elements of resource models. For BI with inconsistency, ⊥, the challenge consists in dealing with BI's Grothendieck topological models within such a proof-search method, based on labels. We prove soundness and completeness theorems for a resource tableaux method TBI with respect to this semantics and provide a way to build countermodels from so-called dependency graphs. As consequences, we have two strong new results for BI: the decidability of propositional BI and the finite model property with respect to Grothendieck topological semantics. In addition, we propose, by considering partially defined monoids, a new semantics which generalizes the semantics of BI's pointer logic and for which BI is complete.</EA>
<CC>001D02A02</CC>
<FD>Bunching; Représentation connaissances; Structure programme; Structure donnée; Démonstration théorème; Décidabilité; Algorithme recherche; Appel procédure; Consistance sémantique; Sémantique; Bunched implication; Pointeur</FD>
<ED>Bunching; Knowledge representation; Program structure; Data structure; Theorem proving; Decidability; Search algorithm; Procedure call; Soundness; Semantics; Pointer</ED>
<SD>Agrupación; Representación conocimientos; Estructura programa; Estructura datos; Demostración teorema; Decidibilidad; Algoritmo búsqueda; Llamada procedimiento; Consistencia semantica; Semántica</SD>
<LO>INIST-16343.354000108459080120</LO>
<ID>03-0077541</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000829 | SxmlIndent | more

Ou

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000829 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:03-0077541
   |texte=   Resource tableaux
}}

Wicri

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022