𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A descriptive complexity approach to the linear hierarchy

✍ Scribed by Yassine Hachaı̈chi

Publisher
Elsevier Science
Year
2003
Tongue
English
Weight
204 KB
Volume
304
Category
Article
ISSN
0304-3975

No coin nor oath required. For personal study only.

✦ Synopsis

This paper gives some new logical characterizations of the class of rudimentary languages in the scope of descriptive complexity. These characterizations are based on a logic introduced by Parigot and Pelz to characterize Petri Net languages, and generalized quantiÿers of comparison of cardinality.

📜 SIMILAR VOLUMES

The Descriptive Complexity Approach to L
The Descriptive Complexity Approach to LOGCFL
✍ Clemens Lautemann; Pierre McKenzie; Thomas Schwentick; Heribert Vollmer 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 235 KB

Building upon the known generalized-quantifier-based first-order characterization of LOGCFL, we lay the groundwork for a deeper investigation. Specifically, we examine subclasses of LOGCFL arising from varying the arity and nesting of groupoidal quantifiers in first-order logic with linear order. Ou