On second-order monadic monoidal and groupoidal quantifiers

DOI10.2168/LMCS-6(3:25)2010MaRDI QIDQ2786142zbMATH OpenFDO

Authors Juha Kontinen, Heribert Vollmer

Publication date 21 September 2010

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1009.2893

zbMATH Keywords

computational complexitydescriptive complexityleaf languagesecond-order generalized quantifierword problem

Mathematics Subject Classification ID

Logic with extra quantifiers and operators (03C80) Automata and formal grammars in connection with logical questions (03D05) Complexity of computation (including implicit computational complexity) (03D15) Word problems, etc. in computability and recursion theory (03D40) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Descriptive complexity and finite models (68Q19)

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.

Review text

A groupoid is a finite set \({G}\) on which a binary operation \(\ast\) (multiplication) with an identity element \(e\) is defined. For a fixed groupoid \({G}\), each \({S}\subseteq {G}\) defines a \({G}\)-word problem, i.e., a language \({W(S,G)}\) composed of all words \({w}\), over the alphabet \({G}\), that can be bracketed in such a way that \({w}\) multiplies out to an element of \({S}\). The word problem of a monoid, i.e., an associative groupoid, is defined analogously. Groupoid word problems relate to context-free languages in the same way as monoid word problems relate to regular languages: every such word problem is context-free, and every context-free language is a homomorphic pre-image of a groupoid word problem. NEWLINENEWLINEThe authors 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.NEWLINENEWLINEThey give a computational classification of the expressive power of these logics over strings with varying built-in predicates. In particular, it is shown that ATIME(\({n}\)) can be logically characterized in terms of second-order monadic monoidal quantifiers.NEWLINENEWLINETwo open questions are formulated.

Recommendations

• On Second-Order Monadic Groupoidal Quantifiers
• Monadic Second Order Logic with Measure and Category Quantifiers
• Quantitative Monadic Second-Order Logic
• scientific article; zbMATH DE number 2051828
• First order quantifiers in monadic second order logic

Cited in

(4)

• On Second-Order Monadic Groupoidal Quantifiers
• On Monadic Second-Order Theories of Multidominance Structures
• scientific article; zbMATH DE number 1072416 (Why is no real title available?)
• Leaf languages and string compression

This page was built for publication: On second-order monadic monoidal and groupoidal quantifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2786142)