A crevice on the Crane Beach: finite-degree predicatesReportar como inadecuado




A crevice on the Crane Beach: finite-degree predicates - Descarga este documento en PDF. Documentación en PDF para descargar gratis. Disponible también para leer online.

Reference: Cadilhac, M and Paperman, C, (2017). A crevice on the Crane Beach: finite-degree predicates. 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).Citable link to this page:

 

A crevice on the Crane Beach: finite-degree predicates

Abstract: First-order logic (FO) over words is shown tobe equiexpressive with FO equipped with a restricted set ofnumerical predicates, namely the order, a binary predicate MSB0,and the finite-degree predicates: FO[ARB] = FO[≤, MSB0, FIN].The Crane Beach Property (CBP), introduced more than a decadeago, is true of a logic if all the expressible languages admittinga neutral letter are regular. Although it is known that FO[ARB]does not have the CBP, it is shown here that the (strong formof the) CBP holds for both FO[≤, FIN] and FO[≤, MSB0]. ThusFO[≤, FIN] exhibits a form of locality and the CBP, and canstill express a wide variety of languages, while being one simplepredicate away from the expressive power of FO[ARB]. Thecounting ability of FO[≤, FIN] is studied as an application.

Publication status:PublishedPeer Review status:Peer reviewedVersion:Accepted ManuscriptDate of acceptance:22 March 2017 Funder: Deutsche Forschungsgemeinschaft   Notes:This is the accepted manuscript version of the article. The final version is available online from IEEE at: https://doi.org/10.1109/LICS.2017.8005148

Bibliographic Details

Publisher: IEEE

Publisher Website: http://ieeexplore.ieee.org/

Host: 2017 32nd Annual ACM/IEEE Symposium on Logic in Computer Science (LICS)see more from them

Publication Website: http://ieeexplore.ieee.org/xpl/mostRecentIssue.jsp?punumber=7999337

Issue Date: 2017-08-10Identifiers

Uuid: uuid:787ac043-2942-421a-a157-7631b37adb0e

Urn: uri:787ac043-2942-421a-a157-7631b37adb0e

Pubs-id: pubs:690039

Issn: 1043-6871

Isbn: 978-1-5090-3019-4

Doi: https://doi.org/10.1109/LICS.2017.8005148 Item Description

Type: conference-proceeding;

Version: Accepted Manuscript

Relationships





Autor: Cadilhac, M - Oxford, MPLS, Computer Science - - - Paperman, C - - - - Bibliographic Details Publisher: IEEE - Publisher Website:

Fuente: https://ora.ox.ac.uk/objects/uuid:787ac043-2942-421a-a157-7631b37adb0e



DESCARGAR PDF




Documentos relacionados