On labeled paths

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 K Linear-Hierarchy.

Grantor dc:publisher

University of Alabama Libraries

Year dc:date.issued

2010

Author dc:creator

• Wiegand, Nathan

Advisor dc:contributor.advisor

• Borie, Richard B.

Contributors dc:contributor

• Bradford, Phillip G.
• Lusth, John C.
• Dixon, Brandon
• Neggers, Joseph

• Computer science

Statement dc:rights

• All rights reserved by the author unless otherwise indicated.

Language dc:language.iso

en_US, English

Dc Identifier Other

u0015_0000001_0000258
Wiegand_alatus_0004D_10311

OAI identifier oai:identifier

oai:ir.ua.edu:123456789/764