Modeling of subjective judgments made by a researcher-modeler about the model of the research object

Methods are considered for the mathematic modeling of incomplete and unreliable knowledge about the model M(x) of the research object expressed in the form of subjective judgments made by the researcher-modeler (r-m) about the possible values of the unknown parameter x ∈ X defining the model. The mathematical model of subjective judgments is defined as the space (X, P(X), $Pl^{\tilde x} $ , $Bel^{\tilde x} $ ), in which the indeterminate element (i.el.) $\tilde x$ characterizes (as an undefined propositional variable) the subjective judgments made by the r-m about the validity of each value x ∈ X by the values of measures such as the plausibility $Pl^{\tilde x} $ of the equality $\tilde x$ = x, and belief $Bel^{\tilde x} $ in the inequality $\tilde x$ ≠ x. If there are observational data on the subject, available to the r-m he can use them to construct an empirical estimate of the i.el. $\tilde x$ and an empirical model (X, P(X), $Pl^{\tilde x} $ , $Bel^{\tilde x} $ ) of the subjective judgments about possible values of x ∈ X.     

A note on reverse scheduling with maximum lateness objective

The inverse and reverse counterparts of the single-machine scheduling problem $1||L_{\max }$ are studied in [2], in which the complexity classification is provided for various combinations of adjustable parameters (due dates and processing times) and for five different types of norm: $\ell _{1},\ell _{2},\ell _{\infty },\ell _{H}^{\Sigma } $ , and $\ell _{H}^{\max }$ . It appears that the $O(n^{2})$ -time algorithm for the reverse problem with adjustable due dates contains a flaw. In this note, we present the structural properties of the reverse model, establishing a link with the forward scheduling problem with due dates and deadlines. For the four norms $\ell _{1},\ell _{\infty },\ell _{H}^{\Sigma }$ , and $ \ell _{H}^{\max }$ , the complexity results are derived based on the properties of the corresponding forward problems, while the case of the norm $\ell _{2}$ is treated separately. As a by-product, we resolve an open question on the complexity of problem $1||\sum \alpha _{j}T_{j}^{2}$ .     

On the class of λ-statistically convergent difference sequences of fuzzy numbers

In this study, we introduce the sets $\left[ V,\lambda ,p\right] _{\Updelta }^{{\mathcal{F}}},\left[ C,1,p\right] _{\Updelta }^{{\mathcal{F}}}$ and examine their relations with the classes of $ S_{\lambda }\left( \Updelta ,{\mathcal{F}}\right)$ and $ S_{\mu }\left( \Updelta ,{\mathcal{F}}\right)$ of sequences for the sequences $\left( \lambda _{n}\right)$ and $\left( \mu _{n}\right) , 0<p<\infty $ and difference sequences of fuzzy numbers.     

New types of fuzzy ideals of near-rings

In this paper, we consider the $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy and $(\overline{\in}_{\gamma},\overline{\in}_{\gamma} \vee \; \overline{\hbox{q}}_{\delta})$ -fuzzy subnear-rings (ideals) of a near-ring. Some new characterizations are also given. In particular, we introduce the concepts of (strong) prime $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy ideals of near-rings and discuss the relationship between strong prime $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy ideals and prime $(\in_{\gamma},\in_{\gamma} \vee \; \hbox{q}_{\delta})$ -fuzzy ideals of near-rings.     

An efficient simulation algorithm on Kripke structures

A number of algorithms for computing the simulation preorder (and equivalence) on Kripke structures are available. Let $\varSigma $ denote the state space, ${\rightarrow }$ the transition relation and $P_{\mathrm {sim}}$ the partition of $\varSigma $ induced by simulation equivalence. While some algorithms are designed to reach the best space bounds, whose dominating additive term is $|P_{\mathrm {sim}}|^2$ , other algorithms are devised to attain the best time complexity $O(|P_{\mathrm {sim}}||{\rightarrow }|)$ . We present a novel simulation algorithm which is both space and time efficient: it runs in $O(|P_ {\mathrm {sim}}|^2 \log |P_{\mathrm {sim}}| + |\varSigma |\log |\varSigma |)$ space and $O(|P_{\mathrm {sim}}||{\rightarrow }|\log |\varSigma |)$ time. Our simulation algorithm thus reaches the best space bounds while closely approaching the best time complexity.     

