Meeting Agenda
Meeting AgendaIn this talk I will show that the latter two models are equivalent. More precisely, automata with k pointers that can be compared are equivalent with respect to language recognition to automata that mark at most k positions. I will also describe other related simulation techniques.
Some of these results will be presented at the conference ``Fundamentals of Computation Theory'' in Krakow later this year.
ABSTRACT
The ATM switching scheme we propose in this talk provides isochronous service with multiple frame sizes, and is obtained by making a small change to the well-known Stop-and-Go scheme proposed by Golestani. Let F= {f_1, f_2, ..., f_K} be a set of frame sizes. Let a virtual channel c send n^c cells in each frame of length f^c in F. In any scheme, in order to avoid congestion, the link capacity constraint, sum_{c in L} n^c/f^c <= 1, must be satisfied for every link, where L is the set of all virtual channels traversing a given link. Our scheme is very similar to Stop-and-Go, except that we use the EDF (earliest-deadlines-first) scheduler, instead of the rate-monotonic static-priority scheduler. As a result, our scheme works as long as the above capacity constraints are satisfied, while Stop-and-Go cannot make a full utilization of the link bandwidth. Moreover, our scheme does not require that the frames of the same period be synchronized. The EDF scheduling is, in general, more complex than static-priority scheduling. However, we show that the next earliest deadline needs to be computed only when an output frame reaches its end, i.e., not whenever a cell is output, resulting in significant saving in computation time. We also introduce a new concept, called periodic clustered arrivals, and present a regulator design which transforms arriving cells into such arrivals.
Invited by Dr. George Kesidis, Department of Electrical and Computer Engineering
By applying database technologies to embedded control applications such as telephony software, a control program can be made physically data independent by specifying access and update of control data in a declarative query language such as OQL. In such a memory-resident and real-time environment, the generated access plans must avoid the use of temporary storage for arbitrarily sized intermediate results and the use of expensive operations such as sorting. Also, to enable increment use on legacy control software, the generated plans must be able to navigate existing data structures.
This thesis presents an optimization approach for such applications by using existential query graphs (EQG)-a refinement of Peirce's existential graphs. An EQG is expressive enough to directly capture an extended class of conjunctive queries, as well as access plans that encode strategies for query evaluation.
To simplify the mapping from an OQL query to an EQG, a canonical form has been introduced. The mapping algorithms are then discussed. A join order selection procedure that incrementally refines a pair of EQGs, namely, a query graph and a plan graph, is also presented. The former graph captures what is necessarily true of the query, while the latter encodes an access plan for the query. Differential analysis of the two graphs distinguish query conditions that require special checks in access plans from constraints that are defined in the schema.
The expansion of the new features in telephony service has uncovered many unsuspected problems. This thesis addresses on detection feature interactions at the requirement phase. A feature provides added functionality to an existing service in the telecommunication system. Feature interaction occurs when the behavior of an existing feature is changed by the presence of a new feature.
This thesis presents an approach for detecting feature interactions by assertion analysis. Assertions are property facts and assumptions about the telephony system that the feature expects to hold. Each telephony service and feature is modeled by a state-transition- machine in our approach. A formal tabular notation is used to specify services and features individually. Specifications of feature assertions are developed in terms of sets and relations. Assertion analysis is based on composing the feature specifications automatically during reachability analysis, and interactions are detected at reachable states during the composition. Evaluation are presented with respect to a benchmark paper published by the Bellcore.