Search

This paper studies the problem of color consistency correction for sequential images with diverse color characteristics. Existing algorithms try to adjust all images to minimize color differences among images under a unified energy framework, however, the results are prone to presenting a consistent but unnatural appearance when the color difference between images is large and diverse. In our approach, this problem is addressed effectively by providing a guided initial solution for the global consistency optimization, which avoids converging to a meaningless integrated solution. First of all, to obtain the reliable intensity correspondences in overlapping regions between image pairs, we creatively propose the histogram extreme point matching algorithm which is robust to image geometrical misalignment to some extents. In the absence of the extra reference information, the guided initial solution is learned from the major tone of the original images by searching some image subset as the reference, whose color characteristics will be transferred to the others via the paths of graph analysis. Thus, the final results via global adjustment will take on a consistent color similar to the appearance of the reference image subset. Several groups of convincing experiments on both the synthetic dataset and the challenging real ones sufficiently demonstrate that the proposed approach can achieve as good or even better results compared with the state-of-the-art approaches. [ABSTRACT FROM AUTHOR]

This paper proposes a measurement and adjustment procedure for virtual pivot errors using the R-test and investigates the influence of virtual pivot errors to the surface profile in bonnet polishing. Initially, kinematic modeling is carried out for describing the location errors of rotary axes and defining overall errors of the virtual pivot arm. Then, the R-test is introduced to measure the three-dimensional displacement of a sphere located at the virtual pivot point and identify location errors. The adjustment procedure for virtual pivot errors is developed by means of mathematical analysis. The measurement and adjustment approach is applied to an ultra-precision polishing machine, on which an adjustment experiment was conducted to validate the proposed method. Based on this, a contrastive polishing experiment on a concave lens is carried out under good and poor virtual pivot errors. The experiment result shows that the maximum form deviation of the polished surface profile is reduced from 241.0 nm to 89.6 nm when good alignment of virtual error is achieved. Analytical simulation based on a material removal model of the bonnet polishing tool and machine is implemented to reveal the influence of virtual pivot errors to polishing quality. [ABSTRACT FROM AUTHOR]

Abstract: In this paper, we modify a Multi-Objective Evolutionary Algorithm, known as Nondominated sorting Genetic Algorithm-II (NSGA-II) for a parallel machine scheduling problem with three objectives. The objectives are – (1) minimization of total cost due tardiness, (2) minimization of the deterioration cost and (3) minimization of makespan. The formulated problem has been solved by three Multi-Objective Evolutionary Algorithms which are: (1) the original NSGA-II (Non-dominated Sorting Genetic Algorithm–II), (2) SPEA2 (Strength Pareto Evolutionary Algorithm-2) and (3) a modified version of NSGA-II as proposed in this paper. A new mutation algorithm has also been proposed depending on the type of problem and embedded in the modified NSGA-II. The results of the three algorithms have been compared and conclusions have been drawn. The modified NSGA-II is observed to perform better than the original NSGA-II. Besides, the proposed mutation algorithm also works effectively, as evident from the experimental results. [Copyright &y& Elsevier]

Abstract: This paper considers the coupled, bearing-only formation control of three mobile agents moving in the plane. Each agent has only local inter-agent bearing knowledge and is required to maintain a specified angular separation relative to both neighbor agents. Assuming that the desired angular separation of each agent relative to the group is feasible, a triangle is generated. The control law is distributed and accordingly each agent can determine their own control law using only the locally measured bearings. A convergence result is established in this paper which guarantees global asymptotic convergence of the formation to the desired formation shape. [Copyright &y& Elsevier]

Abstract: In this paper we introduce constraint automata and propose them as an operational model for Reo, an exogenous coordination language for compositional construction of component connectors based on a calculus of channels. By providing composition operators for constraint automata and defining notions of equivalence and refinement relations for them, this paper covers the foundations for building tools to address concerns such as the automated construction of the automaton for a given component connector, equivalence checking or containment checking of the behavior of two given connectors, and verification of coordination mechanisms. [Copyright &y& Elsevier]

