Search

This paper reports on the results of a study of English children's performance on a computer mathematics assessment compared with a pencil-and-paper assessment. Two matched samples of children were each assessed on one of two mathematics pencil-and-paper tests and assessed a month later on a cloned computer test. The performance scores were better on the computer tests than on the pencil-and-paper tests, although this was not statistically significant in every case. The paper goes on to discuss some of the differences between performance and approach to the question between the two media, and explores possible reasons for these differences. In conclusion, the computer tests were found to have an overall positive effect on children's performance, although not for every child and, in some instances, the computer assessment limited the way in which a question could be answered. [ABSTRACT FROM AUTHOR]

Mathematical education, both mass education, and university education of non-mathematicians, are in an abominable state, and rapidly degrading. We argue that the instruction of non-mathematicians should be dramatically reformed both as substance and style. With traditional approach, such a transformation would take decades, with unclear results. But we do not have this time. The advent of Computer Algebra Systems gives the mathematics community a chance to reverse the trend. We should make a serious attempt to seize this opportunity. In the present paper we describe one such project of reform implemented at the St Petersburg State University. [ABSTRACT FROM AUTHOR]

The Victorian Curriculum and Assessment Authority (VCAA) introduced the use of Computer Algebra System (CAS) technology (calculator and software) into the senior secondary mathematics curriculum and examination assessment in three phases, starting with a research-based pilot from 2000, followed by parallel implementation of CAS and non-CAS subjects from 2006 and culminating in transition to CAS-assumed subjects in 2010. This paper reports reflections on these developments over two decades from the perspectives of a researcher and the state mathematics manager (the authors) in consultation with four implementing teachers (the consultants). The authors critically examined the strategic design decisions that were made for the initiative over time. Then, with contributions from the four consultants, technical design issues relating to assessment and to teaching and the changes over a decade were investigated. A range of modifications have been made over the two decades, driven by changes in device capability and progressively increasing teaching expertise. The place of CAS in senior mathematics is now widely accepted, partly because an examination component not allowing any technology has been implemented. Examination questions have become more general, which may have added difficulty, but more questions involve setting up a real situation mathematically. [ABSTRACT FROM AUTHOR]

To solve the problem of the deadline-constrained task scheduling in the cloud computing system, this paper proposes a deadline-constrained scheduling algorithm for cloud computing based on the driver of dynamic essential path (Deadline-DDEP). According to the changes of the dynamic essential path of each task node in the scheduling process, the dynamic sub-deadline strategy is proposed. The strategy assigns different sub-deadline values to every task node to meet the constraint relations among task nodes and the user’s defined deadline. The strategy fully considers the dynamic sub-deadline affected by the dynamic essential path of task node in the scheduling process. The paper proposed the quality assessment of optimization cost strategy to solve the problem of selecting server for each task node. Based on the sub-deadline urgency and the relative execution cost in the scheduling process, the strategy selects the server that not only meets the sub-deadline but also obtains much lower execution cost. In this way, the proposed algorithm will make the task graph complete within its deadline, and minimize its total execution cost. Finally, we demonstrate the proposed algorithm via the simulation experiments using Matlab tools. The experimental results show that, the proposed algorithm produces remarkable performance improvement rate on the total execution cost that ranges between 10.3% and 30.8% under meeting the deadline constraint. In view of the experimental results, the proposed algorithm provides better-quality scheduling solution that is suitable for scientific application task execution in the cloud computing environment than IC-PCP, DCCP and CD-PCP. [ABSTRACT FROM AUTHOR]

In the last ten years, cloud services provided many applications in various areas. Most of them are hosted in a heterogeneous distributed large-scale cloud computing environment and face inherent uncertainty, unreliability, and malicious attacks that trouble both service users and providers. To solve the problems of malicious attacks (including solo and collusion deception ones) in a public cloud computing environment, we for the first time propose a double-blind anonymous evaluation-based trust model. Based on it, cloud service providers and users are anonymously matched according to user requirements. It can be used to effectively handle some malicious attacks that intend to distort trust evaluations. Providers may secretly hide gain-sharing information into service results and send the results to users to ask for higher trust evaluations than their deserved ones. This paper proposes to adopt checking nodes to help detect such behavior. It then conducts gain–loss analysis for providers who intend to perform provider–user collusion deception. The proposed trust model can be used to effectively help one recognize collusion deception behavior and allow policy-makers to set suitable loss to punish malicious providers. Consequently, provider-initiated collusion deception behavior can be greatly discouraged in public cloud computing systems. Simulation results show that the proposed method outperform two updated methods, i.e., one based on fail-stop signature and another based on fuzzy mathematics in terms of malicious node detection ratio and speed. [ABSTRACT FROM AUTHOR]

