Quantum computer is becoming one of ongoing research direction of computer science.Quantum logic is the mathemati-cal foundation of quantum computation and quantum information.Von Neumann represented properties of quantum physical systems by closed subspaces of Hilbert space,thus constituting orthomodular lattice.Elements of orthomodular lattice own definite physical understanding but lack of the ability to describe superposition.Therefore,Bob Coecke constructed propositional lattice with Heyting algebra by adding disjunction elements for superposition.Elements of propositional lattice own definite mathematical meaning but lack of physical understanding.For latter,this paper gives a deeper explanation about physical understanding of elements of propositional lattice.As our viewpoint,the added disjunction elements represent “observer perspective”,which is required while depicting superposition in propositional lattice.Thus,by applying quantum logic on measurement operation,all elements of propositional lattice are given definite physical understanding and provide theoretical basis for quantum teleportation and action at distance.

Influence maximization is selecting seed nodes under a given influence propagation model to maximize the information spread.This problem has a wide range of application scenarios,including recommendation systems,viral marketing,information diffusion and link prediction.In practical applications,the node-to-node propagation probabilities in an information propagation model are usually unknown.Besides,online learning algorithms can automatically learn unknown parameters during the interaction process and gradually approach the optimal solution.The paper first discusses the definition of influence maximization problem,introduces commonly used influence propagation models,and summarizes the common offline influence maximization algorithms.Then it introduces the classic online learning framework,the multi-armed bandit setting,analyzes the research status of online influence maximization problem,and compares the performance of common online influence maximization algorithms in real social networks through experiments.Finally,the challenges and research directions of this subject in the future is prospected.

An automaton is synchronizing means it is with a word that has the following property:no matter which state the automaton is in,it will always reach a certain state after executing with a synchronizing word as input.For the problem of synchronization of automata,the core is to compute the shortest synchronizing word.Focusing on this core problem,this paper studies the complexity of approximate computing,i.e.the hardness of approximating,the shortest synchronizing word for a class of automata called partially specified deterministic finite automata,which is helpful for the analysis and design of its approximate algorithm.By two reductions from MAX SAT and MAX FA-INT,which are two optimizing problems,to the problem of computing the length of the shortest synchronizing word (i.e.,Shortest-Syn),respectively,and by some existing results related to Probabilistically Checkable Proofs theorem and Probabilistically Checkable Debate theorem,the main results are proved.The results are as follows:for the partially specified deterministic finite automata,approximate computing the problem of Shortest-Syn is NP-hard and PSPACE-hard within some certain approximate ratios,unless NP and PSPACE collapse to P,respectively.

The two-spin system is a simplified model for the interaction of the multiparticle system in statistical physics.Computing the partition function of the system is of great significance in both statistical physics and computer science.It is well-known that the exact computation of the partition function is ＃P-hard for general systems.Therefore,the approximability of the partition function has attracted a lot of attention of computer scientists.Notable progress has been made along this line of research in recent years.Close connections between the approximability of the partition function and the phase transition of the physical mo-dels have been revealed.Based on these connections,approximation algorithms have been discovered for the model in a wide range of parameters.This paper reviews the research on the approximability of the partition functions of ferromagnetic 2-spin systems,introduces the main ideas of three classes of algorithms for this problem,including MCMC based algorithms,decay of correlation based algorithm and recent polynomial interpolation based algorithms.Moreover,the results of these algorithms are compared with the current inapproximability results.

In recent years,formal argumentation has gradually become one of the research hotspots in the field of artificial intelligence.Since Dung put forward the abstract argumentation framework in 1995,it is generally accepted in the academic circles that the core task of argumentation is to evaluate a set of arguments under various extension-based semantics,so as to determine their justification status.Graded argumentation system(GAS) is a generalization of the classical Dung-style Argumentation System (DAS),which provides a more fine-grained notion of argument status by generalizing the two core principles of DAS semantics,conflict-free and acceptability.The current research on semantic equivalence of argumentation system mainly focuses on the framework and argument level,which can provide powerful support for its structural reduction.For the semantic equivalence of the arguments in two different graded argumentation systems,firstly,fragments of the graded argumentation system are formalized by using Graded Modal Logic (GML).Then,the one-to-one correspondence between the extension-based semantics and GML formula in graded argumentation system is established and proved.Finally,the graded bisimulation relation is defined and that it implies four prominent semantic equivalences of GAS is proved.