Abstract: This paper introduces a fast algorithm for image interpolation. By using this method, real-time enlargement of video images is accessible. The basic idea of the algorithm is to partition digital images into homogeneous and edge areas based on the analysis of the local structure on the images. In addition, in order to have better performance on interpolating images, specified algorithms are assigned to interpolate each classified areas, respectively. Experimental results show that the subjective quality of the interpolated images is substantially improved by using the proposed algorithm compared with that of using conventional interpolation algorithms. The computational complexity of the proposed algorithm is much lower than those of others mentioned in this paper. We also successfully implemented real-time enlargement of QCIF video sequences to CIF sequences with better image quality in low bit-rate environment. [Copyright &y& Elsevier]

We introduce a notion of postfix automata and apply it to finite automata constructions. We give a compact method for constructing smaller nondeterministic finite automata (NFAs) from given regular expressions. There are four steps in our method. First, we convert one or more given regular expressions into postfix form, better known as Reverse Polish notation, and call it a postfix regular expression . Second, we construct a syntax tree for the postfix regular expression. Next, we code the syntax tree using a specific algorithm and finally, we construct an NFA based on the coded syntax tree. Using our method we can obtain smaller NFAs, called postfix automata , with only one starting state and one final state. In this paper, we prove several notions and present a classical example to compare the size of a postfix automaton with the NFAs created by several classical construction methods. We also derive the efficiency in reducing the size of the NFA through general theoretical analysis. [ABSTRACT FROM AUTHOR]

Abstract: This paper describes an algorithm that predicts the shape of material removed by a flat-end milling tool, and this may be used to compute machining strip width and scallop height at different positions of the tool path track. The algorithm computes swept sections, profiles which are swept by a moving tool bottom by passing through given planes. The technique is applicable for finish and semi-finish multi-axis milling strategies that use flat-end tools. For these strategies, the algorithm complexity can be reduced from computation of the 3D envelope of swept volumes to computation of plane-circle intersections. A new adaptive derivative-free method to sample tool motion provides robust means to generate intermediate tool positions. The step length is constrained by and dependent on different geometrical measures. At each point of a tool path, in the plane perpendicular to the cutting direction, the bottom profile of the swept section is an estimate of the profile of material left. By calculating the distance between part geometry and the computed profile of removed material, machining strip width and a scallop profile can be derived. These results can be used by tool path generation and validation routines to accurately determine the step-over between tool path tracks and surface quality. [Copyright &y& Elsevier]

Abstract: In this paper, we continue our study on the state complexity of combined operations on regular languages. We study the state complexities of , , , and , for regular languages , , . We obtain the exact bounds for these combined operations and show that the state complexities of and are the same as the mathematical compositions of the state complexities of their component individual operations, while, on the other hand, the state complexities of and are lower than the corresponding mathematical compositions. [Copyright &y& Elsevier]

Abstract: Modal specifications are classic, convenient, and expressive mathematical objects to represent interfaces of component-based systems. However, time is a crucial aspect of systems for practical applications, e.g. in the area of embedded systems. And yet, only few results exist on the design of timed component-based systems. In this paper, we propose a timed extension of modal specifications, together with fundamental operations (conjunction, product, and quotient) that enable reasoning in a compositional way about timed system. The specifications are given as modal event-clock automata, where clock resets are easy to handle. We develop an entire theory that promotes efficient incremental design techniques. [Copyright &y& Elsevier]

Abstract: This paper studies a k-out-of-n:G repairable system with n identical machines and R repairmen. In this multi-machine system, both the redundant dependency and the multiple vacations policy for repairmen are taken into account. All vacations of the R repairmen are independent and identically distributed, and they are also independent with the other processes. By using the discrete transforms method and the Runge–Kutta method, the machine repair problem is analyzed theoretically and numerically. The influences of the redundant dependency and the repair capacity on the reliability of the system are obtained. Moreover, through some special cases, the insight on the effect of repair capacity and redundant dependency class on the reliability of the system is provided. [Copyright &y& Elsevier]