A function computation problem over a directed acyclic network has been considered in the literature, where a sink node is required to compute a target function correctly with the inputs arbitrarily generated at multiple source nodes. The network links are error free but capacity limited, and the intermediate nodes perform network coding. The computing rate of a network code is the average number of times that the target function is computed for one use of the network, i.e., each link in the network is used at most once. In the existing papers, two cut-set bounds were proposed on the computing rate. However, we in this paper show that these bounds are not valid for general network function computation problems. We analyze the reason of the invalidity and propose a general cut-set bound by using a new equivalence relation associated with the inputs of the target function. Moreover, some results in the existing papers were proved by applying the invalid upper bound. We also justify the validity of these results. [ABSTRACT FROM AUTHOR]

Several recent studies have supported the existence of a link between spatial processing and some aspects of mathematical reasoning, including mental arithmetic. Some of these studies suggested that people are more accurate when performing arithmetic operations for which the operands appeared in the lower-left and upper-right spaces than in the upper-left and lower-right spaces. However, this cross-over Horizontality × Verticality interaction effect on arithmetic accuracy was only apparent for multiplication, not for addition. In these studies, the authors used a spatio-temporal synchronous operand presentation in which all the operands appeared simultaneously in the same part of space along the horizontal and vertical dimensions. In the present paper, we report studies designed to investigate whether these results can be generalized to mental arithmetic tasks using a spatio-temporal asynchronous operand presentation. We present three studies in which participants had to solve addition (Study 1a), subtraction (Study 1b), and multiplication (Study 2) in which the operands appeared successively at different locations along the horizontal and vertical dimensions. We found that the cross-over Horizontality × Verticality interaction effect on arithmetic accuracy emerged for addition but not for subtraction and multiplication. These results are consistent with our predictions derived from the spatial polarity correspondence account and suggest interesting directions for the study of the link between spatial processing and mental arithmetic performances. [ABSTRACT FROM AUTHOR]

Solid-state drives (SSDs) have recently become a common storage component in computer systems, and they are fueled by continued bit cost reductions achieved with smaller feature sizes and multiple-level cell technologies. However, as the flash memory stores more bits per cell, the performance and reliability of the flash memory degrade substantially. To solve this problem, a fast non-volatile memory (NVM-)based cache has been employed within SSDs to reduce the long latency required to write data. Absorbing small writes in a fast NVM cache can also reduce the number of flash memory erase operations. To maximize the benefits of an NVM cache, it is important to increase the NVM cache utilization. In this paper, we propose and study ProCache, a simple NVM cache management scheme, that makes cache-entrance decisions based on random probability testing. Our scheme is motivated by the observation that frequently written hot data will eventually enter the cache with a high probability, and that infrequently accessed cold data will not enter the cache easily. Owing to its simplicity, ProCache is easy to implement at a substantially smaller cost than similar previously studied techniques. We evaluate ProCache and conclude that it achieves comparable performance compared to a more complex reference counter-based cache-management scheme. [ABSTRACT FROM AUTHOR]

A (combinatorial) channel consists of pairs of words representing all possible input-output channel situations. In a past paper, we formalized the intuitive concept of 'largest amount of errors' detectable by a given language L, by defining the maximal error-detecting capabilities of L with respect to a given class of channels, and we showed how to compute all maximal error-detecting capabilities (channels) of a given regular language with respect to the class of rational channels and a class of channels involving only the substitution-error type. In this paper we resolve the problem for channels involving any combination of the basic error types: substitution, insertion, deletion. Moreover, we consider the problem of finding the inverses of these channels, in view of the fact that L is error-detecting for γ if and only if it is error-detecting for the inverse of γ. We also discuss a natural method of reducing the problem of computing (inner) distances of a given regular language L to the problem of computing maximal error-detecting capabilities of L. [ABSTRACT FROM AUTHOR]

Abstract: The range minimum query problem, RMQ for short, is to preprocess a sequence of real numbers for subsequent queries of the form: “Given indices i, j, what is the index of the minimum value of ?” This problem has been shown to be linearly equivalent to the LCA problem in which a tree is preprocessed for answering the lowest common ancestor of two nodes. It has also been shown that both the RMQ and LCA problems can be solved in linear preprocessing time and constant query time under the unit-cost RAM model. This paper studies a new query problem arising from the analysis of biological sequences. Specifically, we wish to answer queries of the form: “Given indices i and j, what is the maximum-sum segment of ?” We establish the linear equivalence relation between RMQ and this new problem. As a consequence, we can solve the new query problem in linear preprocessing time and constant query time under the unit-cost RAM model. We then present alternative linear-time solutions for two other biological sequence analysis problems to demonstrate the utilities of the techniques developed in this paper. [Copyright &y& Elsevier]

