Search

For more than two decades, proving or refuting the following statement has remained a challenging open problem in the theory of secret sharing schemes (SSSs): every ideal access structure admits an ideal perfect multi-linear SSS. The class of group-characterizable (GC) SSSs include the multi-linear ones. Hence, if the above statement is true, then so is the following weaker statement: every ideal access structure admits an ideal perfect GC SSS. One contribution of this paper is to show that ideal SSSs are not necessarily GC. Our second contribution is to study the above two statements with respect to several variations of weakly-ideal access structures. Recently, Mejia and Montoya studied ideal access structures that admit ideal multi-linear schemes and provided a classification-like theorem for them. We additionally present some tools that are useful to extend their result.

Convolutional transform learning (CTL), learning filters by minimizing the data fidelity loss function in an unsupervised way, is becoming very pervasive, resulting from keeping the best of both worlds: the benefit of unsupervised learning and the success of the convolutional neural network. There have been growing interests in developing efficient CTL algorithms. However, developing a convergent and accelerated CTL algorithm with accurate representations simultaneously with proper sparsity is an open problem. This article presents a new CTL framework with a log regularizer that can not only obtain accurate representations but also yield strong sparsity. To efficiently address our nonconvex composite optimization, we propose to employ the proximal difference of the convex algorithm (PDCA) which relies on decomposing the nonconvex regularizer into the difference of two convex parts and then optimizes the convex subproblems. Furthermore, we introduce the extrapolation technology to accelerate the algorithm, leading to a fast and efficient CTL algorithm. In particular, we provide a rigorous convergence analysis for the proposed algorithm under the accelerated PDCA. The experimental results demonstrate that the proposed algorithm can converge more stably to desirable solutions with lower approximation error and simultaneously with stronger sparsity and, thus, learn filters efficiently. Meanwhile, the convergence speed is faster than the existing CTL algorithms.

The eternal vertex cover problem is a variant of the classical vertex cover problem defined in terms of an infinite attacker–defender game played on a graph. In each round of the game, the defender reconfigures guards from one vertex cover to another in response to a move by the attacker. The minimum number of guards required in any winning strategy of the defender when this game is played on a graph G is the eternal vertex cover number of G , denoted by evc ( G ) . It is known that given a graph G and an integer k , checking whether evc ( G ) ≤ k is NP-hard. Further, it is known that for any graph G , mvc ( G ) ≤ evc ( G ) ≤ 2 mvc ( G ) , where mvc ( G ) is the vertex cover number of G . Though a characterization is known for graphs for which evc ( G ) = 2 mvc ( G ) , a characterization of graphs for which evc ( G ) = mvc ( G ) remained as an open problem, since 2009. We achieve such a characterization for a class of graphs that includes chordal graphs and internally triangulated planar graphs. For biconnected chordal graphs, our characterization leads to a polynomial time algorithm for precisely determining evc ( G ) and an algorithm for determining a safe strategy for guard movement in each round of the game using only evc ( G ) guards. Though the eternal vertex cover problem is only known to be in PSPACE in general, it follows from our new characterization that the problem is in NP for locally connected graphs, a graph class which includes all biconnected internally triangulated planar graphs. We also provide reductions establishing NP-completeness of the problem for biconnected internally triangulated planar graphs. As far as we know, this is the first NP-completeness result known for the problem for any graph class.

The law of importation between fuzzy implications and conjunctions is an important property in both the theory and the application of fuzzy logic. Although many interesting results have been reported in the literature, the related open problem of finding all possible pairs of implications and conjunctions satisfying the law of importation has not been fully solved. As a continuation of two articles S. Massanet et al. (2018) [23] ; S. Massanet et al. (2018) [24] , this article aims to characterize fuzzy implication solutions with a continuous natural negation to the law of importation with respect to a fixed conjunctive uninorm having continuous underlying operators in several cases. Such solutions for the cases where the continuous underlying triangular norm and triangular conorm of a prefixed uninorm are idempotent or Archimedean are completely characterized, and the solutions for the cases where the continuous underlying operators are given by ordinal sums are characterized under some additional assumptions. Finally, some comments on relations to recent independent work W.-H. Li and F. Qin (2021) [25] are given. These two independent articles will go a further step towards answering the open problem regarding the law of importation.

Scheduling the recharging of electric vehicle fleets under different scenarios is an important but open problem. One important scenario is that vehicles travel at different speeds in different periods since traffic congestion is common in urban areas nowadays. Therefore, in this article, a novel time-dependent electric vehicle routing problem with congestion tolls is proposed. If a vehicle enters a peak period, a fixed congestion toll needs to be paid in this problem. A mixed integer linear programming model is established and an adaptive large neighborhood search (ALNS) heuristic is designed to solve the model. The model and solving method are validated and evaluated extensively with benchmark instances. Results indicate that a certain level of congestion tolls could prevent vehicles from entering peak periods and relieve road congestions significantly. Furthermore, the ALNS heuristic could provide much better solutions for the problem than typical optimization software, such as Gurobi, in much shorter running time.