Abstract: This paper deals with the concept of complete residuated lattice-valued (referred to as -valued) finite tree automata. In this regard, we first define an -valued regular tree language, and then we prove a necessary and sufficient condition for the regularity of an -valued tree language. Furthermore, we generalize the pumping lemma for -valued finite tree automata (L-FTA). Afterwards, the behavior of L-FTA is addressed and some theorems are provided. Moreover, the existence of the minimal form of an L-FTA is considered. Finally, a minimization algorithm of the L-FTA is presented and its time complexity is analyzed. [Copyright &y& Elsevier]

Abstract: Li and Pedrycz have proved fundamental results that provide different equivalent ways to represent fuzzy languages with membership values in a lattice-ordered monoid, and generalize the well-known results of the classical theory of formal languages. In particular, they have shown that a fuzzy language over an integral lattice-ordered monoid can be represented by a fuzzy regular expression if and only if it can be recognized by a fuzzy finite automaton. However, they did not give any efficient method for constructing an equivalent fuzzy finite automaton from a given fuzzy regular expression. In this paper we provide such an efficient method. Transforming scalars appearing in a fuzzy regular expression αinto letters of the new extended alphabet, we convert the fuzzy regular expression αto an ordinary regular expression . Then, starting from an arbitrary nondeterministic finite automaton that recognizes the language represented by the regular expression , we construct fuzzy finite automata and with the same or even less number of states than the automaton , which recognize the fuzzy language ‖α‖represented by the fuzzy regular expression α. The starting nondeterministic finite automaton can be obtained from using any of the well-known constructions for converting regular expressions to nondeterministic finite automata, such as Glushkov–McNaughton–Yamada''s position automaton, Brzozowski''s derivative automaton, Antimirov''s partial derivative automaton, or Ilie–Yu''s follow automaton. [Copyright &y& Elsevier]

Abstract: The paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set of final states or on the cardinality of the set . We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms. [Copyright &y& Elsevier]

Abstract: This paper studies the nonterminal complexity of tree controlled grammars. It is proved that the number of nonterminals in tree controlled grammars without erasing rules leads to an infinite hierarchy of families of tree controlled languages, while every recursively enumerable language can be generated by a tree controlled grammar with erasing rules and at most nine nonterminals. [Copyright &y& Elsevier]

Abstract: Several methods have been developed to construct -free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu). All these automata can be obtained with quadratic time complexity, thus, the comparison criterion is usually the size of the resulting automaton. The methods that obtain the smallest automata (although, for general expressions, they are not comparable), are the follow and the partial derivatives methods. In this paper, we propose another method to obtain a -free automaton from a regular expression. The number of states of the automata we obtain is bounded above by the size of both the partial derivatives automaton and of the follow automaton. Our algorithm also runs with the same time complexity of these methods. [Copyright &y& Elsevier]

Abstract: In this paper we develop a version of Algorithmic Information Theory (AIT) based on finite transducers instead of Turing machines; the complexity induced is called finite-state complexity. In spite of the fact that the Universality Theorem (true for Turing machines) is false for finite transducers, the Invariance Theorem holds true for finite-state complexity. We construct a class of finite-state complexities based on various enumerations of the set of finite transducers. In contrast with descriptional complexities (plain, prefix-free) from AIT, finite-state complexity is computable and there is no a priori upper bound for the number of states used for minimal descriptions of arbitrary strings. Upper and lower bounds for the finite-state complexity of arbitrary strings, and for strings of particular types, are given and incompressible strings are studied. [Copyright &y& Elsevier]

Abstract: We study an on-line machine covering problem, in which jobs arrive one by one and their processing times are known upon their arrival, and jobs are allowed to migrate between machines when a new job is added in the system. However, the total processing time of migration induced by an incoming job is bounded by a constant factor times the processing time of the incoming job. The objective is to maximize the minimum machine load. In this paper, we present an on-line algorithm with competitive ratio 6/5 for the two identical machines case with . Moreover, the presented on-line algorithm is only a local migration, that is, when one job is assigned to machine , only the jobs on machine are allowed to migrate. We also show that the provided algorithm is a best possible on-line algorithm in the sense of local migration. [Copyright &y& Elsevier]

