Juha Kontinen ; Heribert Vollmer - On Second-Order Monadic Monoidal and Groupoidal Quantifiers

lmcs:1006 - Logical Methods in Computer Science, September 20, 2010, Volume 6, Issue 3 - https://doi.org/10.2168/LMCS-6(3:25)2010
On Second-Order Monadic Monoidal and Groupoidal QuantifiersArticle

Authors: Juha Kontinen ORCID; Heribert Vollmer

    We study logics defined in terms of second-order monadic monoidal and groupoidal quantifiers. These are generalized quantifiers defined by monoid and groupoid word-problems, equivalently, by regular and context-free languages. We give a computational classification of the expressive power of these logics over strings with varying built-in predicates. In particular, we show that ATIME(n) can be logically characterized in terms of second-order monadic monoidal quantifiers.

    https://doi.org/10.2168/LMCS-6(3:25)2010
    Source: arXiv.org:1009.2893
    Volume: Volume 6, Issue 3
    Published on: September 20, 2010
    Imported on: September 21, 2009
    Keywords: Computer Science - Logic in Computer Science,F.4.1, F.4.3
    Licence: arXiv.org - Non-exclusive license to distribute

    Publications

    Has review
    • 1 zbMATH Open

    1 Document citing this article

    Share and export

    Consultation statistics

    This page has been seen 1507 times.
    This article's PDF has been downloaded 342 times.