We investigate the expressive power of second-order logic over finite structures, when two limitations are imposed. Let SAA ) be the set of second-order formulas such that the arity of the relation variables is bounded by k and the number of alternations of second-order quantification is bounded by n . We show that this imposes a proper hierarchy on second-order logic, i.e. for every k , n there are problems not definable in AA but definable in AA for some c (...) 1 , d 1 . The method to show this is to introduce the set AUTOSAT of formulas in F which satisfy themselves. We study the complexity of this set for various fragments of second-order loeic. For first-order logic FOL with unbounded alternation of quantifiers AUTOSAT is PSpace complete. For first-order logic FOL n with alternation of quantifiers bounded by n , AUTOSAT is definable in AA . AUTOSAT) is definable in AA for some c 1 , d 1. (shrink)

We introduce a cyclic proof system for the two-way alternation-free modal μ-calculus. The system manipulates one-sided Gentzen sequents and locally deals with the backwards modalities by allowing analytic applications of the cut rule. The global effect of backwards modalities on traces is handled by making the semantics relative to a specific strategy of the opponent in the evaluation game. This allows us to augment sequents by so-called trace atoms, describing traces that the proponent can construct against the opponent’s strategy. (...) The idea for trace atoms comes from Vardi’s reduction of alternating two-way automata to deterministic one-way automata. Using the multi-focus annotations introduced earlier by Marti and Venema, we turn this trace-based system into a path-based system. We prove that our system is sound for all sequents and complete for sequents not containing trace atoms. (shrink)

Journal Name: Cognitive Linguistics Issue: Ahead of print.

Recent evidence suggests that probabilistic grammars may be modulated by communication mode and genre. Accordingly, the question arises how complex language users’ lectal competence is, where complexity is proportional to the extent to which choice-making processes depend on the situation of language use. Do probabilistic constraints vary when we talk to a friend compared to when we give a speech? Are differences between spoken and written language larger than those within each mode? In the present study, we aim to approach (...) these questions systematically. Guided by theorizing in cognitive (socio)linguistics and using logistic regression based on corpus materials, we analyzed the dative alternation with give (The government gives farmers money vs. The government gives money to farmers) in four broad registers of English: spoken informal, spoken formal, written informal, and written formal. Corpus analysis was supplemented with a scalar rating experiment. Results suggest that language users’ probabilistic grammars vary as a function of register. (shrink)

This paper discusses the role of cognitive factors in language change; specifically, it investigates the potential impact of argument ambiguity avoidance on the emergence of one of the most well-studied syntactic alternations in English, viz. the dative alternation. Linking this development to other major changes in the history of English like the loss of case marking, I propose that morphological as well as semantic-pragmatic ambiguity between prototypical agents and prototypical recipients in ditransitive clauses plausibly gave a processing advantage to (...) patterns with higher cue reliability such as prepositional marking, but also fixed clause-level order. The main hypotheses are tested through a quantitative analysis of ditransitives in a corpus of Middle English, which confirms that the spread of the PP-construction is impacted by argument ambiguity and demonstrates that this change reflects a complex restructuring of disambiguation strategies. (shrink)

Within a one-dimensional spatial framework, we deduce that partiesto go negative’, by blaming alleged insufficiencies of the rival concerning commonly shared values, increase with their ideological proximity. We test our hypothesis by considering the long period of no-cabinet alternation that characterized both Italy and Japan. In particular, we focus on the (spatial) incentives of the Italian Communist Party and of the Japanese Socialist Party to emphasize on a particular topic related to negative campaigning, i.e. political corruption issues. The status (...) of the perennial opposition held by both parties, together with the existence of several political corruption scandals during the period considered, makes the Italian and the Japanese political systems particularly apt to test our hypothesis. The results, based on data derived from electoral programs, support our theoretical insights. (shrink)

