AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS

We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability in monadic second-order (MSO) logic. We also provide three logical applications. First, we establish the first known col...

Full description

Saved in:
Bibliographic Details
Published in:The Journal of symbolic logic 2018-09, Vol.83 (3), p.1147-1189
Main Authors: CARTON, OLIVIER, COLCOMBET, THOMAS, PUPPIS, GABRIELE
Format: Article
Language:English
Subjects:
Computer Science
Formal Languages and Automata Theory
Logic
Logic in Computer Science
Mathematics
Philosophy
Realism
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c351t-7ce20ae325642acc4d2694f1c41a2928891d1b9acdbbc190a935080a2b7da2be3
cites cdi_FETCH-LOGICAL-c351t-7ce20ae325642acc4d2694f1c41a2928891d1b9acdbbc190a935080a2b7da2be3
container_end_page 1189
container_issue 3
container_start_page 1147
container_title The Journal of symbolic logic
container_volume 83
creator CARTON, OLIVIER
COLCOMBET, THOMAS
PUPPIS, GABRIELE
description We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability in monadic second-order (MSO) logic. We also provide three logical applications. First, we establish the first known collapse result for the quantifier alternation of MSO logic over countable linear orderings. Second, we solve an open problem posed by Gurevich and Rabinovich, concerning the MSO-definability of sets of rational numbers using the reals in the background. Third, we establish the MSO-definability of the set of yields induced by an MSO-definable set of trees, confirming a conjecture posed by Bruyère, Carton, and Sénizergues.
doi_str_mv 10.1017/jsl.2018.7
format article
fullrecord <record><control><sourceid>jstor_hal_p</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_01470325v2</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><jstor_id>26600366</jstor_id><sourcerecordid>26600366</sourcerecordid><originalsourceid>FETCH-LOGICAL-c351t-7ce20ae325642acc4d2694f1c41a2928891d1b9acdbbc190a935080a2b7da2be3</originalsourceid><addsrcrecordid>eNo90E1rg0AQBuCltNA07aX3gtBTC6azH-rucWOMEawGYw49LetqaCStrSaF_vsqllxmYHh4GV6E7jHMMGDvpe4OMwKYz7wLNMGCUdvh3L1EEwBCbMYxuUY3XVcDgCMYn6BQJpaMw2Ceyci35HqdpdJfWXlqvW5SexEso0TOozjK36w0sfx0m-RyHgdWHCWBzKw0WwRZlISbW3S104euuvvfU7RdBrm_suM0jHwZ24Y6-Gh7piKgK0oclxFtDCuJK9gOG4Y1EYRzgUtcCG3KojBYgBbUAQ6aFF7Zj4pO0dOY-64P6qvdf-j2VzV6r1YyVsMNMPOgz_8hvX0c7VfbfJ-q7qjq5tR-9u8p4nGPgsOI16vnUZm26bq22p1jMaihVNWXqoZS1YAfRlx3x6Y9S-K6ANR16R9fwGsK</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2787305427</pqid></control><display><type>article</type><title>AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS</title><source>JSTOR Archival Journals and Primary Sources Collection</source><source>Cambridge University Press</source><creator>CARTON, OLIVIER ; COLCOMBET, THOMAS ; PUPPIS, GABRIELE</creator><creatorcontrib>CARTON, OLIVIER ; COLCOMBET, THOMAS ; PUPPIS, GABRIELE</creatorcontrib><description>We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability in monadic second-order (MSO) logic. We also provide three logical applications. First, we establish the first known collapse result for the quantifier alternation of MSO logic over countable linear orderings. Second, we solve an open problem posed by Gurevich and Rabinovich, concerning the MSO-definability of sets of rational numbers using the reals in the background. Third, we establish the MSO-definability of the set of yields induced by an MSO-definable set of trees, confirming a conjecture posed by Bruyère, Carton, and Sénizergues.</description><identifier>ISSN: 0022-4812</identifier><identifier>EISSN: 1943-5886</identifier><identifier>DOI: 10.1017/jsl.2018.7</identifier><language>eng</language><publisher>Pasadena: Association for Symbolic Logic, Inc</publisher><subject>Computer Science ; Formal Languages and Automata Theory ; Logic ; Logic in Computer Science ; Mathematics ; Philosophy ; Realism</subject><ispartof>The Journal of symbolic logic, 2018-09, Vol.83 (3), p.1147-1189</ispartof><rights>2018, Association for Symbolic Logic</rights><rights>Copyright © The Association for Symbolic Logic 2018</rights><rights>Attribution</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c351t-7ce20ae325642acc4d2694f1c41a2928891d1b9acdbbc190a935080a2b7da2be3</citedby><cites>FETCH-LOGICAL-c351t-7ce20ae325642acc4d2694f1c41a2928891d1b9acdbbc190a935080a2b7da2be3</cites><orcidid>0000-0002-2728-6534 ; 0000-0001-9831-3264 ; 0000-0001-6529-6963</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://www.jstor.org/stable/pdf/26600366$$EPDF$$P50$$Gjstor$$H</linktopdf><linktohtml>$$Uhttps://www.jstor.org/stable/26600366$$EHTML$$P50$$Gjstor$$H</linktohtml><link.rule.ids>230,314,776,780,881,27901,27902,58213,58446</link.rule.ids><backlink>$$Uhttps://hal.science/hal-01470325$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>CARTON, OLIVIER</creatorcontrib><creatorcontrib>COLCOMBET, THOMAS</creatorcontrib><creatorcontrib>PUPPIS, GABRIELE</creatorcontrib><title>AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS</title><title>The Journal of symbolic logic</title><description>We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability in monadic second-order (MSO) logic. We also provide three logical applications. First, we establish the first known collapse result for the quantifier alternation of MSO logic over countable linear orderings. Second, we solve an open problem posed by Gurevich and Rabinovich, concerning the MSO-definability of sets of rational numbers using the reals in the background. Third, we establish the MSO-definability of the set of yields induced by an MSO-definable set of trees, confirming a conjecture posed by Bruyère, Carton, and Sénizergues.</description><subject>Computer Science</subject><subject>Formal Languages and Automata Theory</subject><subject>Logic</subject><subject>Logic in Computer Science</subject><subject>Mathematics</subject><subject>Philosophy</subject><subject>Realism</subject><issn>0022-4812</issn><issn>1943-5886</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2018</creationdate><recordtype>article</recordtype><recordid>eNo90E1rg0AQBuCltNA07aX3gtBTC6azH-rucWOMEawGYw49LetqaCStrSaF_vsqllxmYHh4GV6E7jHMMGDvpe4OMwKYz7wLNMGCUdvh3L1EEwBCbMYxuUY3XVcDgCMYn6BQJpaMw2Ceyci35HqdpdJfWXlqvW5SexEso0TOozjK36w0sfx0m-RyHgdWHCWBzKw0WwRZlISbW3S104euuvvfU7RdBrm_suM0jHwZ24Y6-Gh7piKgK0oclxFtDCuJK9gOG4Y1EYRzgUtcCG3KojBYgBbUAQ6aFF7Zj4pO0dOY-64P6qvdf-j2VzV6r1YyVsMNMPOgz_8hvX0c7VfbfJ-q7qjq5tR-9u8p4nGPgsOI16vnUZm26bq22p1jMaihVNWXqoZS1YAfRlx3x6Y9S-K6ANR16R9fwGsK</recordid><startdate>20180901</startdate><enddate>20180901</enddate><creator>CARTON, OLIVIER</creator><creator>COLCOMBET, THOMAS</creator><creator>PUPPIS, GABRIELE</creator><general>Association for Symbolic Logic, Inc</general><general>Cambridge University Press</general><general>Association for Symbolic Logic</general><scope>AAYXX</scope><scope>CITATION</scope><scope>AABKS</scope><scope>ABSDQ</scope><scope>1XC</scope><scope>VOOES</scope><orcidid>https://orcid.org/0000-0002-2728-6534</orcidid><orcidid>https://orcid.org/0000-0001-9831-3264</orcidid><orcidid>https://orcid.org/0000-0001-6529-6963</orcidid></search><sort><creationdate>20180901</creationdate><title>AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS</title><author>CARTON, OLIVIER ; COLCOMBET, THOMAS ; PUPPIS, GABRIELE</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c351t-7ce20ae325642acc4d2694f1c41a2928891d1b9acdbbc190a935080a2b7da2be3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2018</creationdate><topic>Computer Science</topic><topic>Formal Languages and Automata Theory</topic><topic>Logic</topic><topic>Logic in Computer Science</topic><topic>Mathematics</topic><topic>Philosophy</topic><topic>Realism</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>CARTON, OLIVIER</creatorcontrib><creatorcontrib>COLCOMBET, THOMAS</creatorcontrib><creatorcontrib>PUPPIS, GABRIELE</creatorcontrib><collection>CrossRef</collection><collection>Philosophy Collection</collection><collection>Philosophy Database</collection><collection>Hyper Article en Ligne (HAL)</collection><collection>Hyper Article en Ligne (HAL) (Open Access)</collection><jtitle>The Journal of symbolic logic</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>CARTON, OLIVIER</au><au>COLCOMBET, THOMAS</au><au>PUPPIS, GABRIELE</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS</atitle><jtitle>The Journal of symbolic logic</jtitle><date>2018-09-01</date><risdate>2018</risdate><volume>83</volume><issue>3</issue><spage>1147</spage><epage>1189</epage><pages>1147-1189</pages><issn>0022-4812</issn><eissn>1943-5886</eissn><abstract>We develop an algebraic notion of recognizability for languages of words indexed by countable linear orderings. We prove that this notion is effectively equivalent to definability in monadic second-order (MSO) logic. We also provide three logical applications. First, we establish the first known collapse result for the quantifier alternation of MSO logic over countable linear orderings. Second, we solve an open problem posed by Gurevich and Rabinovich, concerning the MSO-definability of sets of rational numbers using the reals in the background. Third, we establish the MSO-definability of the set of yields induced by an MSO-definable set of trees, confirming a conjecture posed by Bruyère, Carton, and Sénizergues.</abstract><cop>Pasadena</cop><pub>Association for Symbolic Logic, Inc</pub><doi>10.1017/jsl.2018.7</doi><tpages>43</tpages><orcidid>https://orcid.org/0000-0002-2728-6534</orcidid><orcidid>https://orcid.org/0000-0001-9831-3264</orcidid><orcidid>https://orcid.org/0000-0001-6529-6963</orcidid><oa>free_for_read</oa></addata></record>
fulltext fulltext
identifier ISSN: 0022-4812
ispartof The Journal of symbolic logic, 2018-09, Vol.83 (3), p.1147-1189
issn 0022-4812
1943-5886
language eng
recordid cdi_hal_primary_oai_HAL_hal_01470325v2
source JSTOR Archival Journals and Primary Sources Collection; Cambridge University Press
subjects Computer Science
Formal Languages and Automata Theory
Logic
Logic in Computer Science
Mathematics
Philosophy
Realism
title AN ALGEBRAIC APPROACH TO MSO-DEFINABILITY ON COUNTABLE LINEAR ORDERINGS
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-02-09T21%3A41%3A39IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-jstor_hal_p&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=AN%20ALGEBRAIC%20APPROACH%20TO%20MSO-DEFINABILITY%20ON%20COUNTABLE%20LINEAR%20ORDERINGS&rft.jtitle=The%20Journal%20of%20symbolic%20logic&rft.au=CARTON,%20OLIVIER&rft.date=2018-09-01&rft.volume=83&rft.issue=3&rft.spage=1147&rft.epage=1189&rft.pages=1147-1189&rft.issn=0022-4812&rft.eissn=1943-5886&rft_id=info:doi/10.1017/jsl.2018.7&rft_dat=%3Cjstor_hal_p%3E26600366%3C/jstor_hal_p%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c351t-7ce20ae325642acc4d2694f1c41a2928891d1b9acdbbc190a935080a2b7da2be3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2787305427&rft_id=info:pmid/&rft_jstor_id=26600366&rfr_iscdi=true