Bases for projective modules in An(k)

Let A_n(k) be the Weyl algebra, with k a field of characteristic zero. It is known that every projective finitely generated left module is free or isomorphic to a left ideal. Let M be a left submodule of a free module. In this paper we give an algorithm to compute the projective dimension of M. If M is projective and rank(M)≥2 we give a procedure to find a basis.     

Su models of the maximum of several dependent random variables: Development and computer application

An approach for modeling the distribution of the random variable (U) that is the maximum of several dependent random variables is described in this paper. Applications of the model to various problems associated with the Industrial Engineering profession are described and one — the accumulation of components in small-lot assembly systems — is studied in detail. Numerical tests investigated the accuracy of the approach and identify several fundamental characteristics of the accumulation process. Apparent advantages of the model are that it requires computer run time that is fraction of that required by Monte Carlo sampling (simulation) procedure and that it is readily amenable to parallel processing.     

Theory of truth degrees of propositions in the logic system Ln*

By means of infinite product of uniformly distributed probability spaces of cardinal n the concept of truth degrees of propositions in the n-valued generalized Lukasiewicz propositional logic system L _n ^* is introduced in the present paper. It is proved that the set consisting of truth degrees of all formulas is dense in [0, 1], and a general expression of truth degrees of formulas as well as a deduction rule of truth degrees is then obtained. Moreover, similarity degrees among formulas are proposed and a pseudo-metric is defined therefrom on the set of formulas, and hence a possible framework suitable for developing approximate reasoning theory in n-valued generalized Lukasiewicz propositional logic is established.     

The computational complexity of ideal semantics

We analyse the computational complexity of the recently proposed ideal semantics within both abstract argumentation frameworks (afs) and assumption-based argumentation frameworks (abfs). It is shown that while typically less tractable than credulous admissibi-lity semantics, the natural decision problems arising with this extension-based model can, perhaps surprisingly, be decided more efficiently than sceptical preferred semantics. In particular the task of finding the unique ideal extension is easier than that of deciding if a given argument is accepted under the sceptical semantics. We provide efficient algorithmic approaches for the class of bipartite argumentation frameworks and, finally, present a number of technical results which offer strong indications that typical problems in ideal argumentation are complete for the class of languages decidable by polynomial time algorithms allowed to make non-adaptive queries to a C oracle, where C is an upper bound on the computational complexity of deciding credulous acceptance: C=np for afs and logic programming (lp) instantiations of abfs; for abfs modelling default theories.     

PECVD-SiOxNy films for large area self-sustained grids applications

In this work we study the structural properties and mechanical stress of silicon oxynitride (SiO_xN_y) films obtained by plasma enhanced chemical vapor deposition (PECVD) technique at low temperatures (320 °C) and report the feasibility of using this material for the fabrication of large area self-sustained grids. The films were obtained at different deposition conditions, varying the gas flow ratio between the precursor gases (N₂O and SiH₄) and maintaining all the other deposition parameters constant. The films were characterized by ellipsometry, by Fourier transform infrared (FT-IR) spectroscopy and by optically levered laser technique to measure the total mechanical stress. The results demonstrate that for appropriated deposition conditions, it is possible to obtain SiO_xN_y with very low mechanical stress, a necessary condition for the fabrication of mechanically stable thick films (up to 10 μm). Since this material (SiO_xN_y) is very resistant to KOH wet chemical etching it can be utilized to fabricate, by silicon substrate bulk micromachining, very large self-sustained grids and membranes, with areas up to 1 cm² and with thickness in the 2–6 μm range. These results allied with the compatibility of the PECVD SiO_xN_y films deposition with the standard silicon based microelectronic processing technology makes this material promising for micro electro mechanical system (MEMS) fabrication.     

Titania NOx sensors for exhaust monitoring

Oxide semiconductors have been examined to develop NO_x sensors for exhaust monitoring. Titania doped with trivalent elements, such as Al³⁺, Sc³⁺, Ga³⁺ or In³⁺, has a good sensitivity and selectivity to NO between 450 and 550 °C, and shows rapid response. A sensor probe for monitoring exhaust NO_x has been fabricated. Many kinds of interference gases, such as C₃H₆, CO and SO₂, have been found to have only a slight influence on the sensor response to NO. The influence of O₂ and H₂O is also negligible, except for the cases of 0% H₂O and fuel-rich conditions. In accordance with these results, the sensor probe operates satisfactority in the exhaust gas of various combustion conditions without interference from the various kinds of gas species in the exhaust gases.     