Conventional divisible load scheduling algorithms attempt to achieve optimal partitioning of massive loads to be distributed among processors in a distributed computing system in the presence of communication delays in the network. However, these algorithms depend strongly upon the assumption of prior knowledge of network parameters and cannot handle variations or lack of information about these parameters. In this paper, we present an adaptive strategy that estimates network parameter values using a probing technique and uses them to obtain optimal load partitioning. Three algorithms, based on the same strategy, are presented in the paper, incorporating the ability to cope with unknown network parameters. Several illustrative numerical examples are given. Finally, we implement the adaptive algorithms on an actual network of processor nodes using MPI implementation and demonstrate the feasibility of the adaptive approach. [ABSTRACT FROM AUTHOR]

For over 30 years, Blum's Medial Axis Transform (MAT) has proven to be an intriguing tool for analyzing and computing with form, but it is one that is notoriously difficult to apply in a robust and stable way. It is well documented how a tiny change to an object's boundary can cause a large change in its MAT. There has also been great difficulty in using the MAT to decompose an object into a hierarchy of parts reflecting the natural parts-hierarchy that we perceive. This paper argues that the underlying cause of these problems is that medial representations embody both the substance of each part of an object and the connections between adjacent parts. A small change in an object's boundary corresponds to a small change in its substance but may involve a large change in its connection information. The problems with Blum's MAT are generated because it does not explicitly represent this dichotomy of information. To use the Blum MAT to it's full potential, this paper presents a method for separating the substance and connection information of an object. This provides a natural parts-hierarchy while eliminating instabilities due to small boundary changes. The method also allows for graded, fuzzy classifications of object parts to match the ambiguity in human perception of many objects. [ABSTRACT FROM AUTHOR]

The aim of this paper is to use formal power series techniques to study the structure of small arithmetic complexity classes such as GapNC[SUP1] and GapL. More precisely, we apply the formal power series operations of inversion and root extraction to these complexity classes. We define a counting version of Kleene closure and show that it is intimately related to inversion and root extraction within GapNC[SUP1] and GapL. We prove that Kleene closure, inversion, and root extraction are all hard operations in the following sense: there is a language in AC[SUP0] for which inversion and root extraction are GapL-complete and Kleene closure is NLOG-complete, and there is a finite set for which inversion and root extraction are GapNC[SUP1]-complete and Kleene closure is NC[SUP1]-complete, with respect to appropriate reducibilities. The latter result raises the question of classifying finite languages so that their inverses fall within interesting subclasses of GapNC[SUP1], such as GapAC[SUP0]. We initiate work in this direction by classifying the complexity of the Kleene closure of finite languages. We formulate the problem in terms of finite monoids and relate its complexity to the internal structure of the monoid. Some results in this paper show properties of complexity classes that are interesting independent of formal power series considerations, including some useful closure properties and complete problems for GapL. [ABSTRACT FROM AUTHOR]

Let gd(n) be the set of d-regular simple graphs with n vertices, and for G = (V, E) in gd(n) let f : → {1, 2, . . . , n} be a objective coloring of the vertices of G. Also let α denote an interference parameter in {0, 1,. . . ,n - 1}, and define the interference number of f with respect to G and α as the number of edges {u, v} in E for which min{/f(u) - f(v)\,n - f(u) - f(v)\} < α. We consider two interference number problems for feasible (n, α, d). The first is to specify a G E and an f for which the interference number is as small as possible. The second is to determine a G &epsiv; gd(n) whose minimum interference number over all f is as large as possible. A previous paper completely solves both problems for d = 2. The present paper solves the first problem for all d ≥ 3 and obtains partial results for the second problem for d ≥ 3 that focus on interference-minimizing f's when G consists of disjoint copies of Kd+1. [ABSTRACT FROM AUTHOR]

The complexity of a mathematical expression is a measure that can be used to compare the expression with other mathematical expressions and judge which one is simpler. In the paper, we analyze three effect factors for the complexity of a mathematical expression: representational length, computational time, and intelligibility. Mainly, the paper introduces a binary-lambda-calculus based calculation method for representational complexity and a rule based calculation method for algebraic computation complexity. In the process of calculating the representation complexity of mathematical expressions, we transform the de bruijn notation into the binary lambda calculus of mathematical expressions that is inspired by compressing symmetry strings in Kolmogorov complexity theorem. Furthermore, the application of complexity of mathematical expressions in MACP, a mathematics answer checking protocol, is also addressed. MACP can be used in a computer aided assessment system in order to compute correct answers, verify equivalence of expressions, check user answers whether in a simplification form, and give automatic partial grades. [ABSTRACT FROM AUTHOR]

