Axiomatizations of team logics

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.     

Negation and partial axiomatizations of dependence and independence logic revisited

In this paper, we axiomatize the negatable consequences in dependence and independence logic by extending the systems of natural deduction of the logics given in [22] and [11]. We prove a characterization theorem for negatable formulas in independence logic and negatable sentences in dependence logic, and identify an interesting class of formulas that are negatable in independence logic. Dependence and independence atoms, first-order formulas belong to this class. We also demonstrate our extended system of independence logic by giving explicit derivations for Armstrong's Axioms and the Geiger-Paz-Pearl axioms of dependence and independence atoms.     

Bilinear spaces over a fixed field are simple unstable

We study the model theory of vector spaces with a bilinear form over a fixed field. For finite fields this can be, and has been, done in the classical framework of full first-order logic. For infinite fields we need different logical frameworks. First we take a category-theoretic approach, which requires very little set-up. We show that linear independence forms a simple unstable independence relation. With some more work we then show that we can also work in the framework of positive logic, which is much more powerful than the category-theoretic approach and much closer to the classical framework of full first-order logic. We fully characterise the existentially closed models of the arising positive theory. Using the independence relation from before we conclude that the theory is simple unstable, in the sense that dividing has local character but there are many distinct types. We also provide positive version of what is commonly known as the Ryll-Nardzewski theorem for ω-categorical theories in full first-order logic, from which we conclude that bilinear spaces over a countable field are ω-categorical.     

Finite problems and the logic of the weak law of excluded middle

A new characteristic of propositional formulas as operations on finite problems, the cardinality of a sufficient solution set, is defined. It is proved that if a formula is deducible in the logic of the weak law of excluded middle, then the cardinality of a sufficient solution set is bounded by a constant depending only on the number of variables; otherwise, the accessible cardinality of a sufficient solution set is close to (greater than the nth root of) its trivial upper bound. This statement is an analog of the authors result about the algorithmic complexity of sets obtained as values of propositional formulas, which was published previously. Also, we introduce the notion of Kolmogorov complexity of finite problems and obtain similar results.     

Finite problems and the logic of the weak law of excluded middle

A new characteristic of propositional formulas as operations on finite problems, the cardinality of a sufficient solution set, is defined. It is proved that if a formula is deducible in the logic of the weak law of excluded middle, then the cardinality of a sufficient solution set is bounded by a constant depending only on the number of variables; otherwise, the accessible cardinality of a sufficient solution set is close to (greater than the nth root of) its trivial upper bound. This statement is an analog of the authors result about the algorithmic complexity of sets obtained as values of propositional formulas, which was published previously. Also, we introduce the notion of Kolmogorov complexity of finite problems and obtain similar results.Translated from Matematicheskie Zametki, vol. 77, no. 2, 2005, pp. 291–302.Original Russian Text Copyright © 2005 by A. V. Chernov.This revised version was published online in April 2005 with a corrected issue number.     

Generating Functions in the Knapsack Problem

The knapsack problem with Boolean variables and a single constraint is considered. Combinatorial formulas for calculating and estimating the cardinality of the set of feasible solutions and the values of the functional in various cases depending on given parameters of the problem are derived. The coefficients of the objective function and of the constraint vector and the knapsack size are used as parameters. The baseline technique is the classical method of generating functions. The results obtained can be used to estimate the complexity of enumeration and decomposition methods for solving the problem and can also be used as auxiliary procedures in developing such methods.     

Beth’s theorem in cardinality logics

We prove that the Beth definability theorem fails for a comprehensive class of first-order logics with cardinality quantifiers. In particular, we give a counterexample to Beth’s theorem forL(Q), which is finitary first-order logic (with identity) augmented with the quantifier “there exists uncountably many”. This research was partially supported by NSF GP29254.     

Monotonicity and the Expressibility of NP Operators

We investigate why similar extensions of first-order logic using operators (that is, generalized quantifiers) corresponding to NP-complete decision problems apparently differ in expressibility: the logics capture either NP or L^NP. It had been conjectured that the complexity class captured is NP if and only if the operator is monotone. We show that this conjecture is false. However, we provide evidence supporting a revised conjecture involving finite variations of monotone problems. Mathematics Subject Classification: 68Q15, 03D15, 03C13.     

First-order Nilpotent minimum logics: first steps

Inspired by the work done by Baaz et al. (Ann Pure Appl Log 147(1–2): 23–47, 2007; Lecture Notes in Computer Science, vol 4790/2007, pp 77–91, 2007) for first-order Gödel logics, we investigate Nilpotent Minimum logic NM. We study decidability and reciprocal inclusion of various sets of first-order tautologies of some subalgebras of the standard Nilpotent Minimum algebra, establishing also a connection between the validity in an NM-chain of certain first-order formulas and its order type. Furthermore, we analyze axiomatizability, undecidability and the monadic fragments.     

Local convergence of the method of multipliers for variational and optimization problems under the noncriticality assumption

