In All But Finitely Many Possible Worlds: Model-Theoretic Investigations on ‘<Emphasis Type="Italic">Overwhelming Majority</Emphasis>’ Default Conditionals

Defeasible conditionals are statements of the form ‘if A then normally B’. One plausible interpretation introduced in nonmonotonic reasoning dictates that (\(A\Rightarrow B\)) is true iff B is true in ‘most’ A-worlds. In this paper, we investigate defeasible conditionals constructed upon a notion of ‘overwhelming majority’, defined as ‘truth in a cofinite subset of \(\omega \)’, the first infinite ordinal. One approach employs the modal logic of the frame \((\omega , <)\), used in the temporal logic of discrete linear time. We introduce and investigate conditionals, defined modally over \((\omega , <)\); several modal definitions of the conditional connective are examined, with an emphasis on the nonmonotonic ones. An alternative interpretation of ‘majority’ as sets cofinal (in \(\omega \)) rather than cofinite (subsets of \(\omega \)) is examined. For these modal approaches over \((\omega , <)\), a decision procedure readily emerges, as the modal logic \({\mathbf {K4DLZ}}\) of this frame is well-known and a translation of the conditional sentences can be mechanically checked for validity; this allows also for a quick proof of \(\mathsf {NP}\)-completeness of the satisfiability problem for these logics. A second approach employs the conditional version of Scott-Montague semantics, in the form of \(\omega \)-many possible worlds, endowed with neighborhoods populated by collections of cofinite subsets of \(\omega \). This approach gives rise to weak conditional logics, as expected. The relative strength of the conditionals introduced is compared to (the conditional logic ‘equivalent’ of) KLM logics and other conditional logics in the literature.     

Mixed <Emphasis Type="Italic">H</Emphasis><Subscript>2</Subscript>/<Emphasis Type="Italic">H</Emphasis><Subscript>∞</Subscript> control for linear infinite-dimensional systems

In this paper, we consider mixed H ₂/H _∞ control problems for linear infinite-dimensional systems. The first part considers the state feedback control for the H ₂/H _∞ control problems of linear infinite-dimensional systems. The cost horizon can be infinite or finite time. The solutions of the H ₂/H _∞ control problem for linear infinitedimensional systems are presented in terms of the solutions of the coupled operator Riccati equations and coupled differential operator Riccati equations. The second part addresses the observer-based H ₂/H _∞ control of linear infinite-dimensional systems with infinite horizon and finite horizon costs. The solutions for the observer-based H ₂/H _∞ control problem of linear infinite-dimensional systems are represented in terms of the solutions of coupled operator Riccati equations. The first-order partial differential system examples are presented for illustration. In particular, for these examples, the Riccati equations are represented in terms of the coefficients of first-order partial differential systems.     

Indefinite summation of rational functions with additional minimization of the summable part

An algorithm of indefinite summation of rational functions is proposed. For a given function f(x), it constructs a pair of rational functions g(x) and r(x) such that f(x) = g(x + 1) ? g(x) + r(x), where the degree of the denominator of r(x) is minimal, and, when this condition is satisfied, the degree of the denominator of g(x) is also minimal.     

Cryptanalysis of an MOR cryptosystem based on a finite associative algebra基于有限结合代数的 MOR 公钥密码安全性分析

The Shor algorithm is effective for public-key cryptosystems based on an abelian group. At CRYPTO 2001, Paeng (2001) presented a MOR cryptosystem using a non-abelian group, which can be considered as a candidate scheme for post-quantum attack. This paper analyses the security of a MOR cryptosystem based on a finite associative algebra using a quantum algorithm. Specifically, let L be a finite associative algebra over a finite field F. Consider a homomorphism φ: Aut(L) → Aut(H)×Aut(I), where I is an ideal of L and H ? L/I. We compute dim Im(φ) and dim Ker(φ), and combine them by dim Aut(L) = dim Im(φ)+dim Ker(φ). We prove that Im(φ) = Stab_Comp(H,I)(μ + B²(H, I)) and Ker(φ) ? Z¹(H, I). Thus, we can obtain dim Im(φ), since the algorithm for the stabilizer is a standard algorithm among abelian hidden subgroup algorithms. In addition, Z¹(H, I) is equivalent to the solution space of the linear equation group over the Galois fields GF(p), and it is possible to obtain dim Ker(φ) by the enumeration theorem. Furthermore, we can obtain the dimension of the automorphism group Aut(L). When the map ? ∈ Aut(L), it is possible to effectively compute the cyclic group 〈?〉 and recover the private key a. Therefore, the MOR scheme is insecure when based on a finite associative algebra in quantum computation.     

