| Termination of String Rewriting Rules that have One Pair of Overlaps |
OCT 2002 |
16 pages |
| Authors:
Alfons Geser; INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
|
 | This paper presents a partial solution to the long standing open problem of termination of one-rule string rewriting. Overlaps between the two sides of the rule play a central rule in existing termination criteria. We characterize termination of all one-rule string rewriting systems that have one such overlap at either end. This both completes a result of Kurth and generalizes a result of Shikishima-Tsuji et al. |
|
| Air Traffic Conflict Resolution and Recovery |
MAY 2002 |
24 pages |
| Authors:
Alfons Geser; Cesar Munoz; Gilles Dowek; Florent Kirchner; INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
|
| An essential element in the Free Flight concept is the detection and avoidance of air traffic conflicts. A conflict occurs when the required separation between two aircraft, namely the ownership and the intruder, is lost. Conflict detection and resolution systems predict loss of separation and output conflict avoidance maneuvers that divert the ownership from its original trajectory. In this paper, we address the problem of redirecting the ownership to its ... |
|
| Loops of Superexponential Lengths in One-rule String Rewriting |
FEB 2002 |
16 pages |
| Authors:
Alfons Geser; INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
|
| Loops are the most frequent cause of non-termination in string rewriting. In the general case, non-terminating, non-looping string rewriting systems exist, and the uniform termination problem is undecidable. For rewriting with only one string rewriting rule, it is unknown whether non-terminating, non- looping systems exist and whether uniform termination is decidable. If in the one-rule case, non-termination is equivalent to the existence of loops, as McNaughton conjectures, then a decision ... |
|
| Tactical Conflict Detection and Resolution in a 3-D Airspace |
APR 2001 |
17 pages |
| Authors:
Gilles Dowek; Cesar Munoz; Alfons Geser; INSTITUTE FOR COMPUTER APPLICATIONS IN SCIENCE AND ENGINEERING HAMPTON VA
|
| This paper presents an algorithm for detection and resolution of air traffic conflicts in a 3- dimensional (3-D) airspace for two aircraft, namely ownship and intruder. A conflict is a projected incursion of the intruder aircraft within the protected zone of the ownship. A solution is a single maneuver, to be performed by the ownship, that effectively keeps the required minimum separation without cooperation of the intruder aircraft. The input ... |
|
Reports by Author