Abstract: Research on optimization in continuous domains gains much of focus in swarm computation recently. A hybrid ant colony optimization approach which combines with the continuous population-based incremental learning and the differential evolution for continuous domains is proposed in this paper. It utilizes the ant population distribution and combines the continuous population-based incremental learning to dynamically generate the Gaussian probability density functions during evolution. To alleviate the less diversity problem in traditional population-based ant colony algorithms, differential evolution is employed to calculate Gaussian mean values for the next generation in the proposed method. Experimental results on a large set of test functions show that the new approach is promising and performs better than most of the state-of-the-art ACO algorithms do in continuous domains. [Copyright &y& Elsevier]

Abstract: In this paper, we modify a known parallel cograph-recognition algorithm proposed by Nikolopoulos and Palios [S.D. Nikolopoulos, L. Palios, Efficient parallel recognition of cographs, Discrete Applied Mathematics 150 (1–3) (2005) 182–215] and provide a new analysis of the algorithm. Given an input graph with vertices and edges, we obtain the following three results based on our analysis: [1.] When is -regular for a fixed positive integer , the cograph-recognition problem can be optimally solved in time using processors on an EREW PRAM. [2.] When is -regular for , the cograph-recognition problem can be solved in time using processors on an EREW PRAM. [3.] Given a positive integer , the cograph-recognition problem can be solved in time using processors on an EREW PRAM, provided the number of vertices in with degree larger than is at most . The above results improve upon the previously best known result, which took time using processors on an EREW PRAM. [ABSTRACT FROM AUTHOR]

Abstract: In this paper we consider parallel identical machines scheduling problems with deteriorating jobs. In this model, job processing times are defined by functions of their starting times. We concentrate on two goals separately, namely, minimizing the total absolute differences in completion times (TADC) and the total absolute differences in waiting times (TADW). We show that the problems remains polynomially solvable under the proposed model. [ABSTRACT FROM AUTHOR]

Abstract: The well-designed logical robot paradigmatically represents, in the words of McCarthy, the abilities that a robot-child should have to reveal the structure of reality within a “language of thought”. In this paper we partially support McCarthy''s hypothesis by showing that early perception can trigger an inference process leading to the “language of thought”. We show this by defining a systematic transformation of structures of different formal languages sharing the same signature kernel for actions and states. Starting from early vision, visual features are encoded by descriptors mapping the space of features into the space of actions. The densities estimated in this space form the observation layer of a hidden states model labelling the identified actions as observations and the states as action preconditions and effects. The learned parameters are used to specify the probability space of a first-order probability model. Finally we show how to transform the probability model into a model of the Situation Calculus in which the learning phase has been reified into axioms for preconditions and effects of actions and, of course, these axioms are expressed in the language of thought. This shows, albeit partially, that there is an underlying structure of perception that can be brought into a logical language. [Copyright &y& Elsevier]

Abstract: In this paper, we propose a general learning framework based on local and global regularization. In the local regularization part, our algorithm constructs a regularized classifier for each data point using its neighborhood, while the global regularization part adopts a Laplacian regularizer to smooth the data labels predicted by those local classifiers. We show that such a learning framework can easily be incorporated into either unsupervised learning, semi-supervised learning, and supervised learning paradigm. Moreover, many existing learning algorithms can be derived from our framework. Finally we present some experimental results to show the effectiveness of our method. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate the online scheduling problem on two uniform machines, where the last job of each machine can be reassigned after all jobs have been assigned. The objective is to minimize the makespan. We prove that the classical List Scheduling algorithm with the competitive ratio is optimal for , where is the speed ratio between the two machines. Also, we prove the lower bound for and design an algorithm that matches the bound. [Copyright &y& Elsevier]