Power and performance management problem in large scale computing systems like data centers has attracted a lot of interests from both enterprises and academic researchers as power saving has become more and more important in many fields. Because of the multiple objectives, multiple influential factors and hierarchical structure in the system, the problem is indeed complex and hard. In this paper, the problem will be investigated in a virtualized computing system. Specifically, it is formulated as a power optimization problem with some constraints on performance. Then, the adaptive controller based on least-square self-tuning regulator(LS-STR) is designed to track performance in the first step; and the resource solved by the controller is allocated in order to minimize the power consumption as the second step. Some simulations are designed to test the effectiveness of this method and to compare it with some other controllers. The simulation results show that the adaptive controller is generally effective: it is applicable for different performance metrics, for different workloads, and for single and multiple workloads; it can track the performance requirement effectively and save the power consumption significantly. [ABSTRACT FROM AUTHOR]

Methodology of estimating the Hurst exponent using rescaled range method by use of Computer Algebra System "Mathematica" is presented. Depending of its value this measure of persistence indicates a random walk, "mean-reverting" series or trend reinforcing series. In this paper long-term memory of a time series of S&P500 index weekly returns is tested based on the Hurst exponent value. [ABSTRACT FROM AUTHOR]

In this paper, we consider the half-integral disjoint paths packing. For a graph G and k pairs of vertices (s1, t1), (s2, t2), …, (sk, tk) in G, the objective is to find paths P1, …, Pk in G such that Pi joins si and ti for i = 1, 2, …, k, and in addition, each vertex is on at most two of these paths. We give a polynomial-time algorithm to decide the feasibility of this problem with k = O((log n/log log n)1/7). This improves a result by Kleinberg [Proceedings of the 30th ACM Symposium on Theory of Computing, 1998, pp 530-539] who proved the same conclusion when k = O((log log n)2/15). Our algorithm still works for several problems related to the bounded unsplittable flow. These results can all carry over to problems involving edge capacities. Our main technical contribution is to give a "crossbar" of a polynomial size of the tree width of the graph. [ABSTRACT FROM AUTHOR]

The aim of this paper is to give the basic view on computing consistent extensions and restrictions of information systems noting some order properties of information system families. Information systems are understood in the Pawlak's sense as the systems of knowledge representation. The extension appears if we add to the original information system some new objects corresponding to the known attribute values. Analogously, the restriction appears if we remove from the original information system some objects. Presented observations enable us to find proper descriptions (preserving some features) of concurrent systems whose behavior is represented by means of information systems. [ABSTRACT FROM AUTHOR]

The engineering analysis work is based on a design and planning computer aided system. It is important to create a space at the higher education system where a set of activities and communicational expressions are developed as the fundamental line of the educational process. It will organise theoretical and practical activities where students perform technological applications to the topics developed in the class, linking the themes of the subject, in different subjects of the same or different levels of the area, as well as with other disciplines through solving projects whose complexity is conditioned only by the basic knowledge that students have. Teaching strategies are established based on different practical activities without neglecting the theoretical foundation, with a multidisciplinary approach. In this paper project based learning in engineering mathematics is exemplified on the basis of students' projects carried out at the basic sciences computer laboratory. [ABSTRACT FROM AUTHOR]

In this paper, an assessment is done on graduate distance courses in the mathematical sciences based on two formats of instruction: the traditional face-to-face lecturing with e-learning support and the online synchronous lecturing for distance students. It is shown that with a synchronous teaching tool, it is possible to create a learning environment in which distance students are provided with the necessary tools to lift up the level of learning to the same level as what can be achieved in traditional face-to-face instruction of mathematics. [ABSTRACT FROM AUTHOR]

As a framework for simple but basic statistical inference problems we introduce the genetic Most Likely Solution problem, the task of finding a most likely solution (MLS in short) for a given problem instance under some given probability model. Although many MLS problems are NP-hard, we propose for these problems, to study their average-case complexity under their assumed probability models. We show three examples of MLS problems, and show that “message passing algorithms” (e.g., belief propagation) work reasonably well for these problems. Some of the technical results of this paper are from the author’s recent work (Watanabe and Yamamoto in Lecture Notes in Computer Science, vol. 4142, pp. 277–282, , and Onsjö and Watanabe in Lecture Notes in Computer Science, vol. 4288, pp. 507–516, ). [ABSTRACT FROM AUTHOR]

A Communicating TASIM °T-Genetic Quantum KBO Memory Modules Closure is introduced in this paper by using the background information exists in the given references [1-10]. [ABSTRACT FROM AUTHOR]

Using a peer-to-peer approach for live multimedia streaming applications offers the promise to obtain a highly scalable, decentralized, and robust distribution service. When constructing streaming topologies, however, specific care has to be taken in order to ensure that quality of service requirements in terms of delay, jitter, packet loss, and stability against deliberate denial of service attacks are met. In this paper, we concentrate on the latter requirement of stability against denial-of-service attacks. We present an analytical model to assess the stability of overlay streaming topologies and describe attack strategies. Building on this, we describe topologies, which are optimally stable toward perfect attacks based on global knowledge, and give a mathematical proof of their optimality. The formal construction and analysis of these topologies using global knowledge lead us to strategies for distributed procedures, which are able to construct resilient topologies in scenarios, where global knowledge can not be gathered. Experimental results show that the topologies created in such a real-world scenario are close to optimally stable toward perfect denial of service attacks. [ABSTRACT FROM AUTHOR]

