The complexity of achievement and maintenance problems in agent-based systems

We completely classify the computational complexity of the basic achievement and maintenance agent design problems in bounded environments when these problems are parameterized by the number of environment states and the number of agent actions. The different problems are P-complete, NP-complete, co-NP-complete or PSPACE-complete (when they are not trivial). We also consider alternative achievement and maintenance agent design problems by allowing longer runs in environments (that is, our environments are bounded but the bounds are more liberal than was the case previously). Again, we obtain a complete classification but so that the different problems are DEXPTIME-complete, NEXPTIME-complete, co-NEXPTIME-complete or NEXPSPACE-complete (when they are not trivial).     

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].     

Deterministic solutions to QSAT and Q3SAT by spiking neural P systems with pre-computed resources

In this paper we continue previous studies on the computational efficiency of spiking neural P systems, under the assumption that some pre-computed resources of exponential size are given in advance. Specifically, we give a deterministic solution for each of two well known PSPACE-complete problems: QSAT and Q3SAT. In the case of QSAT, the answer to any instance of the problem is computed in a time which is linear with respect to both the number n of Boolean variables and the number m of clauses that compose the instance. As for Q3SAT, the answer is computed in a time which is at most cubic in the number n of Boolean variables.     

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.     

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.     

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.     

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.     

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.     

FINE: A Fully Informed aNd Efficient communication-induced checkpointing protocol for distributed systems

Communication-Induced Checkpointing (CIC) protocols are classified into two categories in the literature: Index-based and Model-based. In this paper, we discuss two data structures being used in these two kinds of CIC protocols, and their different roles in helping the checkpointing algorithms to enforce Z-cycle Free (ZCF) property. Then, we present our Fully Informed aNd Efficient (FINE) communication-induced checkpointing algorithm, which not only has less checkpointing overhead than the well-known Fully Informed (FI) CIC protocol proposed by Helary et al. but also has less message overhead. Performance evaluation indicates that our protocol performs better than many of the other existing CIC protocols.     

A full-wave solver of the Maxwell's equations in 3D cold plasmas

A new solver for Maxwell's equations in three-dimensional (3D) plasma configurations is presented. The new code LEMan (Low-frequency ElectroMagnetic wave propagation) determines a global solution of the wave equation in a realistic stellarator geometry at low frequencies. The code is aimed at the applications with relatively small computational resources and is very efficient in the Alfvén frequency range. In the present work, the cold plasma model is implemented. Finite elements are applied for the radial discretization and the spectral representation is used for the poloidal and toroidal angles. Special care is taken to avoid the numerical pollution of the spectrum as well as to ensure the energy conservation. The numerical scheme and the convergence properties are discussed. Several benchmarks and results in different geometries are presented.     

Performance evaluation for a transportation system in stochastic case

In a single-commodity multistate flow network, the arc capacity is stochastic and thus the system capacity (i.e. the maximum flow from the source to the sink) is not a fixed number. This paper constructs a multicommodity multistate flow network with weighted capacity allocation to model a transportation system. Each arc with cost attribute has several possible capacities. The capacity weight, the consumed amount of arc capacity by per commodity, varies with the arcs and types of commodity. We define the system capacity as a demand vector d if the system fulfills at most d. The addressed problem in this work is to measure the service quality of a transportation system. We propose a performance index, the probability that the upper bound of the system capacity equals a demand vector d subject to the budget constraint. A simple algorithm based on minimal cuts is presented to generate all (d,B)-MC that are the maximal capacity vectors meeting exactly the demand d under the budget B. The proposed performance index can be subsequently evaluated in terms of such (d,B)-MC.     

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.     

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.     

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.     

Enhanced chemosensing of ammonia based on the novel molecular semiconductor-doped insulator (MSDI) heterojunctions

A series of new molecular semiconductor-doped insulator (MSDI) heterojunctions as conductimetric transducers to NH₃ sensing were fabricated based on a novel semiconducting molecular material, an amphiphilic tris(phthalocyaninato) rare earth triple-decker complex, Eu₂[Pc(15C5)₄]₂[Pc(OC₁₀H₂₁)₈], quasi-Langmuir-Shäfer (QLS) film, as a top-layer, and vacuum-deposited and cast film of CuPc as well as copper tetra-tert-butyl phthalocyanine (CuTTBPc) QLS film as a sub-layer, named as MSDIs 1, 2 and 3, respectively. MSDIs 1-3 and respective sub-layers prepared from three different methods were characterized by X-ray diffraction, electronic absorption spectra and current-voltage (I-V) measurements. Depending on the sub-layer film-forming method used, α-phase CuPc film structure, β-phase CuPc crystallites and H-type aggregates of CuTTBPc have been obtained, respectively. An increasing sensitivity to NH₃ at varied concentrations in the range of 15-800 ppm, follows the order MSDI 2 < MSDI 3 < MSDI 1, revealing the effect of sub-layer film structures on sensing performance of the MSDIs. In particular, the time-dependent current plot of the MSDI 1, with α-phase CuPc film as a sub-layer, clearly shows an excellent separation of the different ammonia concentration levels and nearly complete reversibility and reproducibility even at room temperature, which is unique among the phthalocyanine-based ammonia sensors thus far reported in the literature. This provides a general method to improve sensor response of organic heterojunctions by controlling and tuning the film structure of sub-layer with appropriate fabrication techniques. On the other hand, the enhanced sensitivity, stability and reproducible response of the MSDI 1 heterostructure in comparison with the respective single-layer films have also been obtained. A judicious combination of materials and molecular architectures has led to enhanced sensing properties of the MSDI 1, in which control at the molecular level can be achieved.     

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.     

A Maple package for improved global mapping forecast

We present a Maple implementation of the well known global approach to time series analysis and some further developments designed to improve the computational efficiency of the forecasting capabilities of the approach. This global approach can be summarized as being a reconstruction of the phase space, based on a time ordered series of data obtained from the system. After that, using the reconstructed vectors, a portion of this space is used to produce a mapping, a polynomial fitting, through a minimization procedure, that represents the system and can be employed to forecast further entries for the series. In the present implementation, we introduce a set of commands, tools, in order to perform all these tasks. For example, the command VecTS deals mainly with the reconstruction of the vector in the phase space. The command GfiTS deals with producing the minimization and the fitting. ForecasTS uses all these and produces the prediction of the next entries. For the non-standard algorithms, we here present two commands: IforecasTS and NiforecasTS that, respectively deal with the one-step and the N$N$-step forecasting. Finally, we introduce two further tools to aid the forecasting. The commands GfiTS and AnalysTS, basically, perform an analysis of the behavior of each portion of a series regarding the settings used on the commands just mentioned above.     

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.