Error Analysis of a Compact ADI Scheme for the 2D Fractional Subdiffusion Equation

In this paper, a Crank–Nicolson-type compact ADI scheme is proposed for solving two-dimensional fractional subdiffusion equation. The unique solvability, unconditional stability and convergence of the scheme are proved rigorously. Two error estimates are presented. One is $\mathcal{O }(\tau ^{\min \{2-\frac{\gamma }{2},\,2\gamma \}}+h_1^4+h^4_2)$ in standard $H^1$ norm, where $\tau $ is the temporal grid size and $h_1,h_2$ are spatial grid sizes; the other is $\mathcal{O }(\tau ^{2\gamma }+h_1^4+h^4_2)$ in $H^1_{\gamma }$ norm, a generalized norm which is associated with the Riemann–Liouville fractional integral operator. Numerical results are presented to support the theoretical analysis.     

Integrated damping parameter and control design in structural systems for \bf{\mathcal{H}^2} and {\mathcal{H}^{\infty}} specifications

The paper presents a linear matrix inequality (LMI)-based approach for the simultaneous optimal design of output feedback control gains and damping parameters in structural systems with collocated actuators and sensors. The proposed integrated design is based on simplified $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ norm upper bound calculations for collocated structural systems. Using these upper bound results, the combined design of the damping parameters of the structural system and the output feedback controller to satisfy closed-loop $\mathcal{H}^2$ or $\mathcal{H}^{\infty}$ performance specifications is formulated as an LMI optimization problem with respect to the unknown damping coefficients and feedback gains. Numerical examples motivated from structural and aerospace engineering applications demonstrate the advantages and computational efficiency of the proposed technique for integrated structural and control design. The effectiveness of the proposed integrated design becomes apparent, especially in very large scale structural systems where the use of classical methods for solving Lyapunov and Riccati equations associated with $\mathcal{H}^2$ and $\mathcal{H}^{\infty}$ designs are time-consuming or intractable.     

\lambda -Statistical convergence of fuzzy numbers and fuzzy functions of order \theta

In this paper, we introduce the concept of $\lambda $ -statistical convergence of order $\theta $ and strong $\lambda $ -summability of order $\theta $ for the sequence of fuzzy numbers. Further the same concept is extended to the sequence of fuzzy functions and introduce the spaces like $S_\lambda ^\theta (\hat{f})$ and $\omega _{\lambda p} ^\theta (\hat{f})$ . Some inclusion relations in those spaces and also the underlying relation between these two spaces are also obtained.     

Improved Approximation of Linear Threshold Functions

We prove two main results on how arbitrary linear threshold functions ${f(x) = {\rm sign}(w \cdot x - \theta)}$ over the n-dimensional Boolean hypercube can be approximated by simple threshold functions. Our first result shows that every n-variable threshold function f is ${\epsilon}$ -close to a threshold function depending only on ${{\rm Inf}(f)^2 \cdot {\rm poly}(1/\epsilon)}$ many variables, where ${{\rm Inf}(f)}$ denotes the total influence or average sensitivity of f. This is an exponential sharpening of Friedgut’s well-known theorem (Friedgut in Combinatorica 18(1):474–483, 1998), which states that every Boolean function f is ${\epsilon}$ -close to a function depending only on ${2^{O({\rm Inf}(f)/\epsilon)}}$ many variables, for the case of threshold functions. We complement this upper bound by showing that ${\Omega({\rm Inf}(f)^2 + 1/\epsilon^2)}$ many variables are required for ${\epsilon}$ -approximating threshold functions. Our second result is a proof that every n-variable threshold function is ${\epsilon}$ -close to a threshold function with integer weights at most ${{\rm poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^{2/3})}.}$ This is an improvement, in the dependence on the error parameter ${\epsilon}$ , on an earlier result of Servedio (Comput Complex 16(2):180–209, 2007) which gave a ${{\rm poly}(n) \cdot 2^{\tilde{O}(1/\epsilon^{2})}}$ bound. Our improvement is obtained via a new proof technique that uses strong anti-concentration bounds from probability theory. The new technique also gives a simple and modular proof of the original result of Servedio (Comput Complex 16(2):180–209, 2007) and extends to give low-weight approximators for threshold functions under a range of probability distributions other than the uniform distribution.     

