Function S-rough Sets and Their Law Characteristic

Function S-rough sets(Function Singular rough sets) are defined by R-function equivalence class which has dynamic characteristic, and a function is s law, function S-rough sets have law characteristic. Function S-rough sets has these forms: function one direction S-rough sets, function two direction S-rough sets and dual of function one direction S-rough sets. This paper presents the law characteristic of function one direction S-rough sets and puts forward the theorems of law-chain-attribute and law-belt. Function S-rough sets is s new research direction of the rough sets theory.

F-rough law and the discovery of rough law

By using function one direction S-rough sets （function one direction singular rough sets）, this article presents the concepts of F-law, F-rough law, and the relation metric of rough law; by using these concepts, this article puts forward the theorem of F-law relation metric, two orders theorem of F-rough law relation metric, the attribute theorem of F-rough law band, the extremum theorem of F-rough law relation metric, the discovery principle of F-rough law and the application of F-rough law.

F-Law collision and system state recognition

Using function one direction S-rough sets （function one direction singular rough sets）, f-law and F- law and the concept of law distance and the concept of system law collided by F-law are given. Using these concepts, state characteristic presented by system law collided by F-law and recognition of these states characteristic and recognition criterion and applications are given. Function one direction S-rough sets is one of basic forms of function S-rough sets （function singular rough sets）. Function one direction S-rough sets is importance theory and is a method in studying system law collision.

F-generation law and recognition of system law

If a system is not disturbed （or invaded） by some law, there is no doubt that each system will move according to the expected law and keep stable. Although such a fact often appears, some unknown law breaks into the system and leads it into turbulence. Using function one direction S-rough sets, this article gives the concept of the F-generation law in the system, the generation model of the F-generation law and the recognition method of the system law. Function one direction singular rough sets is a new theory and method in recognizing the disturbance law existing in the system and recognizing the system law.

Hiding dependence-discovery of F-hiding laws and system laws

Function one direction S-rough sets have dynamic characteristics and law characteristics. By using the function one direction S-rough sets, this article presents the concepts of the f-hiding law, F-hiding law, f-hiding law dependence and F-hiding law dependence. Based on the concepts above, this article proposes the hidingdependence theorem of f-hiding laws, the hiding-dependence theorem of F-hiding laws, the hiding-dependence separation theorem, the hiding dependence-discovery principle of unknown laws. Finally, the application of the hiding dependence of hiding laws in the discovery of system laws is given.

■-law collision and system state recognition

Using dual function one direction S-rough sets, this article gives the f-law, the F-law, law distance and the concept of system law collided by the F-law. The characteristics presented by the system law collided by the F-law, the recognition of these characteristics and recognition criterion are also proposed. The dual function one direction S-rough sets is one of the basic forms of function S-rough sets. Its basic theory and application in the study of system law collision are reviewed.

Tripling Construction for Large Sets of Resolvable Directed Triple Systems

In this paper, we first define a doubly transitive resolvable idempotent quasigroup （DTRIQ）, and show that aDTRIQ of order v exists if and only ifv ≡0（mod3） and v ≠ 2（mod4）. Then we use DTRIQ to present a tripling construction for large sets of resolvable directed triple systems, which improves an earlier version of tripling construction by Kang （J. Combin. Designs, 4 （1996）, 301-321）. As an application, we obtain an LRDTS（4·3^n） for any integer n ≥ 1, which provides an infinite family of even orders.

Directed Dominating Set Problem Studied by Cavity Method:Warning Propagation and Population Dynamics

The minimal dominating set for a digraph(directed graph) is a prototypical hard combinatorial optimization problem. In a previous paper, we studied this problem using the cavity method. Although we found a solution for a given graph that gives very good estimate of the minimal dominating size, we further developed the one step replica symmetry breaking theory to determine the ground state energy of the undirected minimal dominating set problem. The solution space for the undirected minimal dominating set problem exhibits both condensation transition and cluster transition on regular random graphs. We also developed the zero temperature survey propagation algorithm on undirected Erds-Rnyi graphs to find the ground state energy. In this paper we continue to develope the one step replica symmetry breaking theory to find the ground state energy for the directed minimal dominating set problem. We find the following.(i) The warning propagation equation can not converge when the connectivity is greater than the core percolation threshold value of 3.704. Positive edges have two types warning, but the negative edges have one.(ii) We determine the ground state energy and the transition point of the Erd?os-R′enyi random graph.(iii) The survey propagation decimation algorithm has good results comparable with the belief propagation decimation algorithm.

The Hiding Characteristic of F-interior Hiding Image and Its Applications

By using function one direction S-rough sets,the concept of F-interior hiding image is presented; the theorem of F-interior hiding and the recognition criteria of interior hiding are proposed; and the applications of F-interior hiding image are given. F-interior hiding image is a new application area of function S-rough sets,and function S-rough sets is a new theory and new tools for iconology research.

F-knowledge and Its F-reduction Theorems

By using the dual of one direction singular rough sets,the concepts of F-knowledge and its F-reduction were given;F-reduction theorem of F-knowledge and attribute supplement redundant principle of F-reduction are presented;the dual of one direction singular rough sets is one of the basic forms of singular rough sets;knowledge reduction is a new research direction on rough sets and rough system theory.

Statistical mechanics of the directed 2-distance minimal dominating set problem

The directed L-distance minimal dominating set(MDS) problem has wide practical applications in the fields of computer science and communication networks. Here, we study this problem from the perspective of purely theoretical interest. We only give results for an Erdós Rényi(ER)random graph and regular random(RR) graph, but this work can be extended to any type of network. We develop spin glass theory to study the directed 2-distance MDS problem. First, we find that the belief propagation(BP) algorithm does not converge when the inverse temperatureβ exceeds a threshold on either an ER random network or RR network. Second, the entropy density of replica symmetric theory has a transition point at a finite β on a regular random graph when the arc density exceeds 2 and on an ER random graph when the arc density exceeds3.3;there is no entropy transition point(or β = ■) in other circumstances. Third, the results of the replica symmetry(RS) theory are in agreement with those of BP algorithm while the results of the BP decimation algorithm are better than those of the greedy heuristic algorithm.

Social Choice Meets Graph Drawing: How to Get Subexponential Time Algorithms for Ranking and Drawing Problems

We analyze a common feature of p-Kemeny AGGregation（p-KAGG） and p-One-Sided Crossing Minimization（p-OSCM） to provide new insights and findings of interest to both the graph drawing community and the social choice community. We obtain parameterized subexponential-time algorithms for p-KAGG—a problem in social choice theory—and for p-OSCM—a problem in graph drawing. These algorithms run in time O＊（2O（√k log k））,where k is the parameter, and significantly improve the previous best algorithms with running times O.1.403k/and O.1.4656k/, respectively. We also study natural ＂above-guarantee＂ versions of these problems and show them to be fixed parameter tractable. In fact, we show that the above-guarantee versions of these problems are equivalent to a weighted variant of p-directed feedback arc set. Our results for the above-guarantee version of p-KAGG reveal an interesting contrast. We show that when the number of ＂votes＂ in the input to p-KAGG is odd the above guarantee version can still be solved in time O＊（2O（√k log k））, while if it is even then the problem cannot have a subexponential time algorithm unless the exponential time hypothesis fails（equivalently, unless FPT D M[1]）.