dc.identifier.uri |
http://dx.doi.org/10.15488/2008 |
|
dc.identifier.uri |
http://www.repo.uni-hannover.de/handle/123456789/2033 |
|
dc.contributor.author |
Kontinen, Juha
|
|
dc.contributor.author |
Vollmer, Heribert
|
|
dc.date.accessioned |
2017-10-10T08:16:57Z |
|
dc.date.available |
2017-10-10T08:16:57Z |
|
dc.date.issued |
2010 |
|
dc.identifier.citation |
Kontinen, Juha; Vollmer, Heribert: On second-order monadic monoidal and groupoidal quantifiers. In: Logical Methods in Computer Science 6 (2010), Nr. 3, 25. DOI: https://doi.org/10.2168/LMCS-6(3:25)2010 |
|
dc.description.abstract |
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. |
eng |
dc.language.iso |
eng |
|
dc.publisher |
Braunschweig : Tech. Univ. Braunschweig |
|
dc.relation.ispartofseries |
Logical Methods in Computer Science 6 (2010), Nr. 3 |
|
dc.rights |
CC BY-ND 2.0 Unported |
|
dc.rights.uri |
https://creativecommons.org/licenses/by-nd/2.0/ |
|
dc.subject |
monoid |
eng |
dc.subject |
groupoid |
eng |
dc.subject |
word-problem |
eng |
dc.subject |
leaf language |
eng |
dc.subject |
second-order generalized quantifier |
eng |
dc.subject |
computational complexity |
eng |
dc.subject |
descriptive complexity |
eng |
dc.subject |
generalized quantifiers |
eng |
dc.subject |
regular languages |
eng |
dc.subject |
permanent |
eng |
dc.subject |
logcfl |
eng |
dc.subject |
logic |
eng |
dc.subject.ddc |
004 | Informatik
|
ger |
dc.title |
On second-order monadic monoidal and groupoidal quantifiers |
|
dc.type |
Article |
|
dc.type |
Text |
|
dc.relation.issn |
1860-5974 |
|
dc.relation.doi |
https://doi.org/10.2168/LMCS-6(3:25)2010 |
|
dc.bibliographicCitation.issue |
3 |
|
dc.bibliographicCitation.volume |
6 |
|
dc.bibliographicCitation.firstPage |
25 |
|
dc.description.version |
publishedVersion |
|
tib.accessRights |
frei zug�nglich |
|