We present an efficient algorithm to find an optimal fiber orientation in composite materials. Within a two-scale setting fiber orientation is regarded as a function in space on the macrolevel. The optimization problem is formulated within a function space setting which makes the imposition of smoothness requirements straightforward and allows for rather general convex objective functionals. We show the existence of a global optimum in the Sobolev space H ¹(Ω). The algorithm we use is a one level optimization algorithm which optimizes with respect to the fiber orientation directly. The costly solve of a big number of microlevel problems is avoided using coordinate transformation formulas. We use an adjoint-based gradient type algorithm, but generalizations to higher-order schemes are straightforward. The algorithm is tested for a prototypical numerical example and its behaviour with respect to mesh independence and dependence on the regularization parameter is studied.     

The location of median paths on grid graphs

In this paper we consider the location of a path shaped facility on a grid graph. In the literature this problem was extensively studied on particular classes of graphs as trees or series-parallel graphs. We consider here the problem of finding a path which minimizes the sum of the (shortest) distances from it to the other vertices of the grid, where the path is also subject to an additional constraint that takes the form either of the length of the path or of the cardinality. We study the complexity of these problems and we find two polynomial time algorithms for two special cases, with time complexity of O(n) and O(nℓ) respectively, where n is the number of vertices of the grid and ℓ is the cardinality of the path to be located. The literature about locating dimensional facilities distinguishes between the location of extensive facilities in continuous spaces and network facility location. We will show that the problems presented here have a close connection with continuous dimensional facility problems, so that the procedures provided can also be useful for solving some open problems of dimensional facilities location in the continuous case.     

Dependence of variables construed as an atomic formula

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].     

Analysis and Solving SAT and MAX-SAT Problems Using an L-partition Approach

In this paper, we study SAT and MAX-SAT using the integer linear programming models and L-partition approach. This approach can be applied to analyze and solve many discrete optimization problems including location, covering, scheduling problems. We describe examples of SAT and MAX-SAT families for which the cardinality of L-covering of the relaxation polytope grows exponentially with the number of variables. These properties are useful in analysis and development of algorithms based on the linear relaxation of the problems. Besides we present the L-class enumeration algorithm for SAT using the L-partition approach. In addition we consider an application of this algorithm to construct exact algorithm and local search algorithms for the MAX-SAT problem.     

A polynomial case of the cardinality-constrained quadratic optimization problem

We propose in this paper a fixed parameter polynomial algorithm for the cardinality-constrained quadratic optimization problem, which is NP-hard in general. More specifically, we prove that, given a problem of size n (the number of decision variables) and s (the cardinality), if the n?k largest eigenvalues of the coefficient matrix of the problem are identical for some 0 < k ≤ n, we can construct a solution algorithm with computational complexity of ${\mathcal{O}\left(n^{2k}\right)}$ . Note that this computational complexity is independent of the cardinality s and is achieved by decomposing the primary problem into several convex subproblems, where the total number of the subproblems is determined by the cell enumeration algorithm for hyperplane arrangement in ${\mathbb{R}^k}$ space.     

Contingent derivatives and regularization for noncoercive inverse problems

Abstract

We study the inverse problem of parameter identification in noncoercive variational problems that commonly appear in applied models. We examine the differentiability of the set-valued parameter-to-solution map using the first-order and the second-order contingent derivatives. We explore the inverse problem using the output least-squares and the modified output least-squares objectives. By regularizing the noncoercive variational problem, we obtain a single-valued regularized parameter-to-solution map and investigate its smoothness and boundedness. We also consider optimization problems using the output least-squares and the modified output least-squares objectives for the regularized variational problem. We give a complete convergence analysis showing that for the output least-squares and the modified output least-squares, the regularized minimization problems approximate the original optimization problems suitably. We also provide the first-order and the second-order adjoint method for the computation of the first-order and the second-order derivatives of the output least-squares objective. We provide discrete formulas for the gradient and the Hessian calculation and present numerical results.     

Enumeration of Lozenge Tilings of Hexagons with Cut-Off Corners

Motivated by the enumeration of a class of plane partitions studied by Proctor and by considerations about symmetry classes of plane partitions, we consider the problem of enumerating lozenge tilings of a hexagon with “maximal staircases” removed from some of its vertices. The case of one vertex corresponds to Proctor's problem. For two vertices there are several cases to consider, and most of them lead to nice enumeration formulas. For three or more vertices there do not seem to exist nice product formulas in general, but in one special situation a lot of factorization occurs, and we pose the problem of finding a formula for the number of tilings in this case.     

Two results in negation-free logic

Negation-free propositional logic (or first-order logic) is clearly less expressive than the corresponding full system with negation. However, we present two complexity results for logic without negation that are no different from those for the original system. First, the problem of determining logical implication between sentences composed solely of conjunctions and disjunctions is shown to be as difficult as that between arbitrary sentences. Second, we show that the problem of determining a minimum satisfying assignment for a propositional formula in negation-free conjunctive normal form, even with no more than two disjuncts per clause, is NP-complete. We also show that unless P = NP, no polynomial time approximation scheme can exist for this problem.     

Complexity of realization by formulas of special form for functions of multivalued logic

A problem of realization by formulas of special form for functions of multivalued logic is considered. For each prime k, k ≠ 2, an upper exponential estimates of complexity for an arbitrary k-valued logic function are obtained.