 |
 |
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)2010On Second-Order Monadic Monoidal and Groupoidal QuantifiersArticle
Authors: Juha Kontinen 
; 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.
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
Classifications
Mathematics Subject Classification 20201
- 03C80 - Logic with extra quantifiers and operators
- 03D05 - Automata and formal grammars in connection with logical questions
- 03D15 - Complexity of computation (including implicit computational complexity)
- 03D40 - Word problems, etc. in computability and recursion theory
- 68Q15 - Complexity classes (hierarchies, relations among complexity classes, etc.)
- 68Q19 - Descriptive complexity and finite models
Publications
1 Document citing this article
Consultation statistics
This page has been seen 3004 times.
This article's PDF has been downloaded 504 times.