Abstract: In this paper, we introduce the idea of abstraction-based diagnosability for large-scale composed discrete event systems that consist of multiple subsystems. To this end, we determine sufficient conditions such that diagnosability of the original system follows from diagnosability of an abstracted system model on a smaller state space. In addition, we prove that also the reverse implication is true if an additional requirement for the abstraction is fulfilled. Then, we show how our method can be applied to compute abstracted models for the diagnosability verification of composed systems without enumerating the whole system state space. In this way, considerable computational savings can be achieved as illustrated by a small manufacturing system example. [Copyright &y& Elsevier]

Abstract: Flexible job-shop scheduling problem (FJSP) is an extension of the classical job-shop scheduling problem. FJSP is NP-hard and mainly presents two difficulties. The first one is to assign each operation to a machine out of a set of capable machines, and the second one deals with sequencing the assigned operations on the machines. This paper proposes a parallel variable neighborhood search (PVNS) algorithm that solves the FJSP to minimize makespan time. Parallelization in this algorithm is based on the application of multiple independent searches increasing the exploration in the search space. The proposed PVNS uses various neighborhood structures which carry the responsibility of making changes in assignment and sequencing of operations for generating neighboring solutions. The results obtained from the computational study have shown that the proposed algorithm is a viable and effective approach for the FJSP. [Copyright &y& Elsevier]

Abstract: For decades, researchers and practitioners have been trying to develop and deploy prognostics technologies with ad hoc and trial-and-error approaches. These efforts have resulted in limited success, due to the fact that it lacks a systematic approach and platform in deploying the right prognostics tools for the right applications. This paper introduces a methodology for designing a reconfigurable prognostics platform (RPP) which can be easily and effectively used to assess and predict the performance of machine tools. RPP can be installed on the equipment and it has the prognostic capabilities to convert the data into performance-related information. The equipment performance information can then be integrated into the enterprise asset management system for maintenance decision making through the Internet. Two industrial cases are used to validate the effectiveness of applying the RPP for different prognostic applications as well as the reconfigurable capabilities of the proposed RPP. [Copyright &y& Elsevier]

Abstract: The concept of an automaton group generalizes easily to semigroups, and the systematic study of this area is beginning. This paper aims to contribute to that study. The basic theory of automaton semigroups is briefly reviewed. Various natural semigroups are shown to arise as automaton semigroups. The interaction of certain semigroup constructions with the class of automaton semigroups is studied. Semigroups arising from Cayley automata are investigated. Various open problems and areas for further research are suggested. [Copyright &y& Elsevier]

Abstract: Splicing systems are generative devices of formal languages, introduced by Head in 1987 to model biological phenomena on linear and circular DNA molecules. A splicing system is defined by giving an initial set and a set of rules. Some unanswered questions are related to the computational power of circular splicing systems. In particular, a still open question is to find a characterization of circular languages generated by finite circular splicing systems (i.e., circular splicing systems with both and finite sets). In this paper we introduce a special class of the latter systems named marked systems. We prove that a marked system generates a regular circular language if and only if satisfies a special (decidable) property. As a consequence, we are able to characterize the structure of these regular circular languages. [Copyright &y& Elsevier]

Abstract: We consider in this paper the scheduling of families of jobs in which both processing and delivery are coordinated together. Only one vehicle is available to deliver the jobs to specified customers. The jobs can be processed together to form processing batches on the machine and setups of batches are required when the machine is changing from one family to another. Jobs from different families cannot be transported together by the vehicle. The objective is to minimize the time when the vehicle finishes delivering the last delivery batch to its customer and returns to the machine. We propose an -time optimal algorithm for the scheduling problem under the group technology assumption. For the scheduling problem without the group technology assumption, we show that the problem is NP-hard and give an -time dynamic programming algorithm, where is the number of jobs, and is the number of families; we also provide a heuristic algorithm with a performance ratio of 3/2. [Copyright &y& Elsevier]

Abstract: In this paper, we investigate a minimum time problem for controlled non-autonomous differential systems, with dynamics depending on the final time. The minimal time function associated to this problem does not satisfy the dynamic programming principle. However, we will prove that it is related to a standard front propagation problem via the reachability function. Two simple numerical examples are given to illustrate our approach. [Copyright &y& Elsevier]

