| Presentation | 1999/11/16 A decision algorithm for rational Presburger sentences using a division routine of polyhedra Naoki SHIBATA, Kozo OKANO, Kenichi TANIGUCHI, |
|---|---|
| PDF Download Page | PDF download Page Link |
| Abstract(in Japanese) | (See Japanese page) |
| Abstract(in English) | Formerly, we have proposed the fastest decision algorithm for prenex-normal-form rational Presburger Sentences. The algorithm is used in areas of testing of protocols, timing verification of hardware, and so on. In this paper, we present techniques to reduce execution time of the algorithm. The techniques are based on three devices: 1. Making the algorithm merge polyhedra into a concave polyhedron and handle the concave polyhedron in order to minimize the number of polyhedra that express a region, 2. Improving a method to calculate a region of a shadow without processing extra polyhedra that don't affect the result of the decision and 3. Reducing the number of judgements on whether faces are crossing. |
| Keyword(in Japanese) | (See Japanese page) |
| Keyword(in English) | Thoery of rationals with addtion / decision procedure and polyhedra |
| Paper # | COMP99-49 |
| Date of Issue |
| Conference Information | |
| Committee | COMP |
|---|---|
| Conference Date | 1999/11/16(1days) |
| Place (in Japanese) | (See Japanese page) |
| Place (in English) | |
| Topics (in Japanese) | (See Japanese page) |
| Topics (in English) | |
| Chair | |
| Vice Chair | |
| Secretary | |
| Assistant | |
| Paper Information | |
| Registration To | Theoretical Foundations of Computing (COMP) |
|---|---|
| Language | JPN |
| Title (in Japanese) | (See Japanese page) |
| Sub Title (in Japanese) | (See Japanese page) |
| Title (in English) | A decision algorithm for rational Presburger sentences using a division routine of polyhedra |
| Sub Title (in English) | |
| Keyword(1) | Thoery of rationals with addtion |
| Keyword(2) | decision procedure and polyhedra |
| 1st Author's Name | Naoki SHIBATA |
| 1st Author's Affiliation | Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University() |
| 2nd Author's Name | Kozo OKANO |
| 2nd Author's Affiliation | Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| 3rd Author's Name | Kenichi TANIGUCHI |
| 3rd Author's Affiliation | Division of Informatics and Mathematical Science, Graduate School of Engineering Science, Osaka University |
| Date | 1999/11/16 |
| Paper # | COMP99-49 |
| Volume (vol) | vol.99 |
| Number (no) | 432 |
| Page | pp.pp.- |
| #Pages | 8 |
| Date of Issue | |