Dissertation/Thesis Abstract

On labeled paths
by Wiegand, Nathan Michael, Ph.D., The University of Alabama, 2010, 96; 3409129
Abstract (Summary)

Labeled graph theory is the marriage of two common problem domains to computer science—graph theory and automata theory. Though each has been independently studied in depth, there has been little investigation of their intersection, the labeled paths.

This dissertation examines three results in the area of labeled path problems. The first result presents an empirical analysis of two context-free labeled all-pairs shortest-path algorithms using MapReduce as the experimental platform. The second and third results examine labeled paths in the context of formal languages beyond the context free languages. The second result is a lower bound on the length of the longest shortest path when the formal language constraining the path is a member of the control language hierarchy. Finally, the third result presents a labeled all-pairs shortest-path algorithm for each level of the infinite KLinear-Hierarchy.

Indexing (document details)
Advisor: Borie, Richard B.
Commitee: Bradford, Phillip G., Dixon, Brandon, Lusth, John, Neggers, Joseph
School: The University of Alabama
Department: Computer Science
School Location: United States -- Alabama
Source: DAI-B 71/07, Dissertation Abstracts International
Subjects: Computer science
Keywords: Algorithms, Control language hierarchy, Formal languages, Graph theory, Labeled graphs
Publication Number: 3409129
ISBN: 978-1-124-06191-7
Copyright © 2020 ProQuest LLC. All rights reserved. Terms and Conditions Privacy Policy Cookie Policy