Abstract: The recently published edge- and lookup table-based inverse halftoning (ELIH) algorithm has shown its quality and superiority when compared with the previous lookup table-based IH algorithm. This paper presents a new finite state machine model (FSMM)-based search method to speed up the existing ELIH algorithm significantly while preserving the same image quality as in the ELIH algorithm. From the observation that the sliding window for the ELIH algorithm moves from left to right one position; there are therefore one output column and one input column which are introduced at each step and thus a simple finite state machine can track the transitions from the current window movement to the next. This is faster than a full search in the lookup table. Under thirty typical testing images adopted from Meşe’s website, experimental results demonstrated that the proposed FSMM-based ELIH algorithm has an improvement in execution time of 20% to 80%, with a typical improvement of 50%, when compared to the ELIH algorithm. [Copyright &y& Elsevier]

Abstract: We show that the absolute worst case time complexity for Hopcroft’s minimization algorithm applied to unary languages is reached only for deterministic automata or cover automata following the structure of the de Bruijn words. A previous paper by Berstel and Carton gave the example of de Bruijn words as a language that requires steps in the case of deterministic automata by carefully choosing the splitting sets and processing these sets in a FIFO mode for the list of the splitting sets in the algorithm. We refine the previous result by showing that the Berstel/Carton example is actually the absolute worst case time complexity in the case of unary languages for deterministic automata. We show that the same result is valid also for the case of cover automata and an algorithm based on the Hopcroft’s method used for minimization of cover automata. We also show that a LIFO implementation for the splitting list will not achieve the same absolute worst time complexity for the case of unary languages both in the case of regular deterministic finite automata or in the case of the deterministic finite cover automata as defined by S. Yu. [Copyright &y& Elsevier]

Abstract: It is known that a nontrivial automorphism on a given graph is computed by using any oracle that computes a pair of vertices such that is mapped to by some nontrivial automorphism. In this paper, we consider a weaker oracle acting as follows. For a given graph, the oracle returns a pair of a vertex and a bit with the promise that if it returns , then the vertex is fixed by some nontrivial automorphism, but if it returns , then the vertex is moved by some nontrivial automorphism, provided that the given graph has a nontrivial automorphism. We here note that the oracle may return an arbitrary pair as its answer in case that the given graph has no nontrivial automorphism. We then show a stronger result that such an oracle is still powerful enough to compute a nontrivial automorphism. We also show that a similar result holds for RightGA, a GA-complete problem. We further investigate the computational complexity of computing a partial solution for PrefixGA which is known to be GI-complete. For this problem, we show that, when we consider any oracle similar to one mentioned above, the oracle does not help us to solve PrefixGA unless GI GA. [Copyright &y& Elsevier]

Abstract: In this paper we study the topological directional entropy of -actions generated by one-dimensional linear cellular automata and the shift map acting on compact metric space . We give a formula, which can be efficiently and rightly computed by means of the coefficients of the local rule , for the topological directional entropy of -action generated by the pair in the direction (). We also generalize the results obtained by Akın [H. Akin, The topological entropy of invertible cellular automata, J. Comput. Appl. Math. 213 (2) (2008) 501–508] to the topological entropy of any invertible one-dimensional linear cellular automata. [Copyright &y& Elsevier]

Abstract: This paper is a note on how Information Theory and Codification Theory are helpful in the computational design of both communication protocols and strategy sets in the framework of finitely repeated games played by bounded rational agents. More precisely, we show the usefulness of both theories to improve the existing automata bounds on the work of Neyman (1998) Finitely repeated games with finite automata, Mathematics of Operations Research, 23 (3), 513–552. [Copyright &y& Elsevier]