On Fixed Cost k-Flow Problems

In the Fixed Cost k-Flow problem, we are given a graph G = (V, E) with edge-capacities {u _e ∣e ∈ E} and edge-costs {c _e ∣e ∈ E}, source-sink pair s, t ∈ V, and an integer k. The goal is to find a minimum cost subgraph H of G such that the minimum capacity of an st-cut in H is at least k. By an approximation-preserving reduction from Group Steiner Tree problem to Fixed Cost k-Flow, we obtain the first polylogarithmic lower bound for the problem; this also implies the first non-constant lower bounds for the Capacitated Steiner Network and Capacitated Multicommodity Flow problems. We then consider two special cases of Fixed Cost k-Flow. In the Bipartite Fixed-Cost k-Flow problem, we are given a bipartite graph G = (A ∪ B, E) and an integer k > 0. The goal is to find a node subset S ? A ∪ B of minimum size |S| such G has k pairwise edge-disjoint paths between S ∩ A and S ∩ B. We give an \(O(\sqrt {k\log k})\) approximation for this problem. We also show that we can compute a solution of optimum size with Ω(k/polylog(n)) paths, where n = |A| + |B|. In the Generalized-P2P problem we are given an undirected graph G = (V, E) with edge-costs and integer charges {b _v : v ∈ V}. The goal is to find a minimum-cost spanning subgraph H of G such that every connected component of H has non-negative charge. This problem originated in a practical project for shift design [11]. Besides that, it generalizes many problems such as Steiner Forest, k-Steiner Tree, and Point to Point Connection. We give a logarithmic approximation algorithm for this problem. Finally, we consider a related problem called Connected Rent or Buy Multicommodity Flow and give a log^3+?? n approximation scheme for it using Group Steiner Tree techniques.     

A New Primal–Dual Algorithm for Minimizing the Sum of Three Functions with a Linear Operator

In this paper, we propose a new primal–dual algorithm for minimizing \(f({\mathbf {x}})+g({\mathbf {x}})+h({\mathbf {A}}{\mathbf {x}})\), where f, g, and h are proper lower semi-continuous convex functions, f is differentiable with a Lipschitz continuous gradient, and \({\mathbf {A}}\) is a bounded linear operator. The proposed algorithm has some famous primal–dual algorithms for minimizing the sum of two functions as special cases. E.g., it reduces to the Chambolle–Pock algorithm when \(f=0\) and the proximal alternating predictor–corrector when \(g=0\). For the general convex case, we prove the convergence of this new algorithm in terms of the distance to a fixed point by showing that the iteration is a nonexpansive operator. In addition, we prove the O(1 / k) ergodic convergence rate in the primal–dual gap. With additional assumptions, we derive the linear convergence rate in terms of the distance to the fixed point. Comparing to other primal–dual algorithms for solving the same problem, this algorithm extends the range of acceptable parameters to ensure its convergence and has a smaller per-iteration cost. The numerical experiments show the efficiency of this algorithm.     

Making Doubling Metrics Geodesic

The starting point of our research is the following problem: given a doubling metric ?=(V,d), can one (efficiently) find an unweighted graph G′=(V′,E′) with V?V′ whose shortest-path metric d′ is still doubling, and which agrees with d on V×V? While it is simple to show that the answer to the above question is negative if distances must be preserved exactly. However, allowing a (1+ε) distortion between d and d′ enables us bypass this hurdle, and obtain an unweighted graph G′ with doubling dimension at most a factor O(log?ε ^?1) times the doubling dimension of G.More generally, this paper gives algorithms that construct graphs G′ whose convex (or geodesic) closure has doubling dimension close to that of ?, and the shortest-path distances in G′ closely approximate those of ? when restricted to V×V. Similar results are shown when the metric ? is an additive (tree) metric and the graph G′ is restricted to be a tree.     

Redshift in the model of embedded spaces