Arithmetizing Classes Around \textsf{NC} 1 and \textsf{L}

The parallel complexity class $\textsf{NC}$ ¹ has many equivalent models such as polynomial size formulae and bounded width branching programs. Caussinus et al. (J. Comput. Syst. Sci. 57:200–212, 1992) considered arithmetizations of two of these classes, $\textsf{\#NC}$ ¹ and $\textsf{\#BWBP}$ . We further this study to include arithmetization of other classes. In particular, we show that counting paths in branching programs over visibly pushdown automata is in $\textsf{FLogDCFL}$ , while counting proof-trees in logarithmic width formulae has the same power as $\textsf{\#NC}$ ¹. We also consider polynomial-degree restrictions of $\textsf{SC}$ ⁱ , denoted $\textsf{sSC}$ ⁱ , and show that the Boolean class $\textsf{sSC}$ ¹ is sandwiched between $\textsf{NC}$ ¹ and $\textsf{L}$ , whereas $\textsf{sSC}$ ⁰ equals $\textsf{NC}$ ¹. On the other hand, the arithmetic class $\textsf{\#sSC}$ ⁰ contains $\textsf{\#BWBP}$ and is contained in $\textsf{FL}$ , and $\textsf{\#sSC}$ ¹ contains $\textsf{\#NC}$ ¹ and is in $\textsf{SC}$ ². We also investigate some closure properties of the newly defined arithmetic classes.     

Branching Time Logics \mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha } with Operations Until and Since Based on Bundles of Integer Numbers, Logical Consecutions, Deciding Algorithms

This paper is intended as an attempt to describe logical consequence in branching time logics. We study temporal branching time logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ which use the standard operations Until and Next and dual operations Since and Previous (LTL, as standard, uses only Until and Next). Temporal logics $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ are generated by semantics based on Kripke/Hinttikka structures with linear frames of integer numbers $\mathcal {Z}$ with a single node (glued zeros). For $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ , the permissible branching of the node is limited by α (where 1≤α≤ω). We prove that any logic $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ is decidable w.r.t. admissible consecutions (inference rules), i.e. we find an algorithm recognizing consecutions admissible in $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ . As a consequence, it implies that $\mathcal {BTL}^{\mathrm {U,S}}_{\mathrm {N},\mathrm {N}^{-1}}(\mathcal {Z})_{\alpha }$ itself is decidable and solves the satisfiability problem.     

The Rank-Width of Edge-Coloured Graphs

A C-coloured graph is a graph, that is possibly directed, where the edges are coloured with colours from the set C. Clique-width is a complexity measure for C-coloured graphs, for finite sets C. Rank-width is an equivalent complexity measure for undirected graphs and has good algorithmic and structural properties. It is in particular related to the vertex-minor relation. We discuss some possible extensions of the notion of rank-width to C-coloured graphs. There is not a unique natural notion of rank-width for C-coloured graphs. We define two notions of rank-width for them, both based on a coding of C-coloured graphs by ${\mathbb{F}}^{*}$ -graphs— $\mathbb {F}$ -coloured graphs where each edge has exactly one colour from $\mathbb{F}\setminus \{0\},\ \mathbb{F}$ a field—and named respectively $\mathbb{F}$ -rank-width and $\mathbb {F}$ -bi-rank-width. The two notions are equivalent to clique-width. We then present a notion of vertex-minor for $\mathbb{F}^{*}$ -graphs and prove that $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width are characterised by a list of $\mathbb{F}^{*}$ -graphs to exclude as vertex-minors (this list is finite if $\mathbb{F}$ is finite). An algorithm that decides in time O(n ³) whether an $\mathbb{F}^{*}$ -graph with n vertices has $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) at most k, for fixed k and fixed finite field $\mathbb{F}$ , is also given. Graph operations to check MSOL-definable properties on $\mathbb{F}^{*}$ -graphs of bounded $\mathbb{F}$ -rank-width (resp. $\mathbb{F}$ -bi-rank-width) are presented. A specialisation of all these notions to graphs without edge colours is presented, which shows that our results generalise the ones in undirected graphs.     

