Search results for "quantifier"

A NOTE ON THE ASYMPTOTIC PROBABILITIES OF EXISTENTIAL SECOND-ORDER MINIMAL GÖDEL SENTENCES WITH EQUALITY

1995

The minimal Gödel class is the class of first-order prenex sentences whose quantifier prefix consists of two universal quantifiers followed by just one existential quantifier. We prove that asymptotic probabilities of existential second-order sentences, whose first-order part is in the minimal Gödel class, form a dense subset of the unit interval.

Quantifying nouns in Italian

2012

Formal Variation and Language Change in Catalan Quantifiers : the Role of Pragmatics

2020

This article studies the formal variation of the masculine singular forms of the quantifiers u/un 'one', algú/algun 'someone, some', ningú/ningun 'no-one, anyone, not one, any, none' and cada u/cada un 'everyone, each one' in contemporary Catalan. The standard uses of these forms are contrasted with dialectal uses, obtained from a thorough search in oral and written corpora. In addition, they are compared with the uses in the other Romance languages and with their historical evolution in Catalan. The whole set of data, and especially the dialectal information on the Valencian area, allow us to explain the various factors that have interacted in the variation and formal change of these quant…

Quantum Finite Automata and Logics

2006

The connection between measure once quantum finite automata (MO-QFA) and logic is studied in this paper. The language class recognized by MO-QFA is compared to languages described by the first order logics and modular logics. And the equivalence between languages accepted by MO-QFA and languages described by formulas using Lindstrom quantifier is shown.

The article <i>a(n)</i> in English quantifying expressions: A default marker of cardinality

2020

Certain English quantificational expressions feature what appears to be an indefinite article, e.g. a bunch, a few, a hundred. These can be divided into three types of quantifying expressions: pseudopartitives (a lot, a bunch, a ton), article-requiring quantifiers (a few, a couple, a hundred), and article-free quantifiers (three, many, several); article-free quantifiers have an article under certain circumstances, e.g. modification by an adjective (a surprising 30 …). While standard analyses would take the article in these expressions to be a D head, it is argued here that the article is not in D, nor is it singular or count, as evidenced by its (lack of an) interaction with verbal agreemen…

Logics for context-free languages

1995

We define matchings, and show that they capture the essence of context-freeness. More precisely, we show that the class of context-free languages coincides with the class of those sets of strings which can be defined by sentences of the form ∃ bϕ, where ϕ is first order, b is a binary predicate symbol, and the range of the second order quantifier is restricted to the class of matchings. Several variations and extensions are discussed.

The monadic quantifier alternation hierarchy over grids and pictures

1998

The subject of this paper is the expressive power of monadic second-order logic over two-dimensional grids. We give a new, self-contained game-theoretical proof of the nonexpressibility results of Matz and Thomas. As we show, this implies the strictness of the monadic second-order quantifier alternation hierarchy over grids.

Adding Path-Functional Dependencies to the Guarded Two-Variable Fragment with Counting

2017

The satisfiability and finite satisfiability problems for the two-variable guarded fragment of first-order logic with counting quantifiers, a database, and path-functional dependencies are both ExpTime-complete.

The Descriptive Complexity Approach to LOGCFL

1998

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. Our work extends the elaborate theory relating monoidal quantifiers to NC1 and its subclasses. In the absence of the BIT predicate, we resolve the main issues: we show in particular that no single outermost unary groupoidal quantifier with FO can capture all the context-free languages, and we obtain the surprising result that a variant of Greibach's ``hardest context-free language'' is LOGCFL-complete under quantifier-free BIT-free proj…

La variación formal de los cuantificadores en catalán: estudio diacrónico (siglos XV‒XX)

2020

AbstractThis article studies the formal variation of the existential quantifiers u/un (‘one; a, an’), algú/algun (‘someone; some’), ningú/ningun (‘no one, anyone; any’) and the distributive universal quantifier cada u/cada un (‘everyone’) in Catalan. The research is based on an extensive diachronic corpus of texts written between the 15th and 20th centuries. The author classifies the syntactic structures of these quantifiers and analyses their meaning and formal vacillations: apocopated form (without ‑n) vs. non-apocopated form (with ‑n). Although hesitations tend to disappear gradually during the period under analysis, the uses of these quantifiers change in Catalan dialects. In fact, dist…