{"id":{"repo_id":"alabama","oai_identifier":"oai:ir.ua.edu:123456789/764"},"canonical_url":"https://search.dev.ndltd.org/etd/alabama/oai:ir.ua.edu:123456789/764","repository":{"repo_id":"alabama","name":"University of Alabama","base_url":"https://ir-api.ua.edu/oai/request"},"display":{"title":"On labeled paths","abstract":"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.","abstract_html":"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.","abstract_has_math":false,"creators":["Wiegand, Nathan"],"institution":"University of Alabama Libraries","degree_name":null,"degree_level":null,"degree_discipline":null,"degree_department":null,"school":null,"contributors":["Bradford, Phillip G.","Lusth, John C.","Dixon, Brandon","Neggers, Joseph"],"advisors":["Borie, Richard B."],"committee_chairs":[],"committee_members":[],"year":2010,"date_issued":"2010","date_published":"2010","updated_at":"2026-07-27T18:44:25Z","subjects":["Computer science"],"languages":["en_US","English"],"rights":["All rights reserved by the author unless otherwise indicated."],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["u0015_0000001_0000258","Wiegand_alatus_0004D_10311"],"render_values":[{"text":"u0015_0000001_0000258","href":null,"code":true},{"text":"Wiegand_alatus_0004D_10311","href":null,"code":true}]}]},"links":{"outbound_url":"https://ir.ua.edu/handle/123456789/764","outbound_label":"Repository record","outbound_source":"dc:identifier.uri"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Bradford, Phillip G.","Lusth, John C.","Dixon, Brandon","Neggers, Joseph"]},{"key":"dc:contributor.advisor","label":"Advisor","values":["Borie, Richard B."]},{"key":"dc:contributor.other","label":"Dc Contributor Other","values":["University of Alabama Tuscaloosa"]},{"key":"dc:creator","label":"Author","values":["Wiegand, Nathan"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date.accessioned","label":"Dc Date Accessioned","values":["2017-02-28T22:25:45Z"]},{"key":"dc:date.available","label":"Dc Date Available","values":["2017-02-28T22:25:45Z"]},{"key":"dc:date.issued","label":"Date","values":["2010"]},{"key":"dc:publisher","label":"Institution","values":["University of Alabama Libraries"]},{"key":"dc:type","label":"Dc Type","values":["thesis","text"]}]},{"id":"subjects_keywords","label":"Subjects and Keywords","entries":[{"key":"dc:subject","label":"Dc Subject","values":["Computer science"]}]},{"id":"language_rights","label":"Language and Rights","entries":[{"key":"dc:language","label":"Dc Language","values":["English"]},{"key":"dc:language.iso","label":"Language (ISO)","values":["en_US"]},{"key":"dc:rights","label":"Dc Rights","values":["All rights reserved by the author unless otherwise indicated."]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier.other","label":"Dc Identifier Other","values":["u0015_0000001_0000258","Wiegand_alatus_0004D_10311"]},{"key":"dc:identifier.uri","label":"Identifier URI","values":["https://ir.ua.edu/handle/123456789/764"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["Electronic Thesis or Dissertation"]},{"key":"dc:description.abstract","label":"Abstract","values":["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."]},{"key":"dc:format.medium","label":"Dc Format Medium","values":["electronic"]},{"key":"dc:format.mimetype","label":"Dc Format Mimetype","values":["application/pdf"]},{"key":"dc:title","label":"Title","values":["On labeled paths"]}]}],"canonical_facts":{"dc:contributor":["Bradford, Phillip G.","Lusth, John C.","Dixon, Brandon","Neggers, Joseph"],"dc:contributor.advisor":["Borie, Richard B."],"dc:contributor.other":["University of Alabama Tuscaloosa"],"dc:creator":["Wiegand, Nathan"],"dc:date.accessioned":["2017-02-28T22:25:45Z"],"dc:date.available":["2017-02-28T22:25:45Z"],"dc:date.issued":["2010"],"dc:description":["Electronic Thesis or Dissertation"],"dc:description.abstract":["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."],"dc:format.medium":["electronic"],"dc:format.mimetype":["application/pdf"],"dc:identifier.other":["u0015_0000001_0000258","Wiegand_alatus_0004D_10311"],"dc:identifier.uri":["https://ir.ua.edu/handle/123456789/764"],"dc:language":["English"],"dc:language.iso":["en_US"],"dc:publisher":["University of Alabama Libraries"],"dc:rights":["All rights reserved by the author unless otherwise indicated."],"dc:subject":["Computer science"],"dc:title":["On labeled paths"],"dc:type":["thesis","text"]},"updated_at":"2026-07-27T18:44:25Z"}