The non-configurational geometrization of the electromagnetic field can be realized using the Model of Embedded Spaces (MES). This model assumes the existence of proper 4D space-time manifolds of particles with a nonzero rest mass and declares that physical space-time is the metric result of the dynamic embedding of these manifolds: the value of the partial contribution of the element manifold is determined by element interactions. The space of the model is provided with a Riemann-like geometry, whose differential formalism is described by a generalization of the gradient operator ?/?x ⁱ → ?/?x ⁱ + 2u ^k ?²/?x[ ⁱ ?u ^k ], where u ⁱ = dx ⁱ /ds is a matter velocity. In the paper, the redshift effect existing in the space of MES is considered, and its electromagnetic component is analyzed. It is shown that for cold matter of the modern Universe this component reduces to a shift in electric fields and is described by the expression \(\Delta {\omega _e}/\omega \simeq \mp \sqrt k \Delta {\varphi _e}/{c^2} = \mp 0.861 \cdot {10^{ - 21}}\Delta {\varphi _e}\left( V \right)\), where the potential is measured in volts and the sign must be determined experimentally. Testing of the effect is the “experimentum crusis” for MES.     

Almost cover-free codes

We say that an s-subset of codewords of a code X is (s, l)-bad if X contains l other codewords such that the conjunction of these l words is covered by the disjunction of the words of the s-subset. Otherwise, an s-subset of codewords of X is said to be (s, l)-bad. A binary code X is called a disjunctive (s, l) cover-free (CF) code if X does not contain (s, l)-bad subsets. We consider a probabilistic generalization of (s, l) CF codes: we say that a binary code is an (s, l) almost cover-free (ACF) code if almost all s-subsets of its codewords are (s, l)-good. The most interesting result is the proof of a lower and an upper bound for the capacity of (s, l) ACF codes; the ratio of these bounds tends as s→∞ to the limit value log₂ e/(le).     

On the Smallest Size of an Almost Complete Subset of a Conic in PG(2, <Emphasis Type="Italic">q</Emphasis>) and Extendability of Reed–Solomon Codes

Abstract—In the projective plane PG(2, q), a subset S of a conic C is said to be almost complete if it can be extended to a larger arc in PG(2, q) only by the points of C \ S and by the nucleus of C when q is even. We obtain new upper bounds on the smallest size t(q) of an almost complete subset of a conic, in particular,

$$t(q) < \sqrt {q(3lnq + lnlnq + ln3)} + \sqrt {\frac{q}{{3\ln q}}} + 4 \sim \sqrt {3q\ln q} ,t(q) < 1.835\sqrt {q\ln q.} $$

The new bounds are used to extend the set of pairs (N, q) for which it is proved that every normal rational curve in the projective space PG(N, q) is a complete (q+1)-arc, or equivalently, that no [q+1,N+1, q?N+1]_q generalized doubly-extended Reed–Solomon code can be extended to a [q + 2,N + 1, q ? N + 2]_q maximum distance separable code.

     

Property-Preserving Data Reconstruction

We initiate a new line of investigation into online property-preserving data reconstruction. Consider a dataset which is assumed to satisfy various (known) structural properties; e.g., it may consist of sorted numbers, or points on a manifold, or vectors in a polyhedral cone, or codewords from an error-correcting code. Because of noise and errors, however, an (unknown) fraction of the data is deemed unsound, i.e., in violation with the expected structural properties. Can one still query into the dataset in an online fashion and be provided data that is always sound? In other words, can one design a filter which, when given a query to any item I in the dataset, returns a sound item J that, although not necessarily in the dataset, differs from I as infrequently as possible. No preprocessing should be allowed and queries should be answered online.We consider the case of a monotone function. Specifically, the dataset encodes a function f:{1,…,n}?? R that is at (unknown) distance ε from monotone, meaning that f can—and must—be modified at ε n places to become monotone.Our main result is a randomized filter that can answer any query in O(log?² nlog? log?n) time while modifying the function f at only O(ε n) places. The amortized time over n function evaluations is O(log?n). The filter works as stated with probability arbitrarily close to 1. We provide an alternative filter with O(log?n) worst case query time and O(ε nlog?n) function modifications. For reconstructing d-dimensional monotone functions of the form f:{1,…,n} ^d ? ? R, we present a filter that takes (2 ^O(d)(log?n)^4d?2log?log?n) time per query and modifies at most O(ε n ^d ) function values (for constant d).     