Boolean satisfiability problem is one of the earliest proven NP complete problem.1-in-3-SAT problem is an NP complete subclass of Boolean satisfiability problem.The computational complexity of 1-in-3-SAT depends on the number of the variables and clauses in the formula.How to reduce the 1-in-3 formula to one with less variables or clauses is the key to improve the efficiency of solving 1-in-3-SAT.Based on a new type of normal form－XCNF,this paper proposes a new algebraic logic reduction method to reduce the number of variables and clauses in polynomial time.The main idea is as follows.First,the method transforms the 1-in-3 formula into a XCNF formula,then tries to find out the X pure literal in the XCNF formula and assign the corresponding Boolean variable in the 1-in-3 formula with X pure literal rule.At last,a reduced formula which has the same 1-in-3 satisfiability with the original one can be obtained.

Membrane computing is a branch of natural computing,and all the computing models investigated in membrane computing are called membrane systems.Communication in cells is a significant characteristic of membrane systems.Communication P systems with membrane division are distributed parallel computing models,which can solve hard computational problems in polynomial time.In this work,promoters are introduced into communication P systems with membrane division,and a variant of P systems,called communication P systems with membrane division and promoters is proposed,where any number of rules can be guided by a promoter in one step,and promoters do not participate the evolution process when the evolved rules are used.The computational efficiency of this kind of P systems is studied.This paper presents a uniform solution to the PSPACE-complete problem QSAT by using symport rules of length at most 2 and promoters of length at most 1 in a polynomial time.

Traditional ontology algorithms use heuristic tricks to calculate semantic similarity.With the increasing amount of data processed by ontology,more and more machine learning technologies are applied to get ontology functions.Stability is a necessary condition for ontology learning algorithms which requires that there is no substantial influence on the obtained optimal ontology function if the ontology sample set is slightly changed.This paper studies the stability and corresponding statistical characteristics of ontology learning algorithms in the setting that the dependency relation of ontology samples are characterized by a graph.Firstly,the traditional PO and LTO uniform stability conditions are analyzed.Then,the extended uniform stability conditions Pk and LkO for large samples are proposed,and related theoretical results are obtained.Finally,two sample transformations (replacement ontology samples and delete ontology samples) are combined to bring forward the concept of combined uniform stability in setting of large ontology samples,and general results are yielded by using statistical learning theory.In addition,under various stability conditions,the generalized bounds of ontology learning algorithms that satisfy the m-independent condition are discussed.

A tree decomposition of the graph G=(V,E) refers to taking a subset of the node set V as a node of the tree T,to make the intersection of the two endpoints on any path of T included in any node on the path.The number of elements of the mini-mum (node) corresponding subset on T minus 1 is defined as the width of the decomposition tree T,and the tree width of the graph G is defined by the tree width of the decomposition tree T with the smallest width.The CNF formula F can be represented by a bipartite graph G=(V∪C,E) (factor graph of the formula),where the variable node set V corresponds to the variable set,and the clause node set C corresponds to the clause set in the formula F.The positive (negative) occurrence of the element in the clause is represented by the real (virtual) side.In order to study the bipartite graph,the symbols on the edges of the formula factor graph are ignored.This paper studies the tree decomposition algorithm of graphs and applies the tree decomposition algorithm to the factor graph tree decomposition of CNF formula,aiming to explore the relationship between the tree width of the formula factor graph and the difficulty of the solution-finding through experiments.

As one of the important part of business process management,business process consistency analysis has been a hot topic in business process management research in recent years.The existing methods mainly study from two aspects,control flow and data flow.Actually,probability and time factors have a major impact on business processes.As a result,this paper proposes a Petri net business process consistency analysis method based on probability and time factor.First,the definition of control flow Petri net with probability factor and data flow Petri net with time factor are proposed.Then,all the transitions of control flow Petri net with probability factor and data flow Petri net with time factor are respectively mapped to the original business process Petri net,and the respective behavior maps are obtained.Corresponding behavioral compatibility algorithms for the two types of Petri net are proposed,and the consistency degree of business process is measured by the value of behavioral compatibility.Finally,the effectiveness and superiority of the method are demonstrated by an example.