Quantum search algorithm for set operation

The operations of data set, such as intersection, union and complement, are the fundamental calculation in mathematics. It’s very significant that designing fast algorithm for set operation. In this paper, the quantum algorithm for calculating intersection set ${\text{C}=\text{A}\cap \text{B}}$ is presented. Its runtime is ${O\left( {\sqrt{\left| A \right|\times \left| B \right|\times \left|C \right|}}\right)}$ for case ${\left| C \right|\neq \phi}$ and ${O\left( {\sqrt{\left| A \right|\times \left| B \right|}}\right)}$ for case ${\left| C \right|=\phi}$ (i.e. C is empty set), while classical computation needs O (|A| × |B|) steps of computation in general, where |.| denotes the size of set. The presented algorithm is the combination of Grover’s algorithm, classical memory and classical iterative computation, and the combination method decrease the complexity of designing quantum algorithm. The method can be used to design other set operations as well.     

Completions of cut systems in Q-sets

Let $ Q$ be a complete residuated lattice. Let $\text {SetR}(Q)$ be the category of sets with similarity relations with values in $ Q$ (called $ Q$ -sets), which is an analogy of the category of classical sets with relations as morphisms. A cut in an $ Q$ -set $(A,\delta )$ is a system $(C_{\alpha })_{\alpha \in Q}$ , where $C_{\alpha }$ are subsets of $A\times Q$ . It is well known that in the category $\text {SetR}(Q)$ , there is a close relation between special cuts (called f-cuts) in an $ Q$ -set on one hand and fuzzy sets in the same $ Q$ -set, on the other hand. Moreover, there exists a completion procedure according to which any cut $(C_{\alpha })_{\alpha }$ can be extended onto an f-cut $(\overline{C_{\alpha }})_{\alpha }$ . In the paper, we prove that the completion procedure is, in some sense, the best possible. This will be expressed by the theorem which states that the category of f-cuts is a full reflective subcategory in the category of cuts.     

On the Exact Complexity of Evaluating Quantified k -CNF

We relate the exponential complexities 2 ^s(k)n of $\textsc {$k$-sat}$ and the exponential complexity $2^{s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))n}$ of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ (the problem of evaluating quantified formulas of the form $\forall\vec{x} \exists\vec{y} \textsc {F}(\vec {x},\vec{y})$ where F is a 3-cnf in $\vec{x}$ variables and $\vec{y}$ variables) and show that s(∞) (the limit of s(k) as k→∞) is at most $s(\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf}))$ . Therefore, if we assume the Strong Exponential-Time Hypothesis, then there is no algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ running in time 2 ^cn with c<1. On the other hand, a nontrivial exponential-time algorithm for $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ would provide a $\textsc {$k$-sat}$ solver with better exponent than all current algorithms for sufficiently large k. We also show several syntactic restrictions of the evaluation problem $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ have nontrivial algorithms, and provide strong evidence that the hardest cases of $\textsc {eval}(\mathrm {\varPi }_{2} 3\textsc {-cnf})$ must have a mixture of clauses of two types: one universally quantified literal and two existentially quantified literals, or only existentially quantified literals. Moreover, the hardest cases must have at least n?o(n) universally quantified variables, and hence only o(n) existentially quantified variables. Our proofs involve the construction of efficient minimally unsatisfiable $\textsc {$k$-cnf}$ s and the application of the Sparsification lemma.     

Simple characterization of strict residuated lattices with an involutive negation

We consider property of strict residuated lattices (SRL-algebras) with a new involutive negation $\lnot, $ called here by SRL $_{\lnot }$ -algebras, and give a simple characterization of SRL $_{\lnot }$ -algebras. We also prove a prime filter theorem of SRL $_{\lnot }$ -algebras, from which we conclude that every linearly ordered SRL $_{\lnot }$ -algebra is simple. As a corollary to this fact, we have a well-known result that every SML $_{\lnot }$ -algebra (SBL $_{\lnot }$ -algebra) is a subdirect product of linearly ordered SML $_{\lnot }$ -algebras (SBL $_{\lnot }$ -algebras).     

