共查询到20条相似文献,搜索用时 31 毫秒
1.
We give a sufficient condition for the inexpressibility of the k-th extended vectorization of a generalized quantifier in , the extension of first-order logic by all k-ary quantifiers. The condition is based on a model construction which, given two -equivalent models with certain additional structure, yields a pair of -equivalent models. We also consider some applications of this condition to quantifiers that correspond to graph properties,
such as connectivity and planarity.
Received: 15 October 1996 相似文献
2.
Raine Rönnholm 《Annals of Pure and Applied Logic》2019,170(9):1070-1099
In this paper we study the expressive power of k-ary exclusion logic, EXC[k], that is obtained by extending first order logic with k-ary exclusion atoms. It is known that without arity bounds exclusion logic is equivalent with dependence logic. By observing the translations, we see that the expressive power of EXC[k] lies in between k-ary and ()-ary dependence logics. We will show that, at least in the case when , both of these inclusions are proper.In a recent work by the author it was shown that k-ary inclusion-exclusion logic is equivalent with k-ary existential second order logic, ESO[k]. We will show that, on the level of sentences, it is possible to simulate inclusion atoms with exclusion atoms, and in this way express ESO[k]-sentences by using only k-ary exclusion atoms. For this translation we also need to introduce a novel method for “unifying” the values of certain variables in a team. As a consequence, EXC[k] captures ESO[k] on the level of sentences, and we obtain a strict arity hierarchy for exclusion logic. It also follows that k-ary inclusion logic is strictly weaker than EXC[k].Finally we use similar techniques to formulate a translation from ESO[k] to k-ary inclusion logic with an alternative strict semantics. Consequently, for any arity fragment of inclusion logic, strict semantics is strictly more expressive than lax semantics. 相似文献
3.
Raine Rönnholm 《Annals of Pure and Applied Logic》2018,169(3):177-215
In this paper we analyze k-ary inclusion–exclusion logic, INEX[k], which is obtained by extending first order logic with k-ary inclusion and exclusion atoms. We show that every formula of INEX[k] can be expressed with a formula of k-ary existential second order logic, ESO[k]. Conversely, every formula of ESO[k] with at most k-ary free relation variables can be expressed with a formula of INEX[k]. From this it follows that, on the level of sentences, INEX[k] captures the expressive power of ESO[k].We also introduce several useful operators that can be expressed in INEX[k]. In particular, we define inclusion and exclusion quantifiers and so-called term value preserving disjunction which is essential for the proofs of the main results in this paper. Furthermore, we present a novel method of relativization for team semantics and analyze the duality of inclusion and exclusion atoms. 相似文献
4.
Martin Grohe 《Combinatorica》1999,19(4):507-532
of first-order logic whose formulas contain at most k variables (for some ). We show that for each , equivalence in the logic is complete for polynomial time. Moreover, we show that the same completeness result holds for the powerful extension of with counting quantifiers (for every ).
The k-dimensional Weisfeiler–Lehman algorithm is a combinatorial approach to graph isomorphism that generalizes the naive color-refinement
method (for ). Cai, Fürer and Immerman [6] proved that two finite graphs are equivalent in the logic if, and only if, they can be distinguished by the k-dimensional Weisfeiler-Lehman algorithm. Thus a corollary of our main result is that the question of whether two finite graphs
can be distinguished by the k-dimensional Weisfeiler–Lehman algorithm is P-complete for each .
Received: March 23, 1998 相似文献
5.
Martin Lück 《Annals of Pure and Applied Logic》2018,169(9):928-969
In a modular approach, we lift Hilbert-style proof systems for propositional, modal and first-order logic to generalized systems for their respective team-based extensions. We obtain sound and complete axiomatizations for the dependence-free fragment FO(~) of Väänänen's first-order team logic TL, for propositional team logic PTL, quantified propositional team logic QPTL, modal team logic MTL, and for the corresponding logics of dependence, independence, inclusion and exclusion.As a crucial step in the completeness proof, we show that the above logics admit, in a particular sense, a semantics-preserving elimination of modalities and quantifiers from formulas. 相似文献
6.
In this paper we show that (n) variables are needed for first-order logic with counting to identify graphs onn vertices. Thek-variable language with counting is equivalent to the (k–1)-dimensional Weisfeiler-Lehman method. We thus settle a long-standing open problem. Previously it was an open question whether or not 4 variables suffice. Our lower bound remains true over a set of graphs of color class size 4. This contrasts sharply with the fact that 3 variables suffice to identify all graphs of color class size 3, and 2 variables suffice to identify almost all graphs. Our lower bound is optimal up to multiplication by a constant becausen variables obviously suffice to identify graphs onn vertices.Research supported by NSF grant CCR-8709818.Research supported by NSF grant CCR-8805978 and Pennsylvania State University Research Initiation grant 428-45.Research supported by NSF grants DCR-8603346 and CCR-8806308. 相似文献
7.
We define a logic D capable of expressing dependence of a variable on designated variables only. Thus D has similar goals to the Henkin quantifiers of [4] and the independence friendly logic of [6] that it much resembles. The logic D achieves these goals by realizing the desired dependence declarations of variables on the level of atomic formulas. By [3] and [17], ability to limit dependence relations between variables leads to existential second order expressive power. Our D avoids some difficulties arising in the original independence friendly logic from coupling the dependence declarations with existential quantifiers. As is the case with independence friendly logic, truth of D is definable inside D. We give such a definition for D in the spirit of [11] and [2] and [1]. 相似文献
8.
An n-ary operation Q:Σn→Σ is called an n-ary quasigroup of order |Σ| if in the relation x0=Q(x1,…,xn) knowledge of any n elements of x0,…,xn uniquely specifies the remaining one. Q is permutably reducible if Q(x1,…,xn)=P(R(xσ(1),…,xσ(k)),xσ(k+1),…,xσ(n)) where P and R are (n-k+1)-ary and k-ary quasigroups, σ is a permutation, and 1<k<n. An m-ary quasigroup S is called a retract of Q if it can be obtained from Q or one of its inverses by fixing n-m>0 arguments. We prove that if the maximum arity of a permutably irreducible retract of an n-ary quasigroup Q belongs to {3,…,n-3}, then Q is permutably reducible. 相似文献
9.
Anuj Dawar 《Annals of Pure and Applied Logic》2009,161(1):1-42
We investigate model theoretic characterisations of the expressive power of modal logics in terms of bisimulation invariance. The paradigmatic result of this kind is van Benthem’s theorem, which says that a first-order formula is invariant under bisimulation if, and only if, it is equivalent to a formula of basic modal logic. The present investigation primarily concerns ramifications for specific classes of structures. We study in particular model classes defined through conditions on the underlying frames, with a focus on frame classes that play a major role in modal correspondence theory and often correspond to typical application domains of modal logics. Classical model theoretic arguments do not apply to many of the most interesting classes-for instance, rooted frames, finite rooted frames, finite transitive frames, well-founded transitive frames, finite equivalence frames-as these are not elementary. Instead we develop and extend the game-based analysis (first-order Ehrenfeucht-Fraïssé versus bisimulation games) over such classes and provide bisimulation preserving model constructions within these classes. Over most of the classes considered, we obtain finite model theory analogues of the classically expected characterisations, with new proofs also for the classical setting. The class of transitive frames is a notable exception, with a marked difference between the classical and the finite model theory of bisimulation invariant first-order properties. Over the class of all finite transitive frames in particular, we find that monadic second-order logic is no more expressive than first-order as far as bisimulation invariant properties are concerned — though both are more expressive here than basic modal logic. We obtain ramifications of the de Jongh-Sambin theorem and a new and specific analogue of the Janin-Walukiewicz characterisation of bisimulation invariant monadic second-order for finite transitive frames. 相似文献
10.
In this paper, we introduce a new approach to independent quantifiers, as originally introduced in Informational independence as a semantic phenomenon by Hintikka and Sandu (1989) [9] under the header of independence-friendly (IF) languages. Unlike other approaches, which rely heavily on compositional methods, we shall analyze independent quantifiers via equilibriums in strategic games. In this approach, coined equilibrium semantics, the value of an IF sentence on a particular structure is determined by the expected utility of the existential player in any of the game’s equilibriums. This approach was suggested in Henkin quantifiers and complete problems by Blass and Gurevich (1986) [2] but has not been taken up before. We prove that each rational number can be realized by an IF sentence. We also give a lower and upper bound on the expressive power of IF logic under equilibrium semantics. 相似文献
11.
Hajós theorem states that every graph with chromatic number at least k can be obtained from the complete graph K
k
by a sequence of simple operations such that every intermediate graph also has chromatic number at least k. Here, Hajós theorem is extended in three slightly different ways to colorings and circular colorings of edge-weighted graphs. These extensions shed some new light on the Hajós theorem and show that colorings of edge-weighted graphs are most natural extension of usual graph colorings.* Supported in part by the Ministry of Education, Science and Sport of Slovenia, Research Program P0–0507–0101. 相似文献
12.
13.
A value space is a topological algebra B equipped with a non-empty family of continuous quantifiers :B∗→B. We will describe first-order logic on the basis of B. Operations of B are used as connectives and its relations are used to define statements. We prove under some normality conditions on the value space that any theory in the new setting can be represented by a classical first-order theory. 相似文献
14.
Kevin Cattell Frank Ruskey Joe Sawada Micaela Serra C. Robert Miers 《Journal of Algorithms in Cognition, Informatics and Logic》2000,37(2):267
Many applications call for exhaustive lists of strings subject to various constraints, such as inequivalence under group actions. A k-ary necklace is an equivalence class of k-ary strings under rotation (the cyclic group). A k-ary unlabeled necklace is an equivalence class of k-ary strings under rotation and permutation of alphabet symbols. We present new, fast, simple, recursive algorithms for generating (i.e., listing) all necklaces and binary unlabeled necklaces. These algorithms have optimal running times in the sense that their running times are proportional to the number of necklaces produced. The algorithm for generating necklaces can be used as the basis for efficiently generating many other equivalence classes of strings under rotation and has been applied to generating bracelets, fixed density necklaces, and chord diagrams. As another application, we describe the implementation of a fast algorithm for listing all degree n irreducible and primitive polynomials over GF(2). 相似文献
15.
M. Eshaghi Gordji H. Khodaei 《Nonlinear Analysis: Theory, Methods & Applications》2009,71(11):5629-5643
In this paper, we achieve the general solution and the generalized Hyers–Ulam–Rassias stability of the following functional equation
f(x+ky)+f(x−ky)=k2f(x+y)+k2f(x−y)+2(1−k2)f(x)