Programming using automata and transducers / Loris D'Antoni.

Format:

Book

Manuscript

Thesis/Dissertation

Author/Creator:

D'Antoni, Loris, author.

Contributor:

Alur, Rajeev, 1966- degree supervisor.

Kannan, Sampath, degree committee member.

Pierce, Benjamin C., degree committee member.

Tannen, Val, 1953- degree committee member.

Veanes, Margus, degree committee member.

University of Pennsylvania. Department of Computer and Information Science.

Language:

English

Subjects (All):

Penn dissertations--Computer and information science.

Computer and information science--Penn dissertations.

Local Subjects:

Penn dissertations--Computer and information science.

Computer and information science--Penn dissertations.

Physical Description:

xiv, 199 leaves : illustrations ; 29 cm

Production:

[Philadelphia, Pennsylvania] : University of Pennsylvania, 2015.

Summary:

Automata, the simplest model of computation, have proven to be an effective tool in reasoning about programs that operate over strings. Transducers augment automata to produce outputs and have been used to model string and tree transformations such as natural language translations. The success of these models is primarily due to their closure properties and decidable procedures, but good properties come at the price of limited expressiveness. Concretely, most models only support finite alphabets and can only represent small classes of languages and transformations. We focus on addressing these limitations and bridge the gap between the theory of automata and transducers and complex real-world applications: Can we extend automata and transducer models to operate over structured and infinite alphabets? Can we design languages that hide the complexity of these formalisms? Can we define executable models that can process the input efficiently?

First, we introduce succinct models of transducers that can operate over large alphabets and design BEX, a language for analysing string coders. We use BEX to prove the correctness of UTF and B ASE64 encoders and decoders. Next, we develop a theory of tree transducers over infinite alphabets and design FAST, a language for analysing tree-manipulating programs. We use FAST to detect vulnerabilities in HTML sanitizers, check whether augmented reality taggers conflict, and optimize and analyze functional programs that operate over lists and trees. Finally, we focus on laying the foundations of stream processing of hierarchical data such as XML files and program traces. We introduce two new efficient and executable models that can process the input in a left-to-right linear pass: symbolic visibly pushdown automata and streaming tree transducers. Symbolic visibly pushdown automata are closed under Boolean operations and can specify and efficiently monitor complex properties for hierarchical structures over infinite alphabets. Streaming tree transducers can express and efficiently process complex XML transformations while enjoying decidable procedures.

Notes:

Ph. D. University of Pennsylvania 2015.

Department: Computer and Information Science.

Supervisor: Rajeev Alur.

Includes bibliographical references.

OCLC:

945583642