Due to the large amounts of data required to be processed by the typical Grid job, it is conceivable that the use of optical transport networks in Grid deployment (hence the term “Lambda Grid”) will increase. The exact topology of the interconnecting network is obtained by solving a dimensioning problem, and the outcome of this strongly depends on both the expected workload characteristics and Grid scheduling policy. Solving this combined scheduling and dimensioning problem using straightforward ILP modelling is cumbersome; however, for steady-state Grid operation, Divisible Load Theory (DLT) can yield scalable formulations of this problem. In this paper, the on-line hierarchical scheduling on a lambda Grid of workload approaching the Grid’s capacity in a two-tier Grid mode of operation is studied. A number of these algorithms are goal-driven, in the sense that target per-resource goals are obtained from the off-line solution to the Divisible Load model. We compare these on-line multiresource scheduling policies for different workloads, Grid interconnection topologies and Grid parameters. We show that these algorithms perform well in the studied scenarios when compared to a fully centralized scheduling algorithm. [ABSTRACT FROM AUTHOR]

Abstract: Let be a graph of order , minimum degree and connectivity . Chartrand and Harary [Graphs with prescribed connectivities, in: P. Erdös, G. Katona (Eds.), Theory of Graphs, Academic Press, New York, 1968, pp. 61–63] gave the following lower bound on the connectivityTopp and Volkmann [Sufficient conditions for equality of connectivity and minimum degree of a graph, J. Graph Theory 17 (1993) 695–700] improved this bound to , if is bipartite and . In this paper, we show that this result remains valid for diamond-free graphs with . A diamond is a graph obtained from a complete graph with 4 vertices by removing an arbitrary edge. Furthermore, we show that the above bounds can be improved significantly for graphs with and no 4-cycle, namely, if , thenFor graphs that, in addition, contain no 3-cycle, we improve this bound even further. [Copyright &y& Elsevier]

Abstract: The discovery of the first fullerene has raised an interest in the study of other candidates for modelling of carbon molecules. As a generalization of the fullerenes, fulleroids are defined as cubic convex polyhedra with all the faces of size five or greater. In this paper, we give necessary and sufficient condition for the existence of fulleroids with only pentagonal and -gonal faces and with the symmetry group isomorphic to the full symmetry group of the regular octahedron. The existence is proved by finding infinite series of examples. The nonexistence is proved using symmetry invariants. [Copyright &y& Elsevier]

Abstract: Given a hypergraph and k different colors, we study the problem of packing and coloring a subset of the hyperedges of the hypergraph as paths in a cycle such that the total profit of the hyperedges selected is maximized, where each physical link on the cycle is used at most times, each hyperedge has its profit and any two paths, each spanning all nodes of its corresponding hyperedge, must be assigned different colors if they share a common physical link. This new problem arises in optical communication networks, and it is called the Maximizing Profits when Packing and Coloring Hyperedges in a Cycle problem (MPPCHC). In this paper, we prove that the MPPCHC problem is NP-hard and then present an algorithm with approximation ratio 2 for this problem. For the special case where each hyperedge has the same profit 1 and each link has same capacity k, we propose an algorithm with approximation ratio . [Copyright &y& Elsevier]

Abstract: For a given graph G of order n, a k--labelling is defined as a function such that when and when . The -labelling number of G, denoted by , is the smallest number k such that G has a k--labelling. The hole index of G is the minimum number of integers not used in a --labelling of G. We say G is full-colorable if ; otherwise, it will be called non-full colorable. In this paper, we consider the graphs with and , where m is a positive integer. Our main work generalized a result by Fishburn and Roberts [No-hole -colorings, Discrete Appl. Math. 130 (2003) 513–519]. [Copyright &y& Elsevier]

Abstract: The asymmetric travelling salesman problem with replenishment arcs (RATSP), arising from work related to aircraft routing, is a generalisation of the well-known ATSP. In this paper, we introduce a polynomial size mixed-integer linear programming (MILP) formulation for the RATSP, and improve an existing exponential size ILP formulation of Zhu [The aircraft rotation problem, Ph.D. Thesis, Georgia Institute of Technology, Atlanta, 1994] by proposing two classes of stronger cuts. We present results that under certain conditions, these two classes of stronger cuts are facet-defining for the RATS polytope, and that ATSP facets can be lifted, to give RATSP facets. We implement our polyhedral findings and develop a Lagrangean relaxation (LR)-based branch-and-bound (BNB) algorithm for the RATSP, and compare this method with solving the polynomial size formulation using ILOG Cplex 9.0, using both randomly generated problems and aircraft routing problems. Finally we compare our methods with the existing method of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427]. It turns out that both of our methods are much faster than that of Boland et al. [The asymmetric traveling salesman problem with replenishment arcs, European J. Oper. Res. 123 (2000) 408–427], and that the LR-based BNB method is more efficient for problems that resemble the aircraft rotation problems. [Copyright &y& Elsevier]

