Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


SJWDALGLISH Math Masters Thesis.pdf (371.73 KB)

ETD Abstract Container

Abstract Header

Least and Inflationary Fixed-Point Logics: A Comparison of Expressive Strength

Dalglish, Steven Jack William
http://orcid.org/0000-0002-2068-7968
http://rave.ohiolink.edu/etdc/view?acc_num=osu1597163479372308

Abstract Details

2020, Master of Science, Ohio State University, Mathematics.
Fixed-point logics arise from languages that contain fixed-point operators, which allow us to identify the smallest class inductively defined by a formula without using full second-order logic. There are two fixed-point operators most commonly studied: the least fixed-point operator and the inflationary fixed-point operator. The logics become particularly complicated when we allow for the operators to be iterated. The question naturally arises as to which operator is expressively stronger: which operator allows us to define more sets? This paper proves the expressive equivalence of the least and inflationary fixed-point operators when they are added to a first-order logic and proves that they are expressively inequivalent when they are added to a propositional modal logic. This clarifies the semantic contribution that such operators make to different fixed-point logics and demonstrates the importance of the underlying logic in answering this question.
Chris Miller (Advisor)
Tim Carlson (Committee Member)
52 p.
Mathematics
fixed-point logic; least fixed-point logic; inflationary fixed-point logic

Recommended Citations

Citations

  • Dalglish, S. J. W. (2020). Least and Inflationary Fixed-Point Logics: A Comparison of Expressive Strength [Master's thesis, Ohio State University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=osu1597163479372308

    APA Style (7th edition)

  • Dalglish, Steven. Least and Inflationary Fixed-Point Logics: A Comparison of Expressive Strength. 2020. Ohio State University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=osu1597163479372308.

    MLA Style (8th edition)

  • Dalglish, Steven. "Least and Inflationary Fixed-Point Logics: A Comparison of Expressive Strength." Master's thesis, Ohio State University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=osu1597163479372308

    Chicago Manual of Style (17th edition)

osu1597163479372308
91
© 2020, all rights reserved.
This open access ETD is published by The Ohio State University and OhioLINK.