Semantically-Guided Goal-Sensitive Reasoning: Inference System and Completeness

We present a new method for clausal theorem proving, named SGGS from semantically-guided goal-sensitive reasoning. SGGS generalizes to first-order logic the conflict-driven clause learning (CDCL) procedure for propositional satisfiability. Starting from an initial interpretation, used for semantic guidance, SGGS employs a sequence of constrained clauses to represent a candidate model, instance generation to extend it, resolution and other inferences to explain and solve conflicts, amending the model. We prove that SGGS is refutationally complete and model complete in the limit, regardless of initial interpretation. SGGS is also goal sensitive, if the initial interpretation is properly chosen, and proof confluent, because it repairs the current model without undoing steps by backtracking. Thus, SGGS is a complete first-order method that is simultaneously model-based à la CDCL, semantically-guided, goal-sensitive, and proof confluent.     

Propelinear codes related to some classes of optimal codes

A code is said to be propelinear if its automorphism group contains a subgroup that acts regularly on codewords. We show propelinearity of complements of cyclic codes C _1,i , (i, 2 ^m ? 1) = 1, of length n = 2 ^m ? 1, including the primitive two-error-correcting BCH code, to the Hamming code; the Preparata code to the Hamming code; the Goethals code to the Preparata code; and the Z₄-linear Preparata code to the Z₄-linear perfect code.     

The weight-constrained maximum-density subtree problem and related problems in trees

Given a tree T=(V,E) of n nodes such that each node v is associated with a value-weight pair (val _v ,w _v ), where value val _v is a real number and weight w _v is a non-negative integer, the density of T is defined as \(\frac{\sum_{v\in V}{\mathit{val}}_{v}}{\sum_{v\in V}w_{v}}\). A subtree of T is a connected subgraph (V′,E′) of T, where V′?V and E′?E. Given two integers w _min? and w _max?, the weight-constrained maximum-density subtree problem on T is to find a maximum-density subtree T′=(V′,E′) satisfying w _min?≤∑_v∈V′ w _v ≤w _max?. In this paper, we first present an O(w _max? n)-time algorithm to find a weight-constrained maximum-density path in a tree T, and then present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T. Finally, given a node subset S?V, we also present an O(w _max? ² n)-time algorithm to find a weight-constrained maximum-density subtree in T which covers all the nodes in S.     

Negation-Limited Complexity of Parity and Inverters

In negation-limited complexity, one considers circuits with a limited number of NOT gates, being motivated by the gap in our understanding of monotone versus general circuit complexity, and hoping to better understand the power of NOT gates. We give improved lower bounds for the size (the number of AND/OR/NOT) of negation-limited circuits computing Parity and for the size of negation-limited inverters. An inverter is a circuit with inputs x ₁,…,x _n and outputs ¬ x ₁,…,¬ x _n . We show that: (a) for n=2 ^r ?1, circuits computing Parity with r?1 NOT gates have size at least 6n?log?₂(n+1)?O(1), and (b) for n=2 ^r ?1, inverters with r NOT gates have size at least 8n?log?₂(n+1)?O(1). We derive our bounds above by considering the minimum size of a circuit with at most r NOT gates that computes Parity for sorted inputs x ₁≥???≥x _n . For an arbitrary r, we completely determine the minimum size. It is 2n?r?2 for odd n and 2n?r?1 for even n for ?log?₂(n+1)??1≤r≤n/2, and it is ?3n/2??1 for r≥n/2. We also determine the minimum size of an inverter for sorted inputs with at most r NOT gates. It is 4n?3r for ?log?₂(n+1)?≤r≤n. In particular, the negation-limited inverter for sorted inputs due to Fischer, which is a core component in all the known constructions of negation-limited inverters, is shown to have the minimum possible size. Our fairly simple lower bound proofs use gate elimination arguments in a somewhat novel way.     

Guaranteed strategies for escaping encirclement

