Fixpoint logic vs. infinitary logic in finite-model theory

The relationship between fixpoint logic and the infinitary logic L/sub infinity omega //sup omega / with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L/sub infinity omega //sup omega / is expressible in fixpoint logic. As a fir...

Full description

Saved in:
Bibliographic Details
Main Authors: Kolaitis, P.G., Vardi, M.Y.
Format: Conference Proceeding
Language:English
Subjects:
Application software
Combinatorial mathematics
Complexity theory
Computer science
Game theory
Logic
Power generation
Spatial databases
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 57
container_issue
container_start_page 46
container_title
container_volume
creator Kolaitis, P.G.
Vardi, M.Y.
description The relationship between fixpoint logic and the infinitary logic L/sub infinity omega //sup omega / with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L/sub infinity omega //sup omega / is expressible in fixpoint logic. As a first application of this, a normal-form theorem for L infinity /sub omega //sup omega / on finite structures is obtained. The relative expressive power of first-order logic, fixpoint logic, and L/sub infinity omega //sup omega / on arbitrary classes of finite structures is examined. A characterization of when L/sub infinity omega //sup omega / collapses to first-order logic on an arbitrary class of finite structures is given.< >
doi_str_mv 10.1109/LICS.1992.185518
format conference_proceeding
fullrecord <record><control><sourceid>proquest_6IE</sourceid><recordid>TN_cdi_proquest_miscellaneous_25649197</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>185518</ieee_id><sourcerecordid>25649197</sourcerecordid><originalsourceid>FETCH-LOGICAL-i245t-f14ac5510c615e920b6e2d510b07b4bb5a10ef43a4d42d6f118422e655f2af303</originalsourceid><addsrcrecordid>eNotkEFLxDAQhQMiqOvexVNP3lozaZIm3qS460LBw67nkrYTjbRNbbri_nuL3XcZ3uNjmHmE3AFNAKh-LHb5PgGtWQJKCFAX5IYqUJJlqWBXZB3CF50lhOKaXpOnjfsdvOunqPUfro5-QhK53rreTWY8nUPXR_8Jxp1vsI2mT_Tj6ZZcWtMGXJ_nirxvXg75a1y8bXf5cxE7xsUUW-Cmni-htQSBmtFKImtmX9Gs4lUlDFC0PDW84ayRFkBxxlAKYZmxKU1X5GHZO4z--4hhKjsXamxb06M_hpIJyTXobAbvF9AhYjmMrptfKJca0j-hFFH-</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype><pqid>25649197</pqid></control><display><type>conference_proceeding</type><title>Fixpoint logic vs. infinitary logic in finite-model theory</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Kolaitis, P.G. ; Vardi, M.Y.</creator><creatorcontrib>Kolaitis, P.G. ; Vardi, M.Y.</creatorcontrib><description>The relationship between fixpoint logic and the infinitary logic L/sub infinity omega //sup omega / with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L/sub infinity omega //sup omega / is expressible in fixpoint logic. As a first application of this, a normal-form theorem for L infinity /sub omega //sup omega / on finite structures is obtained. The relative expressive power of first-order logic, fixpoint logic, and L/sub infinity omega //sup omega / on arbitrary classes of finite structures is examined. A characterization of when L/sub infinity omega //sup omega / collapses to first-order logic on an arbitrary class of finite structures is given.&lt; &gt;</description><identifier>ISBN: 0818627352</identifier><identifier>ISBN: 9780818627354</identifier><identifier>DOI: 10.1109/LICS.1992.185518</identifier><language>eng</language><publisher>IEEE Comput. Soc. Press</publisher><subject>Application software ; Combinatorial mathematics ; Complexity theory ; Computer science ; Game theory ; Logic ; Power generation ; Spatial databases</subject><ispartof>Logic in Computer Science, 7th Conference (LICS '92), 1992, p.46-57</ispartof><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/185518$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,314,780,784,789,790,2056,27923,27924,54919</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/185518$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Kolaitis, P.G.</creatorcontrib><creatorcontrib>Vardi, M.Y.</creatorcontrib><title>Fixpoint logic vs. infinitary logic in finite-model theory</title><title>Logic in Computer Science, 7th Conference (LICS '92)</title><addtitle>LICS</addtitle><description>The relationship between fixpoint logic and the infinitary logic L/sub infinity omega //sup omega / with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L/sub infinity omega //sup omega / is expressible in fixpoint logic. As a first application of this, a normal-form theorem for L infinity /sub omega //sup omega / on finite structures is obtained. The relative expressive power of first-order logic, fixpoint logic, and L/sub infinity omega //sup omega / on arbitrary classes of finite structures is examined. A characterization of when L/sub infinity omega //sup omega / collapses to first-order logic on an arbitrary class of finite structures is given.&lt; &gt;</description><subject>Application software</subject><subject>Combinatorial mathematics</subject><subject>Complexity theory</subject><subject>Computer science</subject><subject>Game theory</subject><subject>Logic</subject><subject>Power generation</subject><subject>Spatial databases</subject><isbn>0818627352</isbn><isbn>9780818627354</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>1992</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNotkEFLxDAQhQMiqOvexVNP3lozaZIm3qS460LBw67nkrYTjbRNbbri_nuL3XcZ3uNjmHmE3AFNAKh-LHb5PgGtWQJKCFAX5IYqUJJlqWBXZB3CF50lhOKaXpOnjfsdvOunqPUfro5-QhK53rreTWY8nUPXR_8Jxp1vsI2mT_Tj6ZZcWtMGXJ_nirxvXg75a1y8bXf5cxE7xsUUW-Cmni-htQSBmtFKImtmX9Gs4lUlDFC0PDW84ayRFkBxxlAKYZmxKU1X5GHZO4z--4hhKjsXamxb06M_hpIJyTXobAbvF9AhYjmMrptfKJca0j-hFFH-</recordid><startdate>19920101</startdate><enddate>19920101</enddate><creator>Kolaitis, P.G.</creator><creator>Vardi, M.Y.</creator><general>IEEE Comput. Soc. Press</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>19920101</creationdate><title>Fixpoint logic vs. infinitary logic in finite-model theory</title><author>Kolaitis, P.G. ; Vardi, M.Y.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-i245t-f14ac5510c615e920b6e2d510b07b4bb5a10ef43a4d42d6f118422e655f2af303</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>1992</creationdate><topic>Application software</topic><topic>Combinatorial mathematics</topic><topic>Complexity theory</topic><topic>Computer science</topic><topic>Game theory</topic><topic>Logic</topic><topic>Power generation</topic><topic>Spatial databases</topic><toplevel>online_resources</toplevel><creatorcontrib>Kolaitis, P.G.</creatorcontrib><creatorcontrib>Vardi, M.Y.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE Xplore</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Kolaitis, P.G.</au><au>Vardi, M.Y.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>Fixpoint logic vs. infinitary logic in finite-model theory</atitle><btitle>Logic in Computer Science, 7th Conference (LICS '92)</btitle><stitle>LICS</stitle><date>1992-01-01</date><risdate>1992</risdate><spage>46</spage><epage>57</epage><pages>46-57</pages><isbn>0818627352</isbn><isbn>9780818627354</isbn><abstract>The relationship between fixpoint logic and the infinitary logic L/sub infinity omega //sup omega / with a finite number of variables is studied. It is observed that the equivalence of two finite structures with respect to L/sub infinity omega //sup omega / is expressible in fixpoint logic. As a first application of this, a normal-form theorem for L infinity /sub omega //sup omega / on finite structures is obtained. The relative expressive power of first-order logic, fixpoint logic, and L/sub infinity omega //sup omega / on arbitrary classes of finite structures is examined. A characterization of when L/sub infinity omega //sup omega / collapses to first-order logic on an arbitrary class of finite structures is given.&lt; &gt;</abstract><pub>IEEE Comput. Soc. Press</pub><doi>10.1109/LICS.1992.185518</doi><tpages>12</tpages><oa>free_for_read</oa></addata></record>
fulltext fulltext_linktorsrc
identifier ISBN: 0818627352
ispartof Logic in Computer Science, 7th Conference (LICS '92), 1992, p.46-57
issn
language eng
recordid cdi_proquest_miscellaneous_25649197
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Application software
Combinatorial mathematics
Complexity theory
Computer science
Game theory
Logic
Power generation
Spatial databases
title Fixpoint logic vs. infinitary logic in finite-model theory
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-12T02%3A55%3A07IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=Fixpoint%20logic%20vs.%20infinitary%20logic%20in%20finite-model%20theory&rft.btitle=Logic%20in%20Computer%20Science,%207th%20Conference%20(LICS%20'92)&rft.au=Kolaitis,%20P.G.&rft.date=1992-01-01&rft.spage=46&rft.epage=57&rft.pages=46-57&rft.isbn=0818627352&rft.isbn_list=9780818627354&rft_id=info:doi/10.1109/LICS.1992.185518&rft_dat=%3Cproquest_6IE%3E25649197%3C/proquest_6IE%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-i245t-f14ac5510c615e920b6e2d510b07b4bb5a10ef43a4d42d6f118422e655f2af303%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=25649197&rft_id=info:pmid/&rft_ieee_id=185518&rfr_iscdi=true