Abstract: Representing and reasoning about time dependent information is a key research issue in many areas of computer science and artificial intelligence. One of the best known and widely used formalisms for representing interval-based qualitative temporal information is Allen''s interval algebra (IA). The fundamental reasoning task in IA is to find a scenario that is consistent with the given information. This problem is in general NP-complete. In this paper, we investigate how an interval-based representation, or IA network, can be encoded into a propositional formula of Boolean variables and/or predicates in decidable theories. Our task is to discover whether satisfying such a formula can be more efficient than finding a consistent scenario for the original problem. There are two basic approaches to modelling an IA network: one represents the relations between intervals as variables and the other represents the end-points of each interval as variables. By combining these two approaches with three different Boolean satisfiability (SAT) encoding schemes, we produced six encoding schemes for converting IA to SAT. In addition, we also showed how IA networks can be formulated into satisfiability modulo theories (SMT) formulae based on the quantifier-free integer difference logic (QF-IDL). These encodings were empirically studied using randomly generated IA problems of sizes ranging from 20 to 100 nodes. A general conclusion we draw from these experimental results is that encoding IA into SAT produces better results than existing approaches. More specifically, we show that the new point-based 1-D support SAT encoding of IA produces consistently better results than the other alternatives considered. In comparison with the six different SAT encodings, the SMT encoding came fourth after the point-based and interval-based 1-D support schemes and the point-based direct scheme. Further, we observe that the phase transition region maps directly from the IA encoding to each SAT or SMT encoding, but, surprisingly, the location of the hard region varies according to the encoding scheme. Our results also show a fixed performance ranking order over the various encoding schemes. [Copyright &y& Elsevier]

Abstract: Two quantum finite automata are equivalent if for any input string the two automata accept with equal probability. In this paper, we first focus on determining the equivalence for one-way quantum finite automata with control language (CL-1QFAs) defined by Bertoni et al., and then, as an application, we address the equivalence problem for measure-many one-way quantum finite automata (MM-1QFAs) introduced by Kondacs and Watrous. More specifically, we obtain that: [(i)] Two CL-1QFAs and with control languages (regular languages) and , respectively, are equivalent if and only if they are -equivalent, where and are the numbers of states in and , respectively, and and are the numbers of states in the minimal DFAs that recognize and , respectively. Furthermore, if and are given in the form of DFAs, with and states, respectively, then there exists a polynomial-time algorithm running in time that takes as input and and determines whether they are equivalent. [(ii)] (As an application of item (i)): Two MM-1QFAs and with and states, respectively, are equivalent if and only if they are -equivalent. Furthermore, there is a polynomial-time algorithm running in time that takes as input and and determines whether and are equivalent. [Copyright &y& Elsevier]

Abstract: The controllability of viscoelastic fields is a fundamental concept that defines some essential capabilities and limitations of the resulting materials. In this paper, we study the controllability of different homogeneous flow fields of viscoelastic fluids governed by the upper convected Maxwell model. The approach is largely based on the nonlinear geometric control theory. Through the analysis of the control Lie algebra, we find the submanifolds in the state space on which the homogeneous flow fields are weakly controllable. Our approach can be generalized to more complicated systems. [Copyright &y& Elsevier]

Abstract: In this paper, a closed-loop fast sampling analysis of a discretized (emulated) continuous-time controller in a sampled-data environment is presented. The analysis involves a general weighted version of the -norm. This allows a qualitative and quantitative stability and performance analysis for an emulated controller. Several examples are used to show the relevance of these results for the analysis of sampled-data implementations and the computation of quantitative upper limits on the sampling period to achieve recovery of stability and performance. [Copyright &y& Elsevier]

Abstract: Measuring the structural similarity of graphs is a challenging and outstanding problem. Most of the classical approaches of the so-called exact graph matching methods are based on graph or subgraph isomorphic relations of the underlying graphs. In contrast to these methods in this paper we introduce a novel approach to measure the structural similarity of directed and undirected graphs that is mainly based on margins of feature vectors representing graphs. We introduce novel graph similarity and dissimilarity measures, provide some properties and analyze their algorithmic complexity. We find that the computational complexity of our measures is polynomial in the graph size and, hence, significantly better than classical methods from, e.g. exact graph matching which are NP-complete. Numerically, we provide some examples of our measure and compare the results with the well-known graph edit distance. [Copyright &y& Elsevier]

