{"id":{"repo_id":"uiuc","oai_identifier":"oai:www.ideals.illinois.edu:2142/86954"},"canonical_url":"https://search.dev.ndltd.org/etd/uiuc/oai:www.ideals.illinois.edu:2142/86954","repository":{"repo_id":"uiuc","name":"University of Illinois - Urbana-Champaign","base_url":"https://www.ideals.illinois.edu/oai-pmh"},"display":{"title":"Alternating Automata and the Temporal Logic of Ordinals","abstract":"In their 1995 paper, Muller and Schupp define the concept of an alternating automaton, a sort of completion of the notion of a non-deterministic automaton, and show how the notion may be used to prove a number of major results in the theory of automata on infinite inputs in a unified way. In this thesis, we extend the notion of an alternating automaton to accommodate linear inputs of arbitrary ordinal length and then use these automata to prove a number of results about linear propositional temporal logic, a form of modal logic. First, we show that there is a natural interpretation of automaton inputs as structures for the logic and that under this interpretation, alternating automata and temporal logic are equally powerful. We then use this fact to investigate the satisfiability problem for temporal logic. In particular, not only do we look at the question of whether a given formula has a model, but we look at this question when the lengths of models is restricted to a specific ordinal. We show that the temporal logic of an arbitrary (but fixed) ordinal is decidable in exponential time, generalizing the known result that the temporal logic of $\\omega$ is decidable in exponential time. We also look at which classes of ordinals are definable by temporal logic formulas (more precisely, which classes of ordinals result from projecting the class of models of a formula onto their respective lengths), and give a characterization of such classes.","abstract_html":"In their 1995 paper, Muller and Schupp define the concept of an alternating automaton, a sort of completion of the notion of a non-deterministic automaton, and show how the notion may be used to prove a number of major results in the theory of automata on infinite inputs in a unified way. In this thesis, we extend the notion of an alternating automaton to accommodate linear inputs of arbitrary ordinal length and then use these automata to prove a number of results about linear propositional temporal logic, a form of modal logic. First, we show that there is a natural interpretation of automaton inputs as structures for the logic and that under this interpretation, alternating automata and temporal logic are equally powerful. We then use this fact to investigate the satisfiability problem for temporal logic. In particular, not only do we look at the question of whether a given formula has a model, but we look at this question when the lengths of models is restricted to a specific ordinal. We show that the temporal logic of an arbitrary (but fixed) ordinal is decidable in exponential time, generalizing the known result that the temporal logic of <span class=\"etd-inline-math\">&omega;</span> is decidable in exponential time. We also look at which classes of ordinals are definable by temporal logic formulas (more precisely, which classes of ordinals result from projecting the class of models of a formula onto their respective lengths), and give a characterization of such classes.","abstract_has_math":true,"creators":["Rohde, Gareth Scott"],"institution":"University of Illinois at Urbana-Champaign","degree_name":"Ph.D.","degree_level":"Dissertation","degree_discipline":"Mathematics","degree_department":null,"school":null,"contributors":["Schupp, Paul E."],"advisors":[],"committee_chairs":[],"committee_members":[],"year":2015,"date_issued":"2015-09-28T15:20:20Z","date_published":"2015-09-28T15:20:20Z","updated_at":"2026-07-22T22:26:28Z","subjects":["Computer Science"],"languages":["eng"],"rights":[],"rights_urls":[],"identifier_entries":[{"key":"dc:identifier","label":"Identifier","values":["(MiAaPQ)AAI9812757"],"render_values":[{"text":"(MiAaPQ)AAI9812757","href":null,"code":true}]}]},"links":{"outbound_url":"http://hdl.handle.net/2142/86954","outbound_label":"Handle","outbound_source":"dc:identifier"},"metadata_groups":[{"id":"people","label":"People","entries":[{"key":"dc:contributor","label":"Contributor","values":["Schupp, Paul E."]},{"key":"dc:creator","label":"Author","values":["Rohde, Gareth Scott"]}]},{"id":"academic_context","label":"Academic Context","entries":[{"key":"dc:date","label":"Dc Date","values":["2015-09-28T15:20:20Z","10000-01-01","1997"]},{"key":"dc:type","label":"Dc Type","values":["text"]},{"key":"thesis:degree_discipline","label":"Discipline","values":["Mathematics"]},{"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/86954","(MiAaPQ)AAI9812757"]}]},{"id":"additional","label":"Additional Metadata","entries":[{"key":"dc:description","label":"Description","values":["In their 1995 paper, Muller and Schupp define the concept of an alternating automaton, a sort of completion of the notion of a non-deterministic automaton, and show how the notion may be used to prove a number of major results in the theory of automata on infinite inputs in a unified way. In this thesis, we extend the notion of an alternating automaton to accommodate linear inputs of arbitrary ordinal length and then use these automata to prove a number of results about linear propositional temporal logic, a form of modal logic. First, we show that there is a natural interpretation of automaton inputs as structures for the logic and that under this interpretation, alternating automata and temporal logic are equally powerful. We then use this fact to investigate the satisfiability problem for temporal logic. In particular, not only do we look at the question of whether a given formula has a model, but we look at this question when the lengths of models is restricted to a specific ordinal. We show that the temporal logic of an arbitrary (but fixed) ordinal is decidable in exponential time, generalizing the known result that the temporal logic of $\\omega$ is decidable in exponential time. We also look at which classes of ordinals are definable by temporal logic formulas (more precisely, which classes of ordinals result from projecting the class of models of a formula onto their respective lengths), and give a characterization of such classes.","Made available in DSpace on 2015-09-28T15:20:20Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9812757.pdf: 10959129 bytes, checksum: c8d2ba9d5d634ec6fff5e82022e68222 (MD5) Previous issue date: 1997","Embargo set by: Seth Robbins for item 88235 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","267 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1997."]},{"key":"dc:title","label":"Title","values":["Alternating Automata and the Temporal Logic of Ordinals"]}]}],"canonical_facts":{"dc:contributor":["Schupp, Paul E."],"dc:creator":["Rohde, Gareth Scott"],"dc:date":["2015-09-28T15:20:20Z","10000-01-01","1997"],"dc:description":["In their 1995 paper, Muller and Schupp define the concept of an alternating automaton, a sort of completion of the notion of a non-deterministic automaton, and show how the notion may be used to prove a number of major results in the theory of automata on infinite inputs in a unified way. In this thesis, we extend the notion of an alternating automaton to accommodate linear inputs of arbitrary ordinal length and then use these automata to prove a number of results about linear propositional temporal logic, a form of modal logic. First, we show that there is a natural interpretation of automaton inputs as structures for the logic and that under this interpretation, alternating automata and temporal logic are equally powerful. We then use this fact to investigate the satisfiability problem for temporal logic. In particular, not only do we look at the question of whether a given formula has a model, but we look at this question when the lengths of models is restricted to a specific ordinal. We show that the temporal logic of an arbitrary (but fixed) ordinal is decidable in exponential time, generalizing the known result that the temporal logic of $\\omega$ is decidable in exponential time. We also look at which classes of ordinals are definable by temporal logic formulas (more precisely, which classes of ordinals result from projecting the class of models of a formula onto their respective lengths), and give a characterization of such classes.","Made available in DSpace on 2015-09-28T15:20:20Z (GMT). No. of bitstreams: 2 license.txt: 4848 bytes, checksum: 96035ab3f5e1c23cc7138a224ce498bd (MD5) 9812757.pdf: 10959129 bytes, checksum: c8d2ba9d5d634ec6fff5e82022e68222 (MD5) Previous issue date: 1997","Embargo set by: Seth Robbins for item 88235 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","267 p.","Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1997."],"dc:identifier":["http://hdl.handle.net/2142/86954","(MiAaPQ)AAI9812757"],"dc:language":["eng"],"dc:subject":["Computer Science"],"dc:title":["Alternating Automata and the Temporal Logic of Ordinals"],"dc:type":["text"],"thesis:degree_discipline":["Mathematics"],"thesis:degree_level":["Dissertation"],"thesis:degree_name":["Ph.D."],"thesis:institution_name":["University of Illinois at Urbana-Champaign"]},"updated_at":"2026-07-22T22:26:28Z"}