The Russian Genitive of Negation construction (Gen Neg) involves case alternation between Genitive and the two structural cases, Nominative and Accusative.1 The factors governing the alternation have been a matter of debate for many decades, and there is a huge literature. Here we focus on one central issue and its theoretical ramifications. The theoretical issue is the following. The same truth-conditional content can often be structured in more than one way; we believe that there is a distinction between (...) choices in how to structure a situation to be described, and choices in how to structure a sentence describing the (already structured) situation. The distinction may not always be sharp, and the term Information Structure may perhaps cover both, but we believe that the distinction is important and needs closer attention. Babby (1980), in a masterful work on the Russian Genitive of Negation, argued that the choice depended principally on Theme-Rheme structure; after initially following Babby (Borschev & Partee 1998), we later argued (Borschev & Partee 2002a,b) that the choice reflects not Theme-Rheme structure but a structuring of the described situation which we call Perspectival Structure. Here we briefly review the phenomenon, Babby’s Theme-Rheme-based analysis, and our arguments for a different analysis. We then consider Hanging Topics, partitive Genitives, and broader licensing conditions of Genitive case, raising the possibility that our counterexamples to Babby’s use of Theme-Rheme structure might be explained away as examples involving Hanging Topics rather than (Praguian) Themes. We argue against that idea as well, but leave open the possibility that our Perspectival Structure may eventually be construable as a kind of information structure itself, if that notion can include some kinds of structuring of the situation as well as of the discourse. (shrink)

The present work is a contribution to the understanding of the sempiternal problem of the “burden of factor two” implied by sexual reproduction versus asexual one, as males are energy consumers not contributing to the production of offspring. We construct a deterministic mathematical model in population dynamics where a species enjoys both sexual and parthenogenetic capabilities of reproduction and lives on a limited resource. We then show how polygamy implies instability of a parthenogenetic population with a small number of sexually (...) born males. This instability implies evolution of the system towards an attractor involving both populations. We also exhibit the analogy with a parasite/host system. (shrink)

This study investigates the extent to which there is individuality in how structural variation is conditioned over time. Earlier research already classified the diachronically unstable gerund variation as involving a high fraction of mixed-usage speakers throughout the change, whereby the proportion of the conservative variant versus the progressive variant as observable in the linguistic output of individual language users superficially resembles the mean proportion as observable at the population level. However, this study sets out to show that there can still (...) be heterogeneity within such a centralized population in terms of how each individual conditions the observed variation. A random forest and conditional inference tree analysis of over 14,000 gerunds uttered by nineteen seventeenth-century authors is presented to show that, while the most important language-internal factors conditioning the gerund variation are adopted by (and shared between) all authors, we can still attest inter-individual variation (i) at lower levels of variable importance, and (ii) in the breadth of the range of contexts individual authors employ to condition the attested variation. (shrink)

Journal Name: Cognitive Linguistics Issue: Ahead of print.

This paper investigates three morphosyntactic alternations in Estonian – those between the exterior locative cases allative, adessive and ablative and the corresponding postpositionspeale‘onto’,peal‘on’ andpealt‘off’. Based on the Complexity Principle (e.g., Rohdenburg, Günter. 2002. Processing complexity and the variable use of prepositions in English. In Hubert Cuyckens & Günter Radden (eds.),Perspectives on prepositions, 79–100. Tübingen: Niemeyer), we expect cognitively more complex constructions to use more explicit (i.e., morphologically more substantial) marking by means of a postposition. Further, we expect variation to be (...) conditioned similarly in all three semantic categories. For each of the three alternations, a random sample of the two outcomes (case vs. postposition) from the Estonian National Corpus is used, resulting in 3,000 data points. Using properties of the Landmark phrase as independent variables in Bayesian mixed-effects logistic regression models, we predict the choice of postpositions over case-marked realisations. Of the patterns found, only the frequency-related one supports our complexity-related hypothesis. We conclude that the Complexity Principle, in its general form, has little explanatory power for the Estonian constructions at hand and, in particular, that the derived principle of ‘analytic support’ is not generally applicable. We show, however, that the grammatical knowledge of Estonian exterior locative cases and the corresponding postpositions is regulated by our three factors in a relatively uniform way. (shrink)