Restricted compositions and permutations: From old to new Gray codes

Any Gray code for a set of combinatorial objects defines a total order relation on this set: x is less than y if and only if y occurs after x in the Gray code list. Let ? denote the order relation induced by the classical Gray code for the product set (the natural extension of the Binary Reflected Gray Code to k-ary tuples). The restriction of ? to the set of compositions and bounded compositions gives known Gray codes for those sets. Here we show that ? restricted to the set of bounded compositions of an interval yields still a Gray code. An n-composition of an interval is an n-tuple of integers whose sum lies between two integers; and the set of bounded n-compositions of an interval simultaneously generalizes product set and compositions of an integer, and so ? put under a single roof all these Gray codes.As a byproduct we obtain Gray codes for permutations with a number of inversions lying between two integers, and with even/odd number of inversions or cycles. Such particular classes of permutations are used to solve some computational difficult problems.     

Complexity of graph self-assembly in accretive systems and self-destructible systems

Self-assembly is a process in which small objects autonomously associate with each other to form larger complexes. It is ubiquitous in biological constructions at the cellular and molecular scale and has also been identified by nanoscientists as a fundamental method for building nano-scale structures. Recent years have seen convergent interest and efforts in studying self-assembly from mathematicians, computer scientists, physicists, chemists, and biologists. However most complexity theoretical studies of self-assembly utilize mathematical models with two limitations: (1) only attraction, while no repulsion, is studied; (2) only assembled structures of two dimensional square grids are studied. In this paper, we study the complexity of the assemblies resulting from the cooperative effect of repulsion and attraction in a more general setting of graphs. This allows for the study of a more general class of self-assembled structures than the previous tiling model. We define two novel assembly models, namely the accretive graph assembly model and the self-destructible graph assembly model, and identify a fundamental problem in them: the sequential construction of a given graph. We refer to it as the Accretive Graph Assembly Problem (AGAP) and the Self-Destructible Graph Assembly Problem (DGAP), in the respective models. Our main results are: (i) AGAP is NP-complete even if the maximum degree of the graph is restricted to 4 or the graph is restricted to be planar with maximum degree 5; (ii) counting the number of sequential assembly orderings that result in a target graph (#AGAP) is #P-complete; and (iii) DGAP is PSPACE-complete even if the maximum degree of the graph is restricted to 6 (this is the first PSPACE-complete result in self-assembly). We also extend the accretive graph assembly model to a stochastic model, and prove that determining the probability of a given assembly in this model is #P-complete.     

On the complexity of 2D discrete fixed point problem

We study a computational complexity version of the 2D Sperner problem, which states that any three coloring of vertices of a triangulated triangle, satisfying some boundary conditions, will have a trichromatic triangle. In introducing a complexity class PPAD, Papadimitriou [C.H. Papadimitriou, On graph-theoretic lemmata and complexity classes, in: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, 1990, 794–801] proved that its 3D analogue is PPAD-complete about fifteen years ago. The complexity of 2D-SPERNER itself has remained open since then.     

On regular realizability problems for context-free languages

We consider regular realizability problems, which consist in verifying whether the intersection of a regular language which is the problem input and a fixed language (filter) which is a parameter of the problem is nonempty. We study the algorithmic complexity of regular realizability problems for context-free filters. This characteristic is consistent with the rational dominance relation of CF languages. However, as we prove, it is more rough. We also give examples of both P-complete and NL-complete regular realizability problems for CF filters. Furthermore, we give an example of a subclass of CF languages for filters of which the regular realizability problems can have an intermediate complexity. These are languages with polynomially bounded rational indices.     

Complexity of reachability problems for finite discrete dynamical systems

Sequential Dynamical Systems (SDSs) are a special type of finite discrete dynamical systems that can be used to model simulation systems. We focus on the computational complexity of testing several phase space properties of SDSs. Our main result is a sharp delineation between classes of SDSs whose behavior is easy to predict and those whose behavior is hard to predict. Specifically, we show the following.

1.

Several state reachability problems for SDSs are PSPACE-complete, even when restricted to SDSs whose underlying graphs are of bounded bandwidth (and hence of bounded pathwidth and treewidth), and the function associated with each node is symmetric. Moreover, this result holds even when the underlying graph is d-regular for some constant d and all the nodes compute the same symmetric Boolean function. An immediate corollary of this result is a PSPACE-hard lower bound on the complexity of reachability problems for regular generalized 1D-Cellular Automata and undirected systolic networks with Boolean totalistic local transition functions.

2.

In contrast, the above reachability problems are solvable in polynomial time for SDSs when the Boolean function associated with each node is symmetric and monotone.

The PSPACE-completeness results follow as corollaries of simulation results which show for several classes of SDSs, how one class of SDSs can be efficiently simulated by another (more restricted) class of SDSs. We also prove several structural properties concerning the phase space of an SDS. SDSs are closely related to Cellular Automata (CA), concurrent transition systems, discrete Hopfield networks and systolic networks. This observation in conjunction with our lower bounds for SDSs, yields new PSPACE-hard lower bounds on the complexity of state reachability problems for these models, extending some of the earlier results in [K. Culik II, J. Karhumäki, On totalistic systolic networks, Inform. Process. Lett. 26 (5) (1988) 231-236; P. Floréen, E. Goles, G. Weisbuch, Transient length in sequential iterations of threshold functions, Discrete Appl. Math. 6 (1983) 95-98; P. Floréen, P. Orponen, Complexity issues in discrete Hopfield networks, Research Report No. A-1994-4, Department of Computer Science, University of Helsinki, 1994. Also appears in: I. Parberry (Ed.), Comp. and Learning Complexity of Neural Networks: Advanced Topics, 1999; D. Harel, O. Kupferman, M.Y. Vardi, On the complexity of verifying concurrent transition systems, Inform. and Comput. 173 (2002) 143-161; S.K. Shukla, H.B. Hunt III, D.J. Rosenkrantz, R.E. Stearns, On the complexity of relational problems for finite state processes, in: International Colloquium on Automata Programming and Languages, ICALP, 1996, pp. 466-477; A. Rabinovich, Complexity of equivalence problems for concurrent systems of finite agents, Inform. and Comput. 127 (2) (1997) 164-185].     

A dual K-Na selective Prussian blue nanotubes sensor

A strategy for dual sensing of Na⁺ and K⁺ ions using Prussian blue nanotubes via selective inter/deintercalation of K⁺ ion and competitive inhibition by Na⁺ ion, is reported. The analytical signal is derived from the cyclic voltammetry cathodic peak position E_pc of Prussian blue nanotubes. Na⁺ and K⁺ levels in a sample solution can be determined conveniently using one Prussian blue nanotubes sensor. In addition, this versatile method can be applied for the analysis of single type of either Na⁺ or K⁺ ions. The dual-ion sensor response towards Na⁺ and K⁺ can be described using a model based on the competitive inhibition effects of Na⁺ on K⁺ inter/deintercalation in Prussian blue nanotubes. Successful application of the Prussian blue nanotubes sensor for Na⁺ and K⁺ determination is demonstrated in artificial saliva.     

Imine-functionalized, turn-on fluorophore for DCP

A monopyrene-imine derivative 1 is a highly selective and sensitive “turn-on” fluorogenic probe for diethyl chlorophosphate (DCP), a stimulant for organophosphorus nerve agents. Upon addition of DCP to a solution of 1, a phosphoramidate was formed which exhibited an enhanced fluorescence emission at 425 nm. When exposed to DCP in the vapor phase, 1 impregnated on silica gel showed a sky-blue fluorescence.     

Four-arc approximation to ellipses: The best in general

So far, the four-arc approximations to an ellipse E are made under the condition that the major and minor axes keep strictly unchanged. In general, however, this condition is unnecessary. Then the fitting can be further improved. Considering a representative quadrant of E, we first draw two auxiliary circular arcs tangent to E at the axes but having a gap ε at their boundary, such that the small arc S lies outside the large arc L. Meanwhile the extreme errors of S and L w.r.t. E are ε and −ε respectively. Giving the radii of S and L a decrement −ε/2 and an increment ε/2 brings them to join smoothly. Thus, reducing the overall error to minimum, an analytic solution in implicit form is derived.     

Novel carbazole/anthracene hybrids for efficient blue organic light-emitting diodes

Two novel carbazole/anthracene hybrided molecules, namely 2-(anthracen-9-yl)-9-ethyl-9H-carbazole (AnCz) and 2,7-di(anthracen-9-yl)-9-ethyl-9H-carbazole (2AnCz), were designed and synthesized via palladium catalyzed coupling reaction. The anthracene was attached either at the 2-site (AnCz) or at both 2,7-sites (2AnCz) of the central carbazole core to tune the conjugation state and the optoelectronic properties of the resultant molecules. Both of them show good solubility in common organic solvents. They also possess relatively high HOMO levels (−5.39 eV, −5.40 eV) that would facilitate efficient hole injection and be favorable for high power efficiencies when used in organic light-emitting devices (OLEDs). AnCz and 2AnCz were used as non-doped emitter to fabricate OLEDs by vacuum evaporation. Good performance was achieved with maximum luminance efficiency of 2.61 cd A⁻¹ and CIE coordinates of (0.15, 0.12) for AnCz, and 9.52 cd A⁻¹ and (0.22, 0.37) for 2AnCz.     

New approximations for minimum-weighted dominating sets and minimum-weighted connected dominating sets on unit disk graphs

Given a node-weighted graph, the minimum-weighted dominating set (MWDS) problem is to find a minimum-weighted vertex subset such that, for any vertex, it is contained in this subset or it has a neighbor contained in this set. And the minimum-weighted connected dominating set (MWCDS) problem is to find a MWDS such that the graph induced by this subset is connected. In this paper, we study these two problems on a unit disk graph. A (4 +ε)-approximation algorithm for an MWDS based on a dynamic programming algorithm for a Min-Weight Chromatic Disk Cover is presented. Meanwhile, we also propose a (1 +ε)-approximation algorithm for the connecting part by showing a polynomial-time approximation scheme for a Node-Weighted Steiner Tree problem when the given terminal set is c-local and thus obtain a (5 +ε)-approximation algorithm for an MWCDS.     

Nonlinear mappings in problem solving and their PSO-based development

The study is devoted to a concept and algorithmic realization of nonlinear mappings aimed at increasing the effectiveness of the problem solving method. Given the original input space X and a certain problem solving method M, designed is a nonlinear mapping ? so that the method operating in the transformed space M(?(X)) becomes more efficient. The nonlinear mappings realize a transformation of X through contractions and expansions of selected regions of the original space. In particular, we show how a piecewise linear mapping is optimized by using particle swarm optimization (PSO) and a suitable fitness function quantifying the objective of the problem. Several families of problems are investigated and illustrated through illustrative experimental results.     

Non-contractible non-edges in 2-connected graphs

Any pair of non-adjacent vertices forms a non-edge in a graph. Contraction of a non-edge merges two non-adjacent vertices into a single vertex such that the edges incident on the non-adjacent vertices are now incident on the merged vertex. In this paper, we consider simple connected graphs, hence parallel edges are removed after contraction. The minimum number of nodes whose removal disconnects the graph is the connectivity of the graph. We say a graph is k-connected, if its connectivity is k. A non-edge in a k-connected graph is contractible if its contraction does not result in a graph of lower connectivity. Otherwise the non-edge is non-contractible. We focus our study on non-contractible non-edges in 2-connected graphs. We show that cycles are the only 2-connected graphs in which every non-edge is non-contractible.     

Science Code .Net: Object-oriented programming for science

We propose an object-oriented programming library system for Science in a similar structure of .NET framework. We call the system Science Code .Net. Presenting rules of thumb, we show how to enhance readability of Science Code .Net. As an initial progress, several namespaces have been constructed. We explain the structure of classes in each namespace. As a challenge to the programming community, a perspective view of Science Code .Net is discussed.     

An efficient algorithm for constructing a connected dominating set in mobile ad hoc networks

The connected dominating set (CDS) is widely used as a virtual backbone in mobile ad hoc networks. Although many distributed algorithms for constructing the CDS have been proposed, nearly all of them require two or more separated phases, which may cause problems such as long delay in the later phases when the network size is large. This paper proposes a Distributed Single-Phase algorithm for constructing a connected dominating set, DSP-CDS, in ad hoc networks. The DSP-CDS is an asynchronous distributed algorithm and converges quickly in a single phase. Each node uses one-hop neighborhood information and makes a local decision on whether to join the dominating set. Each node bases its decision on a key variable, strength, which guarantees that the dominating set is connected when the algorithm converges. The rules for computing strength can be changed to accommodate different application needs. The DSP-CDS adapts well to dynamic network topologies, upon which the algorithm makes only necessary local updates to maintain the CDS of the network. The performance of the DSP-CDS can be tuned by adjusting two main parameters. Extensive simulations have demonstrated that those parameters can affect the CDS size, the CDS diameter, and number of rounds for the algorithm to converge. Comparisons with other multiple-phase CDS algorithms have shown that the DSP-CDS converges fast and generates a CDS of comparable size.     

The complexity of agent design problems: Determinism and history dependence

The agent design problem is as follows: given a specification of an environment, together with a specification of a task, is it possible to construct an agent that can be guaranteed to successfully accomplish the task in the environment? In this article, we study the computational complexity of the agent design problem for tasks that are of the form “achieve this state of affairs” or “maintain this state of affairs.” We consider three general formulations of these problems (in both non-deterministic and deterministic environments) that differ in the nature of what is viewed as an “acceptable” solution: in the least restrictive formulation, no limit is placed on the number of actions an agent is allowed to perform in attempting to meet the requirements of its specified task. We show that the resulting decision problems are intractable, in the sense that these are non-recursive (but recursively enumerable) for achievement tasks, and non-recursively enumerable for maintenance tasks. In the second formulation, the decision problem addresses the existence of agents that have satisfied their specified task within some given number of actions. Even in this more restrictive setting the resulting decision problems are either pspace-complete or np-complete. Our final formulation requires the environment to be history independent and bounded. In these cases polynomial time algorithms exist: for deterministic environments the decision problems are nl-complete; in non-deterministic environments, p-complete.     

Geometric properties of partial least squares for process monitoring

Projection to latent structures or partial least squares (PLS) produces output-supervised decomposition on input X, while principal component analysis (PCA) produces unsupervised decomposition of input X. In this paper, the effect of output Y on the X-space decomposition in PLS is analyzed and geometric properties of the PLS structure are revealed. Several PLS algorithms are compared in a geometric way for the purpose of process monitoring. A numerical example and a case study are given to illustrate the analysis results.     

The complexity of constraint satisfaction problems for small relation algebras

Andréka and Maddux [Notre Dame J. Formal Logic 35 (4) 1994] classified the small relation algebras—those with at most 8 elements, or in other terms, at most 3 atomic relations. They showed that there are eighteen isomorphism types of small relation algebras, all representable. For each simple, small relation algebra they computed the spectrum of the algebra, namely the set of cardinalities of square representations of that relation algebra.In this paper we analyze the computational complexity of the problem of deciding the satisfiability of a finite set of constraints built on any small relation algebra. We give a complete classification of the complexities of the general constraint satisfaction problem for small relation algebras. For three of the small relation algebras the constraint satisfaction problem is NP-complete, for the other fifteen small relation algebras the constraint satisfaction problem has cubic (or lower) complexity.We also classify the complexity of the constraint satisfaction problem over fixed finite representations of any relation algebra. If the representation has size two or less then the complexity is cubic (or lower), but if the representation is square, finite and bigger than two then the complexity is NP-complete.     

The values of college students in business simulation game: A means-end chain approach

Business simulation games (BSGs) enable students to practice making decisions in a virtual environment, accumulate experience in application of strategies, and train themselves in modes of decision-making. This study examines the value sought by players of BSG. In this study, a means-end chain (MEC) model was adopted as the basis, and ladder method soft laddering was used to conduct in-depth interviews with students who had experience in using BSGs. The chain concept of “attribute-consequence-value” was used to understand students’ value cognition structures. Content analysis was used to analyze the attributes-consequences-values for BSGs players, then converted into a Hierarchical Value Map (HVM). The results showed that students consider teamwork and market diversity as the most important attributes, and the consequences of a cooperative approach and market diversity are emotional exchange and multi-thinking, with the ultimate value brought to users by exchanges between teams and constant thinking being interpersonal relationships and a sense of accomplishment.     

Feynman graph generation and calculations in the Hopf algebra of Feynman graphs

Two programs for the computation of perturbative expansions of quantum field theory amplitudes are provided. feyngen can be used to generate Feynman graphs for Yang–Mills, QED and φ^k${\phi }^k$ theories. Using dedicated graph theoretic tools feyngen can generate graphs of comparatively high loop orders. feyncop implements the Hopf algebra of those Feynman graphs which incorporates the renormalization procedure necessary to calculate finite results in perturbation theory of the underlying quantum field theory. feyngen is validated by comparison to explicit calculations of zero dimensional quantum field theories and feyncop is validated using a combinatorial identity on the Hopf algebra of graphs.