On Second-Order Monadic Monoidal and Groupoidal Quantifiers
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 l...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Logical Methods in Computer Science e.V.
2010-09-01
|
| Series: | Logical Methods in Computer Science |
| Subjects: | |
| Online Access: | https://lmcs.episciences.org/1006/pdf |
| _version_ | 1827322934128017408 |
|---|---|
| author | Juha Kontinen Heribert Vollmer |
| author_facet | Juha Kontinen Heribert Vollmer |
| author_sort | Juha Kontinen |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:37:50Z |
| format | Article |
| id | doaj.art-8a714fc8703740c28aafbf800add9dd0 |
| institution | Directory Open Access Journal |
| issn | 1860-5974 |
| language | English |
| last_indexed | 2024-04-25T01:37:50Z |
| publishDate | 2010-09-01 |
| publisher | Logical Methods in Computer Science e.V. |
| record_format | Article |
| series | Logical Methods in Computer Science |
| spelling | doaj.art-8a714fc8703740c28aafbf800add9dd02024-03-08T09:12:34ZengLogical Methods in Computer Science e.V.Logical Methods in Computer Science1860-59742010-09-01Volume 6, Issue 310.2168/LMCS-6(3:25)20101006On Second-Order Monadic Monoidal and Groupoidal QuantifiersJuha Kontinenhttps://orcid.org/0000-0003-0115-5154Heribert VollmerWe 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://lmcs.episciences.org/1006/pdfcomputer science - logic in computer sciencef.4.1, f.4.3 |
| spellingShingle | Juha Kontinen Heribert Vollmer On Second-Order Monadic Monoidal and Groupoidal Quantifiers Logical Methods in Computer Science computer science - logic in computer science f.4.1, f.4.3 |
| title | On Second-Order Monadic Monoidal and Groupoidal Quantifiers |
| title_full | On Second-Order Monadic Monoidal and Groupoidal Quantifiers |
| title_fullStr | On Second-Order Monadic Monoidal and Groupoidal Quantifiers |
| title_full_unstemmed | On Second-Order Monadic Monoidal and Groupoidal Quantifiers |
| title_short | On Second-Order Monadic Monoidal and Groupoidal Quantifiers |
| title_sort | on second order monadic monoidal and groupoidal quantifiers |
| topic | computer science - logic in computer science f.4.1, f.4.3 |
| url | https://lmcs.episciences.org/1006/pdf |
| work_keys_str_mv | AT juhakontinen onsecondordermonadicmonoidalandgroupoidalquantifiers AT heribertvollmer onsecondordermonadicmonoidalandgroupoidalquantifiers |