This paper considers a conflict situation on the plane as follows. A fast evader E has to break out the encirclement of slow pursuers P _{j1,...,j n} = {P _j1,..., P _jn }, n ≥ 3, with a miss distance not smaller than r ≥ 0. First, we estimate the minimum guaranteed miss distance from E to a pursuer P _a , a ∈ {j ₁,..., j _n }, when the former moves along a given straight line. Then the obtained results are used to calculate the guaranteed estimates to a group of two pursuers P _b,c = {P _b , P _c }, b, c ∈ {j ₁,..., j _n }, b ≠ c, when E maneuvers by crossing the rectilinear segment P _b P _c , and the state passes to the domain of the game space where E applies a strategy under which the miss distance to any of the pursuers is not decreased. In addition, we describe an approach to the games with a group of pursuers P _{j1,... jn} , n ≥ 3, in which E seeks to break out the encirclement by passing between two pursuers P _b and P _c , entering the domain of the game space where E can increase the miss distance to all pursuers by straight motion. By comparing the guaranteed miss distances with r for all alternatives b, c ∈ {j ₁,..., j _n }, b ≠ c, and a ? {b, c}, it is possible to choose the best alternative and also to extract the histories of the game in which the designed evasion strategies guarantee a safe break out from the encirclement.     

On (<Emphasis Type="Italic">a</Emphasis>, <Emphasis Type="Italic">d</Emphasis> )-Distance Anti-Magic and 1-Vertex Bimagic Vertex Labelings of Certain Types of Graphs

The results for the corona P _n ?°?P₁ are generalized, which make it possible to state that P _n ?°?P₁ is not an ( a, d)-distance antimagic graph for arbitrary values of a and d. A condition for the existence of an ( a, d)-distance antimagic labeling of a hypercube Q _n is obtained. Functional dependencies are found that generate this type of labeling for Q _n . It is proved by the method of mathematical induction that Q _n is a (2 ⁿ ?+?n???1,?n???2) -distance antimagic graph. Three types of graphs are defined that do not allow a 1-vertex bimagic vertex labeling. A relation between a distance magic labeling of a regular graph G and a 1-vertex bimagic vertex labeling of G?∪?G is established.     

Continuity of the Effective Delay Operator for Networks Based on the Link Delay Model

This paper is concerned with a dynamic traffic network performance model, known as dynamic network loading (DNL), that is frequently employed in the modeling and computation of analytical dynamic user equilibrium (DUE). As a key component of continuous-time DUE models, DNL aims at describing and predicting the spatial-temporal evolution of traffic flows on a network that is consistent with established route and departure time choices of travelers, by introducing appropriate dynamics to flow propagation, flow conservation, and travel delays. The DNL procedure gives rise to the path delay operator, which associates a vector of path flows (path departure rates) with the corresponding path travel costs. In this paper, we establish strong continuity of the path delay operator for networks whose arc flows are described by the link delay model (Friesz et al., Oper Res 41(1):80–91, 1993; Carey, Networks and Spatial Economics 1(3):349–375, 2001). Unlike the result established in Zhu and Marcotte (Transp Sci 34(4):402–414, 2000), our continuity proof is constructed without assuming a priori uniform boundedness of the path flows. Such a more general continuity result has a few important implications to the existence of simultaneous route-and-departure-time DUE without a priori boundedness of path flows, and to any numerical algorithm that allows convergence to be rigorously analyzed.     

One-Nonterminal Conjunctive Grammars over a Unary Alphabet

Systems of equations of the form X _i =φ _i (X ₁,…,X _n ) (1≤ i ≤ n) are considered, in which the unknowns are sets of natural numbers. Expressions φ _i may contain the operations of union, intersection and elementwise addition \(S+T=\{m+n\mid m\in S\), n∈T}. A system with an EXPTIME-complete least solution is constructed in the paper through a complete arithmetization of EXPTIME-completeness. At the same time, it is established that least solutions of all such systems are in EXPTIME. The general membership problem for these equations is proved to be EXPTIME-complete. Among the consequences of the result is EXPTIME-completeness of the compressed membership problem for conjunctive grammars.     

Complexity of ideals in finite semigroups and finite-state machines

# _G (S) denotes the complexity of a finite semigroup as introduced by Krohn and Rhodes. IfI is a maximal ideal or maximal left ideal of a semigroupS, then# _G (I) ? # _G (S) ? # _G (I) + 1. Thus, ifV is an ideal ofS with# _G (S) = n ? k = # _G (V), then there is a chain of ideals ofS

$$V = V_k \subset V_{k + 1} \subset ... \subset V_n \subseteq S$$