Search results for "Existential quantification"
showing 10 items of 39 documents
Harsanyi Power Solutions for Cooperative Games on Voting Structures
2019
International audience; This paper deals with Harsanyi power solutions for cooperative games in which partial cooperation is based on specific union stable systems given by the winning coalitions derived from a voting game. This framework allows for analyzing new and real situations in which there exists a feedback between the economic influence of each coalition of agents and its political power. We provide an axiomatic characterization of the Harsanyi power solutions on the subclass of union stable systems arisen from the winning coalitions from a voting game when the influence is determined by a power index. In particular, we establish comparable axiomatizations, in this context, when co…
Case Distribution and Nominalization: Evidence from Finnish
2009
. In many languages, case is distributed among many grammatical elements inside of argument DPs. This article shows that case distribution in Finnish is sensitive to certain nontrivial structural properties of those DPs. This makes it possible to use case distribution as a tool to investigate the internal structure of a variety of DPs, including nominalized clauses. It is argued, based on such new evidence, that (i) there exists a syntactic nominalizer head n within various kinds of nominal phrases, and that (ii) genitive argument DPs of nominalized clauses undergo raising analogous to the EPP-triggered DP raising in finite clauses. Furthermore, these genitive arguments are base-generated …
Confined subgroups in periodic simple finitary linear groups
2002
A subgroupX of the locally finite groupG is said to beconfined, if there exists a finite subgroupF≤G such thatX g∩F≠1 for allg∈G. Since there seems to be a certain correspondence between proper confined subgroups inG and non-trivial ideals in the complex group algebra ℂG, we determine the confined subgroups of periodic simple finitary linear groups in this paper.
Splittings of Toric Ideals
2019
Let $I \subseteq R = \mathbb{K}[x_1,\ldots,x_n]$ be a toric ideal, i.e., a binomial prime ideal. We investigate when the ideal $I$ can be "split" into the sum of two smaller toric ideals. For a general toric ideal $I$, we give a sufficient condition for this splitting in terms of the integer matrix that defines $I$. When $I = I_G$ is the toric ideal of a finite simple graph $G$, we give additional splittings of $I_G$ related to subgraphs of $G$. When there exists a splitting $I = I_1+I_2$ of the toric ideal, we show that in some cases we can describe the (multi-)graded Betti numbers of $I$ in terms of the (multi-)graded Betti numbers of $I_1$ and $I_2$.
Frames for fusions of modal logics
2018
Let us consider multimodal logics and . We assume that is characterised by a class of connected frames, and there exists an -frame with a so-called -starting point. Similarly, the logic is characterised by a class of connected frames, and there exists an -frame with a -starting point. Using isomorphic copies of the frames and , we construct a connected frame which characterises the fusion . The frame thus obtained has some useful properties. Among others, is countable if both and are countable, and there is a special world of the frame such that any formula is valid in the frame if and only if it is valid at the point . We also describe a similar construction where we assume the existence o…
Correspondences Between 2-Brauer Characters of Solvable Groups
2010
Let G be a finite solvable group and let p be a prime. Let P ∈ Syl p (G) and N = N G (P). We prove that there exists a natural bijection between the 2-Brauer irreducible characters of p′-degree of G and those of N G (P).
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions
2007
For any AND-OR formula of size N, there exists a bounded-error N1/2+o(1)-time quantum algorithm, based on a discrete-time quantum walk, that evaluates this formula on a black-box input. Balanced, or "approximately balanced," formulas can be evaluated in O(radicN) queries, which is optimal. It follows that the (2-o(1))th power of the quantum query complexity is a lower bound on the formula size, almost solving in the positive an open problem posed by Laplante, Lee and Szegedy.
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.
On languages factorizing the free monoid
1996
A language X⊂A* is called factorizing if there exists a language Y⊂A* such that XY = A* This work was partially supported by ESPRIT-EBRA project ASMICS contact 6317 and project 40% MURST “Algoritmi, Modelli di Calcolo e Strutture Informative”. and the product is unambiguous. First we give a combinatorial characterization of factorizing languages. Further we prove that it is decidable whether a regular language X is factorizing and we construct an automaton recognizing the corresponding language Y. For finite languages we show that it suffices to consider words of bounded length. A complete characterization of factorizing languages with three words and explicit regular expression for the co…
On finding common neighborhoods in massive graphs
2003
AbstractWe consider the problem of finding pairs of vertices that share large common neighborhoods in massive graphs. We prove lower bounds on the resources needed to solve this problem on resource-bounded models of computation. In streaming models, in which algorithms can access the input only a constant number of times and only sequentially, we show that, even with randomization, any algorithm that determines if there exists any pair of vertices with a large common neighborhood must essentially store and process the input graph off line. In sampling models, in which algorithms can only query an oracle for the common neighborhoods of specified vertex pairs, we show that any algorithm must …