{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/81681"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/81681","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Solution of Large Markov Models Using Lumping Techniques and Symbolic Data Structures","abstract":"In particular, we have developed the fastest known CTMC lumping algorithm with the running time of O (m log n), where n and m are the number of states and non-zero entries of the generator matrix of the CTMC, respectively. We have also combined the use of symbolic data structures with state-lumping techniques to develop an efficient symbolic state-space exploration algorithm for state-sharing composed models that exploits lumpings that are due to equally behaving components. Finally, we have developed a new compositional algorithm that lumps CTMCs represented as MDs. Unlike other compositional lumping algorithms, our algorithm does not require any knowledge of the modeling formalisms from which the MDs were generated. Our approach relies on local conditions, i.e., conditions on individual nodes of the MD.","abstract_html":"In particular, we have developed the fastest known CTMC lumping algorithm with the running time of O (m log n), where n and m are the number of states and non-zero entries of the generator matrix of the CTMC, respectively. We have also combined the use of symbolic data structures with state-lumping techniques to develop an efficient symbolic state-space exploration algorithm for state-sharing composed models that exploits lumpings that are due to equally behaving components. Finally, we have developed a new compositional algorithm that lumps CTMCs represented as MDs. Unlike other compositional lumping algorithms, our algorithm does not require any knowledge of the modeling formalisms from which the MDs were generated. Our approach relies on local conditions, i.e., conditions on individual nodes of the MD.","abstract_has_math":false,"creators":["Derisavi, Salem"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Computer Science","degree_department":null,"school":null,"contributors":["Sanders, William H."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-25T20:19:59Z","date_published":"2015-09-25T20:19:59Z","updated_at":"2026-07-22T22:26:16Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI3198968"],"render_values":[{"text":"(MiAaPQ)AAI3198968","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/81681","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Sanders, William H."]},{"key":"dc:creator","label":"Author","values":["Derisavi, Salem"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-25T20:19:59Z","10000-01-01","2005"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Computer Science"]},{"key":"thesis:degree_level","label":"Degree Level","values":["Dissertation"]},{"key":"thesis:degree_name","label":"Degree Name","values":["Ph.D."]},{"key":"thesis:institution_name","label":"Thesis Institution Name","values":["University of Illinois at Urbana-Champaign"]}]},{"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":["eng"]}]},{"id":"identifiers","label":"Identifiers","entries":[{"key":"dc:identifier","label":"Identifier","values":["http://hdl.handle.net/2142/81681","(MiAaPQ)AAI3198968"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In particular, we have developed the fastest known CTMC lumping algorithm with the running time of O (m log n), where n and m are the number of states and non-zero entries of the generator matrix of the CTMC, respectively. We have also combined the use of symbolic data structures with state-lumping techniques to develop an efficient symbolic state-space exploration algorithm for state-sharing composed models that exploits lumpings that are due to equally behaving components. Finally, we have developed a new compositional algorithm that lumps CTMCs represented as MDs. Unlike other compositional lumping algorithms, our algorithm does not require any knowledge of the modeling formalisms from which the MDs were generated. Our approach relies on local conditions, i.e., conditions on individual nodes of the MD.","Made available in DSpace on 2015-09-25T20:19:59Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3198968.pdf: 4444528 bytes, checksum: 4b0971b3295d6f20505f09d83351ce27 (MD5) Previous issue date: 2005","Embargo set by: Seth Robbins for item 82962 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","158 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2005."]},{"key":"dc:title","label":"Title","values":["Solution of Large Markov Models Using Lumping Techniques and Symbolic Data Structures"]}]}],"canonical_facts":{"dc:contributor":["Sanders, William H."],"dc:creator":["Derisavi, Salem"],"dc:date":["2015-09-25T20:19:59Z","10000-01-01","2005"],"dc:description":["In particular, we have developed the fastest known CTMC lumping algorithm with the running time of O (m log n), where n and m are the number of states and non-zero entries of the generator matrix of the CTMC, respectively. We have also combined the use of symbolic data structures with state-lumping techniques to develop an efficient symbolic state-space exploration algorithm for state-sharing composed models that exploits lumpings that are due to equally behaving components. Finally, we have developed a new compositional algorithm that lumps CTMCs represented as MDs. Unlike other compositional lumping algorithms, our algorithm does not require any knowledge of the modeling formalisms from which the MDs were generated. Our approach relies on local conditions, i.e., conditions on individual nodes of the MD.","Made available in DSpace on 2015-09-25T20:19:59Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 3198968.pdf: 4444528 bytes, checksum: 4b0971b3295d6f20505f09d83351ce27 (MD5) Previous issue date: 2005","Embargo set by: Seth Robbins for item 82962 Lift date: Forever Reason: Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","Restricted to the U of I community idenfinitely during batch ingest of legacy ETDs","U of I Only","158 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 2005."],"dc:identifier":["http://hdl.handle.net/2142/81681","(MiAaPQ)AAI3198968"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Solution of Large Markov Models Using Lumping Techniques and Symbolic Data Structures"],"dc:type":["text"],"thesis:degree_discipline":["Computer Science"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:16Z"}