Speaker: Karl Lieberherr, Northeastern University, CCIS, Boston
Abstract:
Abbreviating paths with iterated wild cards is an abstraction mechanism common to Adaptive Programming (AP), eXtensible Markup Language (XML) document processing, and Aspect-Oriented Programming (AOP). Recognition of abbreviated paths is used for navigation in both AP and XML, and to decide upon advice execution in AOP. Finite state automata have been used for efficient recognition of abbreviated paths.
Iterated wild cards pose two problems: the semantic problem of ambiguity and an efficiency problem when traversals are naively guided by a navigation specification that contains iterated wild cards. We solve the ambiguity problem using a better kind of wild card interpretation, called WYSIWYG, which also improves the modularity of programs. For solving the efficiency problem, we introduce cover automata for abbreviated path recognition. Cover automata have significantly lower state complexity than automata used in previous approaches. The first contribution of this paper is an algorithm for constructing a cover automaton for abbreviated path recognition. We prove the correctness of our algorithm. A second contribution is a succinct formal semantics for abbreviated paths based on regular language theory which has greatly simplified our proofs. A third contribution is a new construction which subsumes the traversal graph construction in [TOPLAS04]: it is simpler, more efficient and derived systematically from a characterization of the traversal using regular language closure properties.
Joint work with Ahmed Abdelmeged, Therapon Skotiniotis, Mitchell Wand and Pete Manolios.
TOPLAS04: Karl Lieberherr and Boaz Patt-Shamir and Doug Orleans, Traversals of object structures: Specification and Efficient Implementation, ACM Trans. Program. Lang. Syst., 26(2), 2004.