The computational complexity of decentralized discrete-eventcontrol problems

Computational complexity results are obtained for decentralized discrete-event control problems. These results generalize the earlier work of Tsitsiklis (1989), who showed that for a special class of centralized supervisory control problems under partial observation, there is an algorithm for determining in polynomial time whether or not a solution exists. The negative complexity results associated with Tsitsiklis work also carry over to the decentralized case, so that solution existence for the more general class is not decidable in polynomial time, nor does there exist a polynomial-time algorithm for producing supervisor solutions when such solutions exist     

The computational complexity of recognizing permutation functions

Let be a finite field withq elements and a rational function over . No polynomial-time deterministic algorithm is known for the problem of deciding whetherf induces a permutation on . The problem has been shown to be in co-R co-NP, and in this paper we prove that it is inR NP and hence inZPP, and it is deterministic polynomial-time reducible to the problem of factoring univariate polynomials over . Besides the problem of recognizing prime numbers, it seems to be the only natural decision problem inZPP unknown to be inP. A deterministic test and a simple probabilistic test for permutation functions are also presented.     

The computational complexity of N-K fitness functions

N-K fitness landscapes have been used widely as examples and test functions in the field of evolutionary computation. We investigate the computational complexity of the problem of optimizing the N-K fitness functions and related fitness functions. We give an algorithm to optimize adjacent-model N-K fitness functions, which is polynomial in N. We show that the decision problem corresponding to optimizing random-model N-K fitness functions is NP-complete for K>1, and is polynomial for K=1. If the restriction that the ith component function depends on the ith bit is removed, then the problem is NP-complete, even for K=1. We also give a polynomial-time approximation algorithm for the arbitrary-model N-K optimization problem.     

Spectral element solutions for the PN neutron transport equations

This paper discusses the application of the Legendre spectral element method to the steady one-velocity P_N equations describing neutron transport in a one-dimensional heterogeneous slab. Emphasis is put on the implementation of the method. Some key elements related to its efficiency are analyzed to prepare further developments in higher dimensions to evaluate benchmark solutions to the simplified P_N equations.     

The interdeparture time distribution for each class in the ∑Mi/Gi/1 queue with set-up times and repeated server vacations

This paper studies the interdeparture time distribution of one class of customers who arrive at a single server queue where customers of several classes are served and where the server takes a vacation whenever the system becomes empty or is empty when the server returns from a vacation. Furthermore, the first customer in the busy period is allowed to have an exceptional service time (set-up time), depending on the class to which this customer belongs. Batches of customers of each class arrive according to independent Poisson processes and compete with each other on a FIFO basis. All customers who belong to the same class are served according to a common generally distributed service time. Service times, batch sizes and the arrival process are all assumed to be mutually independent. Successive vacation times of the server form independent and identically distributed sequences with a general distribution.For this queueing model we obtain the Laplace transform of the interdeparture time distribution for each class of customers whose batch size is geometrically distributed. No explicit assumptions of the batch size distributions of the other classes of customers are necessary to obtain the results.The paper ends by showing how the mathematical results can be used to evaluate a protocol that controls access to a shared medium of an ATM passive optical network. The numerical results presented in the last section of this paper show that the bundle spacing principle that is used by the permit distribution algorithm of this protocol introduces high delays and in many cases also more variable interdeparture times for the ATM cells of individual connections. An alternative algorithm is proposed that does not cope with these performance short comings and at the same time conserves the good properties of the protocol.     

Nanowire structured SnOx–SWNT composites: High performance sensor for NOx detection

A nanowire structured nanocomposite of tin oxide (SnO_x) and a single-walled carbon nanotube (SWNT) are fabricated using rheotaxial growth and thermal oxidation method for gas sensor application. The morphology, gas sensing properties, as well as the chemical and electrical properties are investigated. The oxidation temperature for Sn mainly determines the stoichiometry of the SnO_x nano-beads, and consequently the electrical and gas sensing properties of the nanocomposite sensors. The gas sensing to nitrogen oxide, hydrogen, oxygen, xylene, acetone, carbon monoxide, and ammonia are also examined to determine the gas selectivity of the sensor. The high sensitivity and selectivity towards NO_x of the nanocomposite sensor is realized via the porous structure of the SWNT template. The gas sensing mechanism of the nanocomposite structure is also discussed.     

