가야대학교 분성도서관
주메뉴
자료검색
- Home
- 상세정보
상세정보
부가기능
The Computational Complexity of Presburger Arithmetic
상세 프로파일
| 자료유형 | E-Book |
|---|---|
| 개인저자 | Nguyen Luu, Danh. |
| 단체저자명 | University of California, Los Angeles. Mathematics 0540. |
| 서명/저자사항 | The Computational Complexity of Presburger Arithmetic. |
| 발행사항 | [S.l.] : University of California, Los Angeles., 2018 |
| 발행사항 | Ann Arbor : ProQuest Dissertations & Theses, 2018 |
| 형태사항 | 238 p. |
| 소장본 주기 | School code: 0031. |
| ISBN | 9780438081598 |
| 일반주기 |
Source: Dissertation Abstracts International, Volume: 79-11(E), Section: B.
Adviser: Igor Pak. |
| 요약 | A wide variety of problems in Discrete Optimization and Integer Programming can be naturally phrased in the language of Presburger Arithmetic (PA), which is the first order logic on the integers with only additions and inequalities. Understandin |
| 요약 | Most important in PA are the numbers of variables and inequalities involved. The main question addressed in Part I of the dissertation is: By restricting the number of variables and inequalities in PA, do we obtain polynomial complexity? We give |
| 요약 | In Part II, we investigate the related theory of Short Generating Functions developed by Barvinok and Woods. First, we first extend their polynomial time algorithm for enumerating projected integer points in polytopes to the unbounded polyhedra |
| 요약 | In Part III, we present two different problems. The first one concerns an extension of PA with scalar multiplications by algebraic irrationals. We show that it has high nonelementary complexity far exceeding that of classical PA, even with a res |
| 일반주제명 | Mathematics. |
| 언어 | 영어 |
| 기본자료 저록 | Dissertation Abstracts International79-11B(E). Dissertation Abstract International |
| 대출바로가기 | http://www.riss.kr/pdu/ddodLink.do?id=T14999110 |
소장정보
- 소장정보
인쇄
| No. | 등록번호 | 청구기호 | 소장처 | 도서상태 | 반납예정일 | 예약 | 서비스 | 매체정보 |
|---|---|---|---|---|---|---|---|---|
| 1 | WE00028418 | 510 | 가야대학교// | 대출가능 |
|
카피라이터