Abstract: A Skolem sequence is a sequence (where , each occurs exactly twice in the sequence and the two occurrences are exactly positions apart. A set that can be used to construct Skolem sequences is called a Skolem set. The existence question of deciding which sets of the form are Skolem sets was solved by Skolem [On certain distributions of integers in pairs with given differences, Math. Scand. 5 (1957) 57–68] in 1957. Many generalizations of Skolem sequences have been studied. In this paper we prove that the existence question for generalized multi-Skolem sequences is -complete. This can be seen as an upper bound on how far the generalizations of Skolem sequences can be taken while still hoping to resolve the existence question. [Copyright &y& Elsevier]

Abstract: Given an integer and any graph , the sequence graph is the graph whose set of vertices is the set of all walks of length in . Moreover, two vertices of are joined by an edge if and only if their corresponding walks are adjacent in . In this paper we prove sufficient conditions for a sequence graph to be maximally edge-connected and edge-superconnected depending on the parity of and on the vertex-connectivity of the original graph . [Copyright &y& Elsevier]

Abstract: In this paper, we are going to study some additional relations between the Stirling matrix and the Pascal matrix . Also the representation for the matrix and in terms of and will be considered. Consequently, this will give an answer to an open problem proposed by EI-Mikkawy [On a connection between the Pascal, Vandermonde and Stirling matrices—II, Appl. Math. Comput. 146 (2003) 759–769]. [Copyright &y& Elsevier]

Abstract: A shortest path connecting two vertices and is called a - geodesic. The distance between and in a graph G, denoted by , is the number of edges in a - geodesic. A graph G with n vertices is panconnected if, for each pair of vertices and for each integer k with , there is a path of length k in G that connects and . A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices , every - geodesic lies on every cycle of length k satisfying . In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs. [Copyright &y& Elsevier]

Abstract: For improving reliability of communication in communication networks, where edges are subject to failure, Kishimoto [Reliable flow with failures in a network, IEEE Trans. Reliability, 46 (1997) 308–315] defined a -reliable flow, for a given source-sink pair of nodes, in a network for , where no edge carries a flow more than a fraction of the total flow in the network, and proved a max-flow min-cut theorem with cut-capacites defined suitably. Kishimoto and Takeuchi in [A method for obtaining -reliable flow in a network, IECCE Fundamentals E-81A (1998) 776–783] provided an efficient algorithm for finding such a flow. When is an integer, say , Kishimoto and Takeuchi [On -route flows in a network, IEICE Trans. J-76-A (1993) 1185–1200 (in Japanese)] introduced the notion of a q-path flow. Kishimoto [A method for obtaining the maximum multi-route flows in a network, Networks 27 (1996) 279–291] proved a max-flow min-cut theorem for q-path flow between a given source-sink pair () of nodes and provided a strongly polynomial algorithm for finding a q-path flow from s to t of maximum flow-value. In this paper, we extend the concept of q-path flow to any real number . When q is fractional, we show that this general q-path flow can be viewed as a sum of some -path flow and some -path flow. We discuss several applications of this results, which include a simpler proof and generalization of a known result on wavelength division multiplexing problem. Finally we present a strongly polynomial, combinatorial algorithm for synthesizing an undirected network with minimum sum of edge capacities that satisfies (non-simultaneously) specified minimum requirements of q-path flow-values between all pairs of nodes, for a given real number . [Copyright &y& Elsevier]

Abstract: In the test suite generation (TSG) problem for software systems, is a set of n input parameters where each has data values, and is a collection of subsets of where the interactions of the parameters in each are thought to affect the outcome of the system. A test case for is an n-tuple that specifies the value of each input parameter in . The goal is to generate a smallest-sized test suite (i.e., a set of test cases) that covers all combinations of each . The decision version of TSG is known to be NP-complete. In this paper, we present new families of for which optimal test suites can be constructed efficiently. They differ from the ones already known by the way we characterize and . We then use these instances to generate test suites for arbitrary software systems. When each has , the sizes of the test suite are guaranteed to be at most , matching the current best bound for this problem. Our constructions utilize the structure of and ; consequently, the less “complex” and are, the better are the bounds on the sizes of the test suites. [Copyright &y& Elsevier]

Abstract: In this paper, we approach the quality of a greedy algorithm for the maximum weighted clique problem from the viewpoint of matroid theory. More precisely, we consider the clique complex of a graph (the collection of all cliques of the graph) which is also called a flag complex, and investigate the minimum number k such that the clique complex of a given graph can be represented as the intersection of k matroids. This number k can be regarded as a measure of “how complex a graph is with respect to the maximum weighted clique problem” since a greedy algorithm is a k-approximation algorithm for this problem. For any , we characterize graphs whose clique complexes can be represented as the intersection of k matroids. As a consequence, we can see that the class of clique complexes is the same as the class of the intersections of partition matroids. Moreover, we determine how many matroids are necessary and sufficient for the representation of all graphs with n vertices. This number turns out to be . Other related investigations are also given. [Copyright &y& Elsevier]

This paper is structured around the idea that a finite Universal Computer cannot be realized and presents in detail a series of unconventional computing paradigms supporting this idea from a quantum mechanical perspective. [ABSTRACT FROM AUTHOR]

Any attribute set in an information system may be evolving in time when new information arrives. Approximations of a concept by rough set theory need updating for data mining or other related tasks. For incremental updating approximations of a concept, methods using the tolerance relation and similarity relation have been previously studied in literature. The characteristic relation-based rough sets approach provides more informative results than the tolerance-and-similarity relation based approach. In this paper, an attribute generalization and its relation to feature selection and feature extraction are firstly discussed. Then, a new approach for incrementally updating approximations of a concept is presented under the characteristic relation-based rough sets. Finally, the approach of direct computation of rough set approximations and the proposed approach of dynamic maintenance of rough set approximations are employed for performance comparison. An extensive experimental evaluation on a large soybean database from MLC shows that the proposed approach effectively handles a dynamic attribute generalization in data mining. [Copyright &y& Elsevier]

Abstract: The Algebra of Communicating Shared Resources (ACSR) is a timed process algebra which extends classical process algebras with the notion of a resource. It takes the view that the timing behavior of a real-time system depends not only on delays due to process synchronization, but also on the availability of shared resources. Thus, ACSR employs resources as a basic primitive and it represents a real-time system as a collection of concurrent processes which may communicate with each other by means of instantaneous events and compete for the usage of shared resources. Resources are used to model physical devices such as processors, memory modules, communication links, or any other reusable resource of limited capacity. Additionally, they provide a convenient abstraction mechanism for capturing a variety of aspects of system behavior. In this paper we give an overview of ACSR and its probabilistic extension, PACSR, where resources can fail with associated failure probabilities. We present associated analysis techniques for performing qualitative analysis (such as schedulability analysis) and quantitative analysis (such as resource utilization analysis) of process-algebraic descriptions. We also discuss mappings between probabilistic and non-probabilistic models, which allow us to use analysis techniques from one algebra on models from the other. [Copyright &y& Elsevier]

In this paper, the performance of maximum-likelihood multiuser detection in space-time-coded code-division multiple-access (CDMA) systems with imperfect channel estimation is analyzed. A K-user synchronous CDMA system that employs orthogonal space-time block codes with M transmit antennas and N receive antennas is considered. A least-squares estimate of the channel matrix is obtained by sending a sequence of pilot bits from each user. The channel matrix is perturbed by an error matrix that depends on the thermal noise and the correlation between the signature waveforms of different users. Because of the linearity of the channel estimation technique, the characteristic function of the decision variable is used to obtain an exact expression for the pairwise error probability, and by using it, an upper bound on the bit error rate (BER) is obtained. The analytical BER bounds are compared with the BER obtained through simulations. The BER bounds are shown to be increasingly tight for large SNR values. It is shown that the degradation in BER performance due to imperfect channel estimation can be compensated by using a larger number of transmitireceive antennas. [ABSTRACT FROM AUTHOR]

Performance models are used increasingly throughout the phases of the software engineering lifecycle of distributed component-based systems. However, as systems grow in size and complexity, building models that accurately capture the different aspects of their behavior becomes a more and more challenging task. In this paper, we present a novel case study of a realistic distributed component-based system, showing how Queueing Petri Net models can be exploited as a powerful performance prediction tool in the software engineering process. A detailed system model is built in a step-by-step fashion, validated, and then used to evaluate the system performance and scalability. Along with the case study, a practical performance modeling methodology is presented which helps to construct models that accurately reflect the system performance and scalability characteristics. Taking advantage of the modeling power and expressiveness of Queueing Petri Nets, our approach makes it possible to model the system at a higher degree of accuracy, providing a number of important benefits. [ABSTRACT FROM AUTHOR]

Sweeney--Robertson--Tocher (SRT) division, as it was discovered in the late 1950s, represented an important improvement in the speed of division algorithms for computers at the time. A variant of SRT division is still commonly implemented in computers today. Although some bounds on the performance of the original SRT division method were obtained, a great many questions remained unanswered. In this paper, the original version of SRT division is described as a dynamical system. This enables us to bring modern dynamical systems theory, a relatively new development in mathematics, to bear on an older problem. In doing so, we are able to show that SRT division is ergodic, and is even Bernoulli, for all real divisors and dividends. With the Bernoulli property, we are able to use entropy to prove that the natural extensions of SRT division are isomorphic by way of the Kolmogorov--Ornstein theorem. We demonstrate how our methods and results can be applied to a much larger class of division algorithms. [ABSTRACT FROM AUTHOR]

Although a tremendous effort has been made to perform a reliable analysis of images and videos in the past fifty years, the reality is that one cannot rely 100% on the analysis results. With exception of applications in controlled environments (e.g., machine vision application), one has to deal with an open world, which means that content of images may significantly change, and it seems impossible to predict all possible changes. Relying on content-based video analysis may lead to bogus results, since the observed changes may be consequence of unreliable features, and not necessarily of observed events of interest. Our main strategy is to estimate the feature properties when the features are reliable computed, so that any set of features that does not have these properties is detected as being unreliable. This way we do not perform any direct content analysis, but instead perform unsupervised analysis of feature properties that are related to the reliability. The solution pursuit in this paper is to monitor the reliability of the computed features using temporal changes and statistical properties of feature value distributions. Results on benchmark real-life videos demonstrate the capability of the proposed techniques to successfully eliminate problems due to change in light conditions, transition/compression artifacts and unwanted camera motions. [ABSTRACT FROM AUTHOR]

Tandem queueing models play an important role in many real world systems such as computer systems, production lines, and service systems. This paper proposes a procedure to construct the membership functions of the performance measures in tandem queueing systems, in that the arrival rate and service rates are fuzzy numbers. The basic idea is to transform a fuzzy tandem queue to a family of crisp tandem queues by applying the α -cut approach. Then on the basis of α -cut representation and the extension principle, a pair of mathematical programs is formulated to describe this family of crisp tandem queues, via which the membership functions of the performance measures are derived. Two numerical examples are solved successfully to demonstrate the validity of the proposed approach. Since the performance measures are expressed by membership functions rather than by crisp values, the fuzziness of input information is completely conserved. Thus the proposed approach for fuzzy systems can represent the system more accurately, and more information is provided for designing queueing systems. The successful extension of tandem queues to fuzzy environments permits tandem queueing models to have wider applications. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we investigate the problem of minimizing a linear objective function subject to a fuzzy relational equation constraint. A necessary condition for optimal solution is proposed. Based on this necessary condition, we propose three rules to simplify the work of computing an optimal solution. Numerical examples are provided to illustrate the procedure. Experimental results are reported showing that our new procedure systematically outperforms our previous work. [Copyright &y& Elsevier]

Attribute exploration is an interactive computer algorithm which helps the expert to get informations about the attribute implications of a formal context. In the part I of this paper (see [H04]) an algorithm for attribute exploration with incomplete knowledge was presented. In this part we prove the main results of the algorithm: At the end of the attribute exploration the expert gets maximal information with respect to his knowledge about the unknown universe: He gets a list of implications which are certainly valid, a list of implications which are possibly valid, a list of counterexamples against the implications which are certainly not valid and a list of fictitious counterexamples against the implications which he answered by "unknown". He only has to check the implications which he answered by "unknown" and if he can decide for each of these implications whether it is valid or not, he gets complete knowledge about the implications of the context. [ABSTRACT FROM AUTHOR]

Most of the work in the field of topology optimization is concentrated on using sensitivity analysis and optimality criteria methods that need explicit formulation. The design systems are often hard-coded for a specific problem with specialized optimization and FEM routines. This paper presents a work that uses a system approach to solid free form design. It attempts to develop a general topology optimization system that has a wide range of applicability by making use of sophisticated optimization and FEM packages available. A computer design system is implemented with an integration of commercial codes CFSQP and NASTRAN. A pre-processor and a post-processor are developed to assist the optimal design process. The system is tested with benchmark cases for minimum mean compliance and minimum weight designs. The results for the cases are presented, demonstrating the ability of the system to handle complex cases with practical feasibility. The implementation is evaluated with a parametric study of its performance. The key factors for the common problems of topology optimization are examined, including the mesh dependency and numerical instability. The computational efficiency is further studied to indicate the direction for further improvement of the system. [ABSTRACT FROM AUTHOR]

In a recent publication on the voxelization of rational curves (Comput. Graphics 27(1) (2003) 83), a difference bound is used to maximize the parameter step, thus speeding up the voxelization. In fact, evaluation of difference bounds has found wide applications in computations of parametric curves and surfaces, as well as in error estimation, in general. While any correctly derived bound can be used for these purposes, a larger bound greatly improves computational efficiency. To respond to the strong interest shown by the graphics community, this short paper proposes very large difference bounds for rational Bézier curves and surfaces. The focus is on the derivation and mathematical proof of the bound evaluation, in the form of two theorems. [Copyright &y& Elsevier]