On the representation of timed polyhedra
Identifieur interne :
000A26 ( PascalFrancis/Corpus );
précédent :
000A25;
suivant :
000A27
On the representation of timed polyhedra
Auteurs : O. Bournez ;
O. MalerSource :
-
Lecture notes in computer science [ 0302-9743 ] ; 2000.
RBID : Pascal:00-0454969
Descripteurs français
English descriptors
Abstract
In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in particular of verification tools based on timed automata. We define a representation scheme for these polyhedra based on their extreme vertices, and show that this compact representation scheme is canonical for all (convex and non-convex) polyhedra in any dimension. We then develop relatively efficient algorithms for membership, boolean operations, projection and passage of time for this representation.
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 1853 |
|---|
| A08 | 01 | 1 | ENG | @1 On the representation of timed polyhedra |
|---|
| A09 | 01 | 1 | ENG | @1 Automata, languages and programming : Geneva, 9-15 July 2000 |
|---|
| A11 | 01 | 1 | | @1 BOURNEZ (O.) |
|---|
| A11 | 02 | 1 | | @1 MALER (O.) |
|---|
| A12 | 01 | 1 | | @1 MONTANARI (Ugo) @9 ed. |
|---|
| A12 | 02 | 1 | | @1 ROLIM (José D.P.) @9 ed. |
|---|
| A12 | 03 | 1 | | @1 WELZL (Emo) @9 ed. |
|---|
| A14 | 01 | | | @1 LORIA, Campus Scientifique BP 239 @2 54506 Vandoeuvre lès Nancy @3 FRA @Z 1 aut. |
|---|
| A14 | 02 | | | @1 VERIMAG 2, av. de Vignate @2 38610 Gières @3 FRA @Z 2 aut. |
|---|
| A20 | | | | @1 793-807 |
|---|
| A21 | | | | @1 2000 |
|---|
| A23 | 01 | | | @0 ENG |
|---|
| A26 | 01 | | | @0 3-540-67715-1 |
|---|
| A43 | 01 | | | @1 INIST @2 16343 @5 354000090060820650 |
|---|
| A44 | | | | @0 0000 @1 © 2000 INIST-CNRS. All rights reserved. |
|---|
| A45 | | | | @0 19 ref. |
|---|
| A47 | 01 | 1 | | @0 00-0454969 |
|---|
| 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 In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in particular of verification tools based on timed automata. We define a representation scheme for these polyhedra based on their extreme vertices, and show that this compact representation scheme is canonical for all (convex and non-convex) polyhedra in any dimension. We then develop relatively efficient algorithms for membership, boolean operations, projection and passage of time for this representation. |
|---|
| C02 | 01 | X | | @0 001D02A03 |
|---|
| C03 | 01 | X | FRE | @0 Informatique théorique @5 01 |
|---|
| C03 | 01 | X | ENG | @0 Computer theory @5 01 |
|---|
| C03 | 01 | X | SPA | @0 Informática teórica @5 01 |
|---|
| C03 | 02 | 3 | FRE | @0 Analyse atteignabilité @5 02 |
|---|
| C03 | 02 | 3 | ENG | @0 Reachability analysis @5 02 |
|---|
| C03 | 03 | X | FRE | @0 Complexité automate @5 03 |
|---|
| C03 | 03 | X | ENG | @0 Automaton complexity @5 03 |
|---|
| C03 | 03 | X | SPA | @0 Complejidad autómata @5 03 |
|---|
| C03 | 04 | 3 | FRE | @0 Vérification formelle @5 04 |
|---|
| C03 | 04 | 3 | ENG | @0 Formal verification @5 04 |
|---|
| C03 | 05 | X | FRE | @0 Fonction booléenne @5 05 |
|---|
| C03 | 05 | X | ENG | @0 Boolean function @5 05 |
|---|
| C03 | 05 | X | SPA | @0 Función booliana @5 05 |
|---|
| C03 | 06 | X | FRE | @0 Système hybride @5 06 |
|---|
| C03 | 06 | X | ENG | @0 Hybrid system @5 06 |
|---|
| C03 | 06 | X | SPA | @0 Sistema híbrido @5 06 |
|---|
| N21 | | | | @1 304 |
|---|
|
|---|
| pR |
| A30 | 01 | 1 | ENG | @1 ICALP 2000 : international colloquium on automata, languages and programming @2 27 @3 Geneva CHE @4 2000-07-09 |
|---|
|
|---|
Format Inist (serveur)
| NO : | PASCAL 00-0454969 INIST |
|---|
| ET : | On the representation of timed polyhedra |
|---|
| AU : | BOURNEZ (O.); MALER (O.); MONTANARI (Ugo); ROLIM (José D.P.); WELZL (Emo) |
|---|
| AF : | LORIA, Campus Scientifique BP 239/54506 Vandoeuvre lès Nancy/France (1 aut.); VERIMAG 2, av. de Vignate/38610 Gières/France (2 aut.) |
|---|
| DT : | Publication en série; Congrès; Niveau analytique |
|---|
| SO : | Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2000; Vol. 1853; Pp. 793-807; Bibl. 19 ref. |
|---|
| LA : | Anglais |
|---|
| EA : | In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in particular of verification tools based on timed automata. We define a representation scheme for these polyhedra based on their extreme vertices, and show that this compact representation scheme is canonical for all (convex and non-convex) polyhedra in any dimension. We then develop relatively efficient algorithms for membership, boolean operations, projection and passage of time for this representation. |
|---|
| CC : | 001D02A03 |
|---|
| FD : | Informatique théorique; Analyse atteignabilité; Complexité automate; Vérification formelle; Fonction booléenne; Système hybride |
|---|
| ED : | Computer theory; Reachability analysis; Automaton complexity; Formal verification; Boolean function; Hybrid system |
|---|
| SD : | Informática teórica; Complejidad autómata; Función booliana; Sistema híbrido |
|---|
| LO : | INIST-16343.354000090060820650 |
|---|
| ID : | 00-0454969 |
|---|
Links to Exploration step
Pascal:00-0454969
Le document en format XML
<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">On the representation of timed polyhedra</title>
<author><name sortKey="Bournez, O" sort="Bournez, O" uniqKey="Bournez O" first="O." last="Bournez">O. Bournez</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, Campus Scientifique BP 239</s1>
<s2>54506 Vandoeuvre lès Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Maler, O" sort="Maler, O" uniqKey="Maler O" first="O." last="Maler">O. Maler</name>
<affiliation><inist:fA14 i1="02"><s1>VERIMAG 2, av. de Vignate</s1>
<s2>38610 Gières</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">00-0454969</idno>
<date when="2000">2000</date>
<idno type="stanalyst">PASCAL 00-0454969 INIST</idno>
<idno type="RBID">Pascal:00-0454969</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000A26</idno>
</publicationStmt><sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">On the representation of timed polyhedra</title>
<author><name sortKey="Bournez, O" sort="Bournez, O" uniqKey="Bournez O" first="O." last="Bournez">O. Bournez</name>
<affiliation><inist:fA14 i1="01"><s1>LORIA, Campus Scientifique BP 239</s1>
<s2>54506 Vandoeuvre lès Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</inist:fA14><author><name sortKey="Maler, O" sort="Maler, O" uniqKey="Maler O" first="O." last="Maler">O. Maler</name>
<affiliation><inist:fA14 i1="02"><s1>VERIMAG 2, av. de Vignate</s1>
<s2>38610 Gières</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14><series><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
<imprint><date when="2000">2000</date>
</imprint><seriesStmt><title level="j" type="main">Lecture notes in computer science</title>
<idno type="ISSN">0302-9743</idno>
</seriesStmt><profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Automaton complexity</term>
<term>Boolean function</term>
<term>Computer theory</term>
<term>Formal verification</term>
<term>Hybrid system</term>
<term>Reachability analysis</term>
</keywords><keywords scheme="Pascal" xml:lang="fr"><term>Informatique théorique</term>
<term>Analyse atteignabilité</term>
<term>Complexité automate</term>
<term>Vérification formelle</term>
<term>Fonction booléenne</term>
<term>Système hybride</term>
</keywords><front><div type="abstract" xml:lang="en">In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in particular of verification tools based on timed automata. We define a representation scheme for these polyhedra based on their extreme vertices, and show that this compact representation scheme is canonical for all (convex and non-convex) polyhedra in any dimension. We then develop relatively efficient algorithms for membership, boolean operations, projection and passage of time for this representation.</div>
</front><inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0302-9743</s0>
</fA01><fA05><s2>1853</s2>
</fA05><fA08 i1="01" i2="1" l="ENG"><s1>On the representation of timed polyhedra</s1>
</fA08><fA09 i1="01" i2="1" l="ENG"><s1>Automata, languages and programming : Geneva, 9-15 July 2000</s1>
</fA09><fA11 i1="01" i2="1"><s1>BOURNEZ (O.)</s1>
</fA11><fA11 i1="02" i2="1"><s1>MALER (O.)</s1>
</fA11><fA12 i1="01" i2="1"><s1>MONTANARI (Ugo)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="02" i2="1"><s1>ROLIM (José D.P.)</s1>
<s9>ed.</s9>
</fA12><fA12 i1="03" i2="1"><s1>WELZL (Emo)</s1>
<s9>ed.</s9>
</fA12><fA14 i1="01"><s1>LORIA, Campus Scientifique BP 239</s1>
<s2>54506 Vandoeuvre lès Nancy</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
</fA14><fA14 i1="02"><s1>VERIMAG 2, av. de Vignate</s1>
<s2>38610 Gières</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14><fA20><s1>793-807</s1>
</fA20><fA21><s1>2000</s1>
</fA21><fA23 i1="01"><s0>ENG</s0>
</fA23><fA26 i1="01"><s0>3-540-67715-1</s0>
</fA26><fA43 i1="01"><s1>INIST</s1>
<s2>16343</s2>
<s5>354000090060820650</s5>
</fA43><fA44><s0>0000</s0>
<s1>© 2000 INIST-CNRS. All rights reserved.</s1>
</fA44><fA45><s0>19 ref.</s0>
</fA45><fA47 i1="01" i2="1"><s0>00-0454969</s0>
</fA47><fA60><s1>P</s1>
<s2>C</s2>
</fA60><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>In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in particular of verification tools based on timed automata. We define a representation scheme for these polyhedra based on their extreme vertices, and show that this compact representation scheme is canonical for all (convex and non-convex) polyhedra in any dimension. We then develop relatively efficient algorithms for membership, boolean operations, projection and passage of time for this representation.</s0>
</fC01><fC02 i1="01" i2="X"><s0>001D02A03</s0>
</fC02><fC03 i1="01" i2="X" l="FRE"><s0>Informatique théorique</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="ENG"><s0>Computer theory</s0>
<s5>01</s5>
</fC03><fC03 i1="01" i2="X" l="SPA"><s0>Informática teórica</s0>
<s5>01</s5>
</fC03><fC03 i1="02" i2="3" l="FRE"><s0>Analyse atteignabilité</s0>
<s5>02</s5>
</fC03><fC03 i1="02" i2="3" l="ENG"><s0>Reachability analysis</s0>
<s5>02</s5>
</fC03><fC03 i1="03" i2="X" l="FRE"><s0>Complexité automate</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="ENG"><s0>Automaton complexity</s0>
<s5>03</s5>
</fC03><fC03 i1="03" i2="X" l="SPA"><s0>Complejidad autómata</s0>
<s5>03</s5>
</fC03><fC03 i1="04" i2="3" l="FRE"><s0>Vérification formelle</s0>
<s5>04</s5>
</fC03><fC03 i1="04" i2="3" l="ENG"><s0>Formal verification</s0>
<s5>04</s5>
</fC03><fC03 i1="05" i2="X" l="FRE"><s0>Fonction booléenne</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="ENG"><s0>Boolean function</s0>
<s5>05</s5>
</fC03><fC03 i1="05" i2="X" l="SPA"><s0>Función booliana</s0>
<s5>05</s5>
</fC03><fC03 i1="06" i2="X" l="FRE"><s0>Système hybride</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="ENG"><s0>Hybrid system</s0>
<s5>06</s5>
</fC03><fC03 i1="06" i2="X" l="SPA"><s0>Sistema híbrido</s0>
<s5>06</s5>
</fC03><fN21><s1>304</s1>
</fN21><pR><fA30 i1="01" i2="1" l="ENG"><s1>ICALP 2000 : international colloquium on automata, languages and programming</s1>
<s2>27</s2>
<s3>Geneva CHE</s3>
<s4>2000-07-09</s4>
</fA30><server><NO>PASCAL 00-0454969 INIST</NO>
<ET>On the representation of timed polyhedra</ET>
<AU>BOURNEZ (O.); MALER (O.); MONTANARI (Ugo); ROLIM (José D.P.); WELZL (Emo)</AU>
<AF>LORIA, Campus Scientifique BP 239/54506 Vandoeuvre lès Nancy/France (1 aut.); VERIMAG 2, av. de Vignate/38610 Gières/France (2 aut.)</AF>
<DT>Publication en série; Congrès; Niveau analytique</DT>
<SO>Lecture notes in computer science; ISSN 0302-9743; Allemagne; Da. 2000; Vol. 1853; Pp. 793-807; Bibl. 19 ref.</SO>
<LA>Anglais</LA>
<EA>In this paper we investigate timed polyhedra, i.e. polyhedra which are finite unions of full dimensional simplices of a special kind. Such polyhedra form the basis of timing analysis and in particular of verification tools based on timed automata. We define a representation scheme for these polyhedra based on their extreme vertices, and show that this compact representation scheme is canonical for all (convex and non-convex) polyhedra in any dimension. We then develop relatively efficient algorithms for membership, boolean operations, projection and passage of time for this representation.</EA>
<CC>001D02A03</CC>
<FD>Informatique théorique; Analyse atteignabilité; Complexité automate; Vérification formelle; Fonction booléenne; Système hybride</FD>
<ED>Computer theory; Reachability analysis; Automaton complexity; Formal verification; Boolean function; Hybrid system</ED>
<SD>Informática teórica; Complejidad autómata; Función booliana; Sistema híbrido</SD>
<LO>INIST-16343.354000090060820650</LO>
<ID>00-0454969</ID>
</server>
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 000A26 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000A26 | 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:00-0454969
|texte= On the representation of timed polyhedra
}}
| 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 |  |