The computational complexity of the backbone coloring problem for bounded-degree graphs with connected backbones

Given a graph G, a spanning subgraph H of G   and an integer λ≥2$\lambda \ge 2$, a λ-backbone coloring of G with backbone H is a proper vertex coloring of G   using colors 1,2,…$1,2,\dots$, in which the color difference between vertices adjacent in H is greater than or equal to λ. The backbone coloring problem is that of finding such a coloring whose maximum color does not exceed a given limit k  . In this paper, we study the backbone coloring problem for bounded-degree graphs with connected backbones and we give a complete computational complexity classification of this problem. We present a polynomial algorithm for optimal backbone coloring for subcubic graphs with arbitrary backbones. We also prove that the backbone coloring problem for graphs with arbitrary backbones and with fixed maximum degree (at least 4) is NP-complete. Furthermore, we show that for the special case of graphs with fixed maximum degree at least 5 and λ≥4$\lambda \ge 4$ the problem remains NP-complete even for spanning tree backbones.     

On the computational complexity of weighted voting games

Coalitional games provide a useful tool for modeling cooperation in multiagent systems. An important special class of coalitional games is weighted voting games, in which each player has a weight (intuitively corresponding to its contribution), and a coalition is successful if the sum of its members’ weights meets or exceeds a given threshold. A key question in coalitional games is finding coalitions and payoff division schemes that are stable, i.e., no group of players has any rational incentive to leave. In this paper, we investigate the computational complexity of stability-related questions for weighted voting games. We study problems involving the core, the least core, and the nucleolus, distinguishing those that are polynomial-time computable from those that are NP-hard or coNP-hard, and providing pseudopolynomial and approximation algorithms for some of the computationally hard problems.     

On the computational complexity of bisimulation, redux

Paris Kanellakis and the second author (Smolka) were among the first to investigate the computational complexity of bisimulation, and the first and third authors (Moller and Srba) have long-established track records in the field. Smolka and Moller have also written a brief survey about the computational complexity of bisimulation [ACM Comput. Surv. 27(2) (1995) 287]. The authors believe that the special issue of Information and Computation devoted to PCK50: Principles of Computing and Knowledge: Paris C. Kanellakis Memorial Workshop represents an ideal opportunity for an up-to-date look at the subject.     

The worst-case time complexity for generating all maximal cliques and computational experiments

We present a depth-first search algorithm for generating all maximal cliques of an undirected graph, in which pruning methods are employed as in the Bron–Kerbosch algorithm. All the maximal cliques generated are output in a tree-like form. Subsequently, we prove that its worst-case time complexity is O(3^n/3)$\mathrm{O}(3^{n/3})$ for an n-vertex graph. This is optimal as a function of n  , since there exist up to 3^n/3$3^{n/3}$ maximal cliques in an n-vertex graph. The algorithm is also demonstrated to run very fast in practice by computational experiments.     

On the computational complexity of coalitional resource games

We study Coalitional Resource Games (crgs), a variation of Qualitative Coalitional Games (qcgs) in which each agent is endowed with a set of resources, and the ability of a coalition to bring about a set of goals depends on whether they are collectively endowed with the necessary resources. We investigate and classify the computational complexity of a number of natural decision problems for crgs, over and above those previously investigated for qcgs in general. For example, we show that the complexity of determining whether conflict is inevitable between two coalitions with respect to some stated resource bound (i.e., a limit value for every resource) is co-np-complete. We then investigate the relationship between crgs and qcgs, and in particular the extent to which it is possible to translate between the two models. We first characterise the complexity of determining equivalence between crgs and qcgs. We then show that it is always possible to translate any given crg into a succinct equivalent qcg, and that it is not always possible to translate a qcg into an equivalent crg; we establish some necessary and some sufficient conditions for a translation from qcgs to crgs to be possible, and show that even where an equivalent crg exists, it may have size exponential in the number of goals and agents of its source qcg.