This paper constructs a conjunction and a disjunction operator for type-2 fuzzy sets that cannot be expressed by the sup-t-norm extension principle applied to conjunction and disjunction of type-1 fuzzy sets by means of t-norms and t-conorms on the unit interval. This result answers affirmatively an open problem posed by Hernandez et al. in 2015. The duality between the set-theoretic operators for type-2 fuzzy sets is obtained from the duality of set-theoretic operations on type-1 fuzzy sets.

Lane detection is one of the indispensable and key elements of self-driving environmental perception. Many lane detection models have been proposed, solving lane detection under challenging conditions, including intersection merging and splitting, curves, boundaries, occlusions and combinations of scene types. Nevertheless, lane detection will remain an open problem for some time to come. The ability to cope well with those challenging scenes impacts greatly the applications of lane detection on advanced driver assistance systems (ADASs). In this paper, a spatio-temporal network with double Convolutional Gated Recurrent Units (ConvGRUs) is proposed to address lane detection in challenging scenes. Both of ConvGRUs have the same structures, but different locations and functions in our network. One is used to extract the information of the most likely low-level features of lane markings. The extracted features are input into the next layer of the end-to-end network after concatenating them with the outputs of some blocks. The other one takes some continuous frames as its input to process the spatio-temporal driving information. Extensive experiments on the large-scale TuSimple lane marking challenge dataset and Unsupervised LLAMAS dataset demonstrate that the proposed model can effectively detect lanes in the challenging driving scenes. Our model can outperform the state-of-the-art lane detection models., Comment: 13 pages, 9 figures, 8 tables, Accepted by IEEE Transactions on Intelligent Transportation Systems

This paper further develops the study of construction of uninorms on bounded lattices. First, by using the fact that triangular norms (t-norms) and triangular conorms (t-conorms) on an arbitrary bounded lattice always exist, we present two new constructions of uninorms on an arbitrary bounded lattice L with an additional constraint on the neutral element. In addition, some illustrative examples for the new constructions of uninorms on bounded lattices are provided. Then, we illustrate how our new construction methods are different from some existing methods for the construction of uninorms on bounded lattices. Finally, we provide an answer to the open problem presented by Cayli.

The law of importation, given by the equality (x^y)→z ≈ (x→(y→z)), is a tautology in classical logic and has been proved to be widely used in approximate reasoning and image processing. Some open problems of fuzzy implication dealing with the law of importation were suggested on 8th international conference on Fuzzy Set Theory and Applications (FSTA 2006). In this paper, we partially solve one open problem associated with this property. Specifically, we mainly devote ourselves to solving the general form of the law of importation I(U(x, y), z) = I(x, I(y, z)), where I is a fuzzy implication and U is a conjunctive uninorm with a continuous underlying tnorm and a continuous underlying t-conorm. Along this study, given a fixed uninorm with continuous underlying operators, all fuzzy implications that satisfy the law of importation with respect to this uninorm, and having an α-section that is a continuous negation, are characterized.

Spectrum activity surveillance (SAS) is essential to dynamic spectrum access (DSA)-enabled systems with a two-fold impact: it is a primitive mechanism to collect usage data for spectrum efficiency improvement; it is also a prime widget to collect misuse forensics of unauthorized or malicious users. While realizing SAS for DSA-enabled systems appears to be intuitive and trivial, it is, however, a challenging yet open problem. On one hand, a large-scale SAS function is costly to implement in practice; on the other hand, it is not clear how to characterize the efficacy and performance of monitor deployment strategies. To address such challenges, we introduce a three-factor space, composed of spectrum, time, and geographic region, over which the SAS problem is formulated by a two-step solution: 3D-tessellation for sweep (monitoring) coverage and graph walk for detecting spectrum culprits, that is, devices responsible for unauthorized spectrum occupancy. In particular, our system model transforms SAS from a globally collective activity to localized (even distributed) actions, and strategy objectives from qualitative attributes to quantitative measures. With this model, we design low-cost deterministic strategies for dedicated monitors, which outperform strategies found by genetic algorithms, and performance-guaranteed random strategies for crowd-source monitors, which can detect adversarial spectrum culprits in bounded time.

This paper studies the multi-agent control problem for affine, rigid, and translational formation, with the aim of developing a unified distributed control strategy for global and finite-time convergence. Global stabilization of rigid formation in arbitrary dimensional spaces still remains open and challenging. This paper provides a general solution to it based on the sliding mode control idea. The control law design consists of two parts: the main control force regulates the trajectories of all agents to reach a sliding surface defined by an affine formation space in finite time and remain in it thereafter; the extra control force governs certain chosen leader agents towards the desired formation in the sliding surface. The paper then presents in detail two approaches for designing the extra control force, one based on distance constraints and the other based on relative position constraints. For the first time, the proposed sliding mode formation control laws solve the open problem of (almost) global and finite-time stabilization of affine, rigid and translational formations in any dimensional space.