Abstract: In this paper, we use resource-bounded dimension theory to investigate polynomial size circuits. We show that for every , has ith-order scaled -strong dimension 0. We also show that has -dimension and -strong dimension 1. Our results improve previous measure results of Lutz [Almost everywhere high nonuniform complexity, J. Comput. Syst. Sci. 44(2) (1992) 220–258] and dimension results of Hitchcock and Vinodchandran [Dimension, entropy rates, and compression, in: Proc. 19th IEEE Conf. Computational Complexity, 2004, pp. 174–183, J. Comput. Syst. Sci., to appear]. Additionally, we establish a Supergale Dilation Theorem, which extends the martingale dilation technique introduced implicitly by Ambos-Spies, Terwijn, and Zheng [Resource bounded randomness and weakly complete problems, Theoret. Comput. Sci. 172(1–2) (1997) 195–207] and made explicit by Juedes and Lutz [Weak completeness in E and , Theoret. Comput. Sci. 143(1) (1995) 149–158]. [Copyright &y& Elsevier]

Abstract: The extension of the duration calculus (DC) by iteration, which is also known as Kleene star, enables the straightforward specification of repetitive behaviour in DC and facilitates the translation of design descriptions between DC, timed regular expressions and timed automata. In this paper we present axioms and a proof rule about iteration in DC. We consider abstract-time DC and its extension by a state-variable binding existential quantifier known as higher-order DC (HDC). We show that the -complete proof systems for DC and HDC known from our earlier work can be extended by our axioms and rule in various ways in order to axiomatise iteration completely. The additions we propose include either the proof rule or an induction axiom. We also present results on the decidability of a subset of the extension of DC by iteration. [Copyright &y& Elsevier]

Abstract: The aim of this paper is to study the first-order theory of the successor, interpreted on finite words. More specifically, we are interested in the hierarchy based on quantifier alternations (or -hierarchy). It was known (J. Comput. Syst. Sci. 25 (1982) 360–375) that this hierarchy collapses at level 2, but the expressive power of the lower levels was not characterized effectively. We give a semigroup theoretic description of the expressive power of , the boolean combinations of existential formulas. We also give an -time algorithm to decide whether the language accepted by a deterministic n-state automaton is expressible by a first-order sentence (respectively, a -sentence). [Copyright &y& Elsevier]

Abstract: A classical result by Rabin states that if a set of trees and its complement are both Büchi definable in the monadic second order logic, then these sets are weakly definable. In the language of -calculi, this theorem asserts the equality between the complexity classes and of the fixed-point alternation-depth hierarchy of the -calculus of tree languages. It is natural to ask whether at higher levels of the hierarchy the ambiguous classes and the composition classes are equal, and for which -calculi. The first result of this paper is that the alternation-depth hierarchy of the games -calculus—whose canonical interpretation is the class of all complete lattices—enjoys this property. More explicitly, every parity game which is equivalent both to a game in and to a game in is also equivalent to a game obtained by composing games in and . The second result is that the alternation-depth hierarchy of the -calculus of tree languages does not enjoy the property. Taking into account that any Büchi definable set is recognized by a nondeterministic Büchi automaton, we generalize Rabin''s result in terms of the following separation theorem: if two disjoint languages are recognized by nondeterministic automata, then there exists a third language recognized by an alternating automaton in containing one and disjoint from the other. Finally, we lift the results obtained for the -calculus of tree languages to the propositional modal -calculus: ambiguous classes do not coincide with composition classes, but a separation theorem is established for disjunctive formulas. [Copyright &y& Elsevier]

Abstract: It is well known that the Kolmogorov equation plays an important role in applied science. For example, the nonlinear filtering problem, which plays a key role in modern technologies, was solved by Yau and Yau [1] by reducing it to the off-line computation of the Kolmogorov equation. In this paper, we develop a theorical foundation of using the wavelet-Galerkin method to solve linear parabolic P.D.E. We apply our theory to the Kolmogorov equation. We give a rigorous proof that the solution of the Kolmogorov equation can be approximated very well in any finite domain by our wavelet-Galerkin method. An example is provided by using Daubechies D 4 scaling functions. [Copyright &y& Elsevier]