Polyadic tense \theta-valued \Lukasiewicz–Moisil algebras

In this paper we introduce the polyadic tense $\theta$ -valued $\L$ ukasiewicz–Moisil algebras (=polyadic tense $\hbox{LM}_{\theta}$ -algebras), as a common generalization of polyadic tense Boolean algebras and polyadic $\hbox{LM}_{\theta}$ -algebras. Our main result is a representation theorem for polyadic tense $\hbox{LM}_{\theta}$ -algebras.     

On reducing factorization to the discrete logarithm problem modulo a composite

The discrete logarithm problem modulo a composite??abbreviate it as DLPC??is the following: given a (possibly) composite integer n??? 1 and elements ${a, b \in \mathbb{Z}_n^*}$ , determine an ${x \in \mathbb{N}}$ satisfying a ^x ?=?b if one exists. The question whether integer factoring can be reduced in deterministic polynomial time to the DLPC remains open. In this paper we consider the problem ${{\rm DLPC}_\varepsilon}$ obtained by adding in the DLPC the constraint ${x\le (1-\varepsilon)n}$ , where ${\varepsilon}$ is an arbitrary fixed number, ${0 < \varepsilon\le\frac{1}{2}}$ . We prove that factoring n reduces in deterministic subexponential time to the ${{\rm DLPC}_\varepsilon}$ with ${O_\varepsilon((\ln n)^2)}$ queries for moduli less or equal to n.     

Pseudorandom generators for CC0[p] and the Fourier spectrum of low-degree polynomials over finite fields

In this paper, we give the first construction of a pseudorandom generator, with seed length O(log n), for CC⁰[p], the class of constant-depth circuits with unbounded fan-in MOD _p gates, for some prime p. More accurately, the seed length of our generator is O(log n) for any constant error ${\epsilon > 0}$ . In fact, we obtain our generator by fooling distributions generated by low-degree polynomials, over ${\mathbb{F}_p}$ , when evaluated on the Boolean cube. This result significantly extends previous constructions that either required a long seed (Luby et al. 1993) or could only fool the distribution generated by linear functions over ${\mathbb{F}_p}$ , when evaluated on the Boolean cube (Lovett et al. 2009; Meka & Zuckerman 2009). En route of constructing our PRG, we prove two structural results for low-degree polynomials over finite fields that can be of independent interest.

1. Let f be an n-variate degree d polynomial over ${\mathbb{F}_p}$ . Then, for every ${\epsilon > 0}$ , there exists a subset ${S \subset [n]}$ , whose size depends only on d and ${\epsilon}$ , such that ${\sum_{\alpha \in \mathbb{F}_p^n: \alpha \ne 0, \alpha_S=0}|\hat{f}(\alpha)|^2 \leq \epsilon}$ . Namely, there is a constant size subset S such that the total weight of the nonzero Fourier coefficients that do not involve any variable from S is small.
2. Let f be an n-variate degree d polynomial over ${\mathbb{F}_p}$ . If the distribution of f when applied to uniform zero–one bits is ${\epsilon}$ -far (in statistical distance) from its distribution when applied to biased bits, then for every ${\delta > 0}$ , f can be approximated over zero–one bits, up to error δ, by a function of a small number (depending only on ${\epsilon,\delta}$ and d) of lower degree polynomials.

     

Fast Polynomial-Space Algorithms Using Inclusion-Exclusion

Given a graph with n vertices, k terminals and positive integer weights not larger than c, we compute a minimum Steiner Tree in $\mathcal{O}^{\star}(2^{k}c)$ time and $\mathcal{O}^{\star}(c)$ space, where the $\mathcal{O}^{\star}$ notation omits terms bounded by a polynomial in the input-size. We obtain the result by defining a generalization of walks, called branching walks, and combining it with the Inclusion-Exclusion technique. Using this combination we also give $\mathcal{O}^{\star}(2^{n})$ -time polynomial space algorithms for Degree Constrained Spanning Tree, Maximum Internal Spanning Tree and #Spanning Forest with a given number of components. Furthermore, using related techniques, we also present new polynomial space algorithms for computing the Cover Polynomial of a graph, Convex Tree Coloring and counting the number of perfect matchings of a graph.