第四屆 程式語言暨系統研討會

交通大學 資訊科學系 及

中央研究院 資訊科學研究所 合辦

民國八十九年五月十九日 ( 星期五 )

The 4th Joint Seminar on Programming Languages and Systems

Dept. of Computer and Information Science, Chiao-Tung University

and

Institute of Information Science, Academia Sinica

May 19, Friday, 2000

Purposes

This seminar brings together researchers and students working on programming languages and systems to present results in their fields. It aims to provide a stimulating environment to further facilitate the exchange of ideas and experiences among the participants.

Schedule

10-10:10 am

簡榮宏 交通大學資訊科學系
Opening ceremony

10:10-11 am

王凡, 中央研究院 (Farn Wang, Academia Sinica)
Efficient Data-structure for the Verification of Real-Time Systems

11:10-12 pm

黃元欣, 海洋大學 (Yuan-Shin Hwang, National Taiwan Ocean University)
Traversal-Pattern-Sensitive Pointer Analysis

12-1:30 pm

午餐 (敬備便當)

1:30-2:20 pm

猶嘉槐, 中央研究院及加拿大Alberta大學 (Jia-Huai You, Academia Sinica and University of Alberta, Canada)
Nonmonotonic Reasoning as Prioritized Argumentation

2:30-3:20 pm

葉慶隆, 大同大學 (Yeh, Ching-Long, Tatung University)
A Logic Programming Approach to Supporting the Entries of XML Documents in an Object Database

Time and Place

The seminar will be held at 新竹市 交通大學 電機資訊大樓 一樓 第三會議室 on May 19 (Friday), 2000. A street map of NCTU is available at http://www.cis.nctu.edu.tw/~plas/map/mapNCTU.jpg. A campus map of NCTU is available at http://www.cis.nctu.edu.tw/~plas/map/mapNCTUcampus.jpg.

Students are especially welcomed to attend this seminar series. There is no registration fee for the seminars. Free lunches will be provided. To help plan the event and the lunch boxes, however, please send a plain-text e-mail to wuuyang@cis.nctu.edu.tw or fax to (03) 5721490 楊武 with your name (both in Chinese and English) and your current affiliation if you plan to attend. Further information about this event, including abstracts of the talks, will be available from WWW at http://www.cis.nctu.edu.tw/~plas/plas2000.html.

Campus accommodation is available. The cost is $600 per night per room (for a room with 2 beds). If you need to reserve a guest room, please send your order to wuuyang@cis.nctu.edu.tw. Since the room is on the first-come first-serve base, please reserve the room as early as possible.

Abstracts

王凡, 中央研究院 (Farn Wang, Academia Sinica)
Efficient Data-structure for the Verification of Real-Time Systems

Real-time systems usually have simple control structure and represent the next opportunity for the successful application of automatic verification technology. But the current technology of real-time system verification seems falling behind its counterpart of hardware verification. For example, it is now possible to automatically verify a hardware circuit with several hundred transistors. But for real-time system verification, the current technology can only handle systems with tens of Boolean variables.

The popular technology of hardware verification is BDD (Binary Decision Diagram) while the one of real-time system verification is DBM (Difference Bound Matrix). In this talk, we shall compare the two technologies and discuss a new data-structure, called RED (Region-Encoding Diagram) for the fully symbolic model-checking of real-time software systems. RED is a BDD-like structure for the encoding of real-time system state subspaces. It is also a minimal canonical form of such state-spaces. Experiments have been carried out to compare RED with DBM technologies.

Also the first half of the talk will introduce the audience to the research topic of computer-aided verification and symbolic manipulation.

---

黃元欣, 海洋大學 (Yuan-Shin Hwang, National Taiwan Ocean University)
Traversal-Pattern-Sensitive Pointer Analysis

Depending on the information that is gathered by these techniques, pointer analysis can be categorized into the following fields: alias analysis, connection analysis, and shape analysis. Alias analysis is to determine if two pointers, say p and q, are aliased to each other at a program point s, i.e. if they refer to the same location at s. Instead of estimating if two pointers refer to the same location, connection analysis identifies if two pointers point to the same structure. Shape analysis is another form of pointer analysis. It differs from the other two methods by estimating the possible shapes of pointer-linked data structures accessible from pointers.
In order to get safe estimation, for each statement p.f = q that builds a link (e.g. an edge) from p to q, existing techniques have to estimate possible aliases or shapes by following all paths that travel from any pointers to q through edge p.f and then from q to all pointers. The outcome of this approach might be too conservative for programs with cyclic pointer-linked data structures due to the fact that many programs travel along acyclic structures (i.e. traversal patterns) to access all nodes on the cyclic data structures. With the knowledge of traversal patterns, compilers can identify the possible paths that programs will access and then perform pointer analysis on these paths only.
In this talk, I will give a brief survey of techniques for pointer analysis. Furthermore, I will present an approach, called traversal-pattern-sensitive pointer analysis, that can improve pointer analysis by using the information of traversal patterns to narrow down the possible paths that are accessed by programs.

---

猶嘉槐, 中央研究院及加拿大Alberta大學 (Jia-Huai You, Academia Sinica and University of Alberta, Canada)
Nonmonotonic Reasoning as Prioritized Argumentation

Argumentation is a remarkable phenomenon in everyday life. In some case we argue in order to reach a conclusion to guide our actions. In some other cases we argue for the purpose of defeating someone else. In this talk we examine the kind of argumentation that may be constrained by priority constraints, and study its relation with default reasoning. For this purpose, we formalize a simple knowledge representation language where a program consists of a collection of rules and a priority among these rules. We investigate semantical issues of the language, and conclude that default, nonmonotonic reasoning as done in AI is in fact priopritized argumentation.

---

葉慶隆, 大同大學 (Yeh, Ching-Long, Tatung University)
A Logic Programming Approach to Supporting the Entries of XML Documents in an Object Database

We employ the parsing and generation capabilities of the DCG in Prolog to convert XML documents into object definitions to be stored in an object database. The system mainly consists of a DTD parser, a schema generator and a DI parser generator. The DTD parser is used to analyze the structure of DTD. The two generators take the parsing results of the DTD parser, and then produce database schema definitions and the DI parser. The database schema for a DTD is built by executing the generated schema definitions. The DI parser analyzes the document instance and produces the corresponding object definitions. The elements in the document are then stored in the object database by executing the object definition.
At the end of the talk, I will briefly describe an extensible query-by-template interface for retrieving XML documents stored in an object database. The main concern of the method is to design an interface for querying XML documents without worrying about the internal structure and the formal query language.

---

Archive