In this note, we point out that Theorem 3 (a version of Egoroff's theorem for monotone set-valued measures) shown in the paper “Lusin's theorem for monotone set-valued measures on topological spaces” (Fuzzy Sets and Systems 364 (2019) 111-123) is not valid, and we present two revised versions. We also point out that the proofs of Lemma 2 and Theorem 1 are defective, thus the truth of their conclusions cannot be affirmed. Thereby, an open problem for the characteristics of monotone measures is raised.

The atom-bond connectivity (ABC) index is a degree-based molecular descriptor that found diverse chemical applications. Characterizing trees with minimum ABC-index remained an elusive open problem even after serious attempts and is considered by some as one of the most intriguing open problems in mathematical chemistry. In this paper, we describe the exact structure of the extremal trees with sufficiently many vertices and we show how their structure evolves when the number of vertices grows. An interesting fact is that their radius is at most 5 and that all vertices except for one have degree at most 54. In fact, all but at most O ( 1 ) vertices have degree 1, 2, 4, or 53. Let γ n = min ⁡ { ABC ( T ) : T is a tree of order n } . It is shown that γ n = 1 365 1 53 ( 1 + 26 55 + 156 106 ) n + O ( 1 ) ≈ 0.67737178 n + O ( 1 ) .

The directed power graph $$\vec {\mathcal {G}}( G)$$ of a group G is the simple digraph with vertex set G in which $$x\rightarrow y$$ if y is a power of x, and the power graph is the underlying simple graph $$\mathcal {G}( G)$$ . In this paper, three versions of the definition of the power graph are discussed, and it is proved that the power graph by any of the three versions of the definition determines the other two up to isomorphism. It is also proved that if G is a torsion-free group of nilpotency class 2 and if H is a group such that $$\mathcal {G}( H)\cong \mathcal {G}( G)$$ , then G and H have isomorphic directed power graphs, which was an open problem proposed by Cameron, Guerra and Jurina [9].

The construction of uninorms on bounded lattices has been a attractive research area. In this paper, we introduce some new classes of uninorms on bounded lattices via t-subnorms and t-subconorms with a neutral element e under some constraints. We also give some illustrative examples to help understand the structure of these new uninorms. Moreover, we provide an answer to the open problem raised by Cayli in 2019. Finally, the differences between our methods and existing approaches are assessed.

For any $\Omega\subset \mathbb{R}^N$ smooth and bounded domain, we prove uniqueness of positive solutions of free boundary problems arising in plasma physics on $\Omega$ in a neat interval depending only by the best constant of the Sobolev embedding $H^{1}_0(\Omega)\hookrightarrow L^{2p}(\Omega)$, $p\in [1,\frac{N}{N-2})$ and show that the boundary density and a suitably defined energy share a universal monotonic behavior. At least to our knowledge, for $p>1$, this is the first result about the uniqueness for a domain which is not a two-dimensional ball and in particular the very first result about the monotonicity of solutions, which seems to be new even for $p=1$. The threshold, which is sharp for $p=1$, yields a new condition which guarantees that there is no free boundary inside $\Omega$. As a corollary, in the same range, we solve a long-standing open problem (dating back to the work of Berestycki-Brezis in 1980) about the uniqueness of variational solutions. Moreover, on a two-dimensional ball we describe the full branch of positive solutions, that is, we prove the monotonicity along the curve of positive solutions until the boundary density vanishes., Comment: 29 pages

The Big Match is a multistage two-player game. In each stage, player 1 hides one or two pebbles in his hand, and his opponent has to guess that number. Player 1 loses a point if player 2 is correct; otherwise, he wins a point. As soon as player 1 hides one pebble, the players cannot change their choices in any future stage. The undiscounted Big Match has been much-studied. Blackwell and Ferguson (1968) give an [Formula: see text]-optimal strategy for player 1 that hides, in each stage, one pebble with a probability that depends on the entire past history. Any strategy that depends on just the clock or just a finite memory is worthless (i.e., cannot guarantee strictly more than the least reward). The long-standing natural open problem has been whether every strategy that depends on just the clock and a finite memory is worthless. The present paper proves that there is such a strategy that is [Formula: see text]-optimal. In fact, we show that just two states of memory are sufficient.

We revisit the single-machine preemptive scheduling problem to minimize total completion time with release times and deadlines. Du and Leung (1993) showed that the problem is binary NP-hard. But the exact complexity (unary NP-hardness or pseudo-polynomial-time solvability) of the problem is a long standing open problem. We show in this paper that the problem is unary NP-hard.

The normal forms of the vector fields with local bifurcations at the equilibrium points can be employed to describe the topological structure in the neighborhood of the critical points. Furthermore, the relationship between the coefficients of the normal form and the original system is very important to understand the behaviors of the practical dynamics. Though many results related to low co-dimensional local bifurcations are presented, the normal forms as well as the computation with high co-dimensional local bifurcations still remain an open problem to be investigated. The main purpose of this paper is to derive the normal form of a vector field with codimension-3 zero-zero-Hopf bifurcation at the origin and develop an uniform program to compute the coefficients of the normal form from a general system. By employing the central manifold theory and the normal form theory, all the expressions of the coefficients of the nonlinear transformations and the normal form up to any desired order related to the local bifurcation are presented, which can be computed via a software program based on the symbolic language Maple, attached in the appendix. Perturbation of the vector field at the bifurcation point can also be derived accordingly, which can be used to explore the topological property of the bifurcation.