Functional networks for B-spline surface reconstruction

Recently, a new extension of the standard neural networks, the so-called functional networks, has been described [E. Castillo, Functional networks, Neural Process. Lett. 7 (1998) 151–159]. This approach has been successfully applied to the reconstruction of a surface from a given set of 3D data points assumed to lie on unknown Bézier [A. Iglesias, A. Gálvez, Applying functional networks to CAGD: the tensor-product surface problem, in: D. Plemenos (Ed.), Proceedings of the International Conference on Computer Graphics and Artificial Intelligence, 3IA’2000, 2000, pp. 105–115; A. Iglesias, A. Gálvez, A new artificial intelligence paradigm for computer-aided geometric design, in: Artificial Intelligence and Symbolic Computation, J.A. Campbell, E. Roanes-Lozano (Eds.), Lectures Notes in Artificial Intelligence, Berlin, Heidelberg, Springer-Verlag, vol. 1930, 2001, pp. 200–213] and B-spline tensor-product surfaces [A. Iglesias, A. Gálvez, Applying functional networks to fit data points from B-spline surfaces, in: H.H.S. Ip, N. Magnenat-Thalmann, R.W.H. Lau, T.S. Chua (Eds.), Proceedings of the Computer Graphics International, CGI’2001, IEEE Computer Society Press, Los Alamitos, CA, 2001, pp. 329–332]. In both cases the sets of data were fitted using Bézier surfaces. However, in general, the Bézier scheme is no longer used for practical applications. In this paper, the use of B-spline surfaces (by far the most common family of surfaces in surface modeling and industry) for the surface reconstruction problem is proposed instead. The performance of this method is discussed by means of several illustrative examples. A careful analysis of the errors makes it possible to determine the number of B-spline surface fitting control points that best fit the data points. This analysis also includes the use of two sets of data (the training and the testing data) to check for overfitting, which does not occur here.     

A correction to “Nonmonotonic inconsistency” [Artificial Intelligence 149 (2003) 161–178]

This note corrects an error in the statement and proof of Propositions 9 and 10 of [C. Cross, Nonmonotonic inconsistency, Artificial Intelligence 149 (2) (2003) 161–178]. Both results turn out to depend on the postulate of Consistency Preservation.     

A genetic algorithm approach to measurement prescription in fault diagnosis

To fully discriminate among all possible diagnoses in a fault diagnosis task, one needs to take measurements from the system being diagnosed. The primary effects of taking one measurement in diagnosis based on first principles were presented in A. Reiter [Artificial Intelligence (32) (1987) 57–95] and a more detailed, formal account was given in A. Hou [Artificial Intelligence (65) (1994) 281–328]. However, the order in which measurements are to be taken is an issue. We propose a genetic algorithm to determine a good measurement order for a diagnosis task. The method applies operators such as selection, crossover, and mutation to evolve an initial population of measurement sequences. The quality of a measurement sequence is evaluated based on the cost taken for the measurement sequence to find the final diagnosis. Experiments on testing circuits have shown that the quality of measurement sequences is greatly improved after evolution.     

The future of artificial intelligence (AI) in manufacturing

Artificial Intelligence (AI) is now among the buzzwords in manufacturing. Articles are written about various aspects of AI in manufacturing and some of these are discussed by Miller in “Artificial Intelligence: Applications for Manufacturing” [1]. Most of those authors extol the virtues of AI in manufacturing. From some of the literature, one might draw the conclusion that AI will solve all of our problems.

AI technologies are very sophisticated and are not going to easily accomodate the “noise” of the factory floor. We can see some of these techniques beginning to make inroads into manufacturing, but the road to full-scale implementation will be a rocky one.     

Erratum to: Reasoning with infinite stable models [Artificial Intelligence 156 (1) (2004) 75-111]

Theorem 16 in [Piero A. Bonatti, Reasoning with infinite stable models, Artificial Intelligence 156 (1) (2004) 75-111] states that ground skeptical and credulous inferences under the stable model semantics are decidable when the given normal logic program is finitary. Giovanni Criscuolo and Nicola Leone independently observed in personal communications that the proof of this theorem relies on an unproved assumption that—at the best of our current knowledge—might turn out to be false. In this note we correct Theorem 16 by adding the set of odd-cyclic atoms to the inputs of the computation, and argue that this change has no impact on the current applications of the theory of finitary programs.     

On the approximation problem of common fixed points for a finite family of non-self asymptotically quasi-nonexpansive-type mappings in Banach spaces

The purpose of this paper is to introduce the concept of non-self asymptotically quasi-nonexpansive-type mappings and to construct a iterative sequence to converge to a common fixed point for a finite family of non-self asymptotically quasi-nonexpansive-type mappings in Banach spaces. The results presented in this paper improve and extend the corresponding results in Alber, Chidume and Zegeye [Ya.I. Alber, C.E. Chidume, H. Zegeye, Approximating of total asymptotically nonexpansive mappings, Fixed Point Theory and Applications (2006) 1–20. Article ID10673], Ghosh and Debnath [M.K. Ghosh, L. Debnath, Convergence of Ishikawa iterates of quasi-nonexpansive mappings, Journal of Mathematical Analysis and Applications 207 (1997) 96–103], Liu [Q.H. Liu, Iterative sequences for asymptotically quasi-nonexpansive type mappings, Journal of Mathematical Analysis and Applications 259 (2001) 1–37; Q.H. Liu, Iterative sequences for asymptotically quasi-nonexpansive mappings with error member, Journal of Mathematical Analysis and Applications 259 (2001) 18–24; Q.H. Liu, Iteration sequences for asymptotically quasi-nonexpansive mapping with an error member of uniform convex Banach space, Journal of Mathematical Analysis and Applications 266 (2002) 468–471], Petryshyn [W.V. Petryshyn, T.E. Williamson Jr., Strong and weak convergence of the sequence of successive approximations for quasi-nonexpansive mappings, Journal of Mathematical Analysis and Applications 43 (1973) 459–497], Quan and Chang [J. Quan, S.S. Chang, X.J. Long, Approximation common fixed point of asymptotically quasi-nonexpansive type mappings by the finite steps iterative sequences, Fixed Point Theory and Applications V (2006) 1–38. Article ID 70830], Shahzad and Udomene [N. Shahzad, A. Udomene, Approximating common fixed point of two asymptotically quasi-nonexpansive mappings in Banach spaces, Fixed Point Theory and Applications (2006) 1–10. Article ID 18909] Xu [B.L. Xu, M.A. Noor, Fixed-point iterations for asymptotically nonexpansive mappings in Banach spaces, Journal of Mathematical Analysis and Applications 267 (2002) 444–453], Zhang [S.S. Zhang, Iterative approximation problem of fixed points for asymptotically nonexpansive mappings in Banach spaces, Acta Mathematicae Applicatae Sinica 24 (2001) 236–241] and Zhou and Chang [Y.Y. Zhou, S.S. Chang, Convergence of implicit iteration process for a finite family of asymptotically nonexpansive mappings in Banach spaces, Numerical Functional Analysis and Optimization 23 (2002) 911–921].     

Computing ideal sceptical argumentation

We present two dialectic procedures for the sceptical ideal semantics for argumentation. The first procedure is defined in terms of dispute trees, for abstract argumentation frameworks. The second procedure is defined in dialectical terms, for assumption-based argumentation frameworks. The procedures are adapted from (variants of) corresponding procedures for computing the credulous admissible semantics for assumption-based argumentation, proposed in [P.M. Dung, R.A. Kowalski, F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence 170 (2006) 114–159]. We prove that the first procedure is sound and complete, and the second procedure is sound in general and complete for a special but natural class of assumption-based argumentation frameworks, that we refer to as p-acyclic. We also prove that in the case of p-acyclic assumption-based argumentation frameworks (a variant of) the procedure of [P.M. Dung, R.A. Kowalski, F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence 170 (2006) 114–159] for the admissible semantics is complete. Finally, we present a variant of the procedure of [P.M. Dung, R.A. Kowalski, F. Toni, Dialectic proof procedures for assumption-based, admissible argumentation, Artificial Intelligence 170 (2006) 114–159] that is sound for the sceptical grounded semantics.     

Relation between powers of factors and the recurrence function characterizing Sturmian words

In this paper we use the relation of the index of an infinite aperiodic word and its recurrence function to give another characterization of Sturmian words. As a by-product, we give a new proof of the theorem describing the index of a Sturmian word in terms of the continued fraction expansion of its slope. This theorem was independently proved in [A. Carpi, A. de Luca, Special factors, periodicity, and an application to Sturmian words, Acta Inform. 36 (2000) 983–1006] and [D. Damanik, D. Lenz, The index of Sturmian sequences, European J. Combin. 23 (2002) 23–29].     

Relation-algebraic semantics

The first half is a tutorial on orderings, lattices, Boolean algebras, operators on Boolean algebras, Tarski's fixed point theorem, and relation algebras.

In the second half, elements of a complete relation algebra are used as “meanings” for program statements. The use of relation algebras for this purpose was pioneered by de Bakker and de Roever in [10–12]. For a class of programming languages with program schemes, single μ-recursion, while-statements, if-then-else, sequential composition, and nondeterministic choice, a definition of “correct interpretation” is given which properly reflects the intuitive (or operational) meanings of the program constructs. A correct interpretation includes for each program statement an element serving as “input/output relation” and a domain element specifying that statement's “domain of nontermination”. The derivative of Hitchcock and Park [17] is defined and a relation-algebraic version of the extension by de Bakker [8, 9] of the Hitchcock-Park theorem is proved. The predicate transformers wp_s(-) and wlp_s(-) are defined and shown to obey all the standard laws in [15]. The “law of the excluded miracle” is shown to hold for an entire language if it holds for that language's basic statements (assignment statements and so on). Determinism is defined and characterized for all the program constructs. A relation-algebraic version of the invariance theorem for while-statements is given. An alternative definition of intepretation, called “demonic”, is obtained by using “demonic union” in place of ordinary union, and “demonic composition” in place of ordinary relational composition. Such interpretations are shown to arise naturally from a special class of correct interpretations, and to obey the laws of wp_s(-).     

HARP: A tableau-based theorem prover

This paper presents HARP, a complete, tableau-based theorem prover for first order logic, which is intended to be used both interactively and as an inference engine for Artificial Intelligence applications. Accordingly, HARP's construction is influenced by the design goals of naturalness, efficiency, usefulness in an Artificial Intelligence environment, and modifiability of the control structure by heuristics. To achieve these goals, HARP accepts the entire language of first order logic, i.e. avoids conversion to any kind of normal form, and combines a proof condensation procedure with explicitly represented, declaratively formulated heuristics to construct and communicate its proofs in a format congenial to people. The proof condensation procedure makes proof shorter and more readable by excising redundancies from proof trees. Domain-independent heuristics are formulated to capture efficient and human-like deduction strategies and to rapidly detect certain types of nontheorems. Domain-dependent heuristics can be used to implement specific control regimes, e.g. to efficiently support inheritance. HARP's architecture-and the concomitant ready extensibility of its control structure by declarative heuristic rules-renders it easy to let extralogical information, e.g. semantic and world knowledge, guide the search for proofs and help eliminate irrelevant premisses.     

Two ant-colony algorithms for minimizing total flowtime in permutation flowshops

The problem of scheduling in flowshops with the objective of minimizing total flowtime is studied. For solving the problem two ant-colony algorithms are proposed and analyzed. The first algorithm refers to some extent to ideas by Stuetzle [Stuetzle, T. (1998). An ant approach for the flow shop problem. In: Proceedings of the sixth European Congress on intelligent techniques and soft computing (EUFIT '98) (Vol. 3) (pp. 1560–1564). Aachen: Verlag Mainz] and Merkle and Middendorf [Merkle, D., & Middendorf, M. (2000). An ant algorithm with a new pheromone evaluation rule for total tardiness problems. In: Proceedings of the EvoWorkshops 2000, lecture notes in computer science 1803 (pp. 287–296). Berlin: Springer]. The second algorithm is newly developed. The proposed ant-colony algorithms have been applied to 90 benchmark problems taken from Taillard [Taillard, E. (1993). Benchmarks for basic scheduling problems. European Journal of Operational Research, 64, 278–285]. A comparison of the solutions yielded by the ant-colony algorithms with the best heuristic solutions known for the benchmark problems up to now, as published in extensive studies by Liu and Reeves [Liu, J., & Reeves, C.R. (2001). Constructive and composite heuristic solutions to the P//ΣC_i scheduling problem. European Journal of Operational Research, 132, 439–452, and Rajendran and Ziegler [Rajendran, C., & Ziegler, H. (2004). Ant-colony algorithms for permutation flowshop scheduling to minimize makespan/total flowtime of jobs. European Journal of Operational Research, 155, 426–438], shows that the presented ant-colony algorithms are better, on an average, than the heuristics analyzed by Liu and Reeves and Rajendran and Ziegler.     

A new approach to the periodicity lemma on strings with holes

We first give an elementary proof of the periodicity lemma for strings containing one hole (variously called a “wild card”, a “don’t-care” or an “indeterminate letter” in the literature). The proof is modelled on Euclid’s algorithm for the greatest common divisor and is simpler than the original proof given in [J. Berstel, L. Boasson, Partial words and a theorem of Fine and Wilf, Theoret. Comput. Sci. 218 (1999) 135–141]. We then study the two-hole case, where our result agrees with the one given in [F. Blanchet-Sadri, Robert A. Hegstrom, Partial words and a theorem of Fine and Wilf revisited, Theoret. Comput. Sci. 270 (1-2) (2002) 401–419] but is more easily proved and enables us to identify a maximum-length prefix or suffix of the string to which the periodicity lemma does apply. Finally, we extend our result to three or more holes using elementary methods, and state a version of the periodicity lemma that applies to all strings with or without holes. We describe an algorithm that, given the locations of the holes in a string, computes maximum-length substrings to which the periodicity lemma applies, in time proportional to the number of holes. Our approach is quite different from that used by Blanchet-Sadri and Hegstrom, and also simpler.     

A Prolog simulator for deterministic P systems with active membranes

In this paper we propose a new way to represent P systems with active membranes based on Logic Programming techniques. This representation allows us to express the set of rules and the configuration of the P system in each step of the evolution as literals of an appropriate language of first order logic. We provide a Prolog program to simulate, the evolution of these P systems and present some auxiliary tools to simulate the evolution of a P system with active membranes using 2-division which solves the SAT problem following the techniques presented in Reference.¹⁰ Andrés Cordón-Franco: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Mathematical Logic, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical (software implementation) point of view. Miguel A. Gutiérrez-Naranjo: He is an assistant professor in the Computer Science and Artificial Intelligence Department at University of Sevilla, Spain. He is also a member of the Research Group on Natural Computing of the University of Seville. His research interest includes Machine Learning, Logic Programming and Membrane Computing, both from a theoretical and a practical point of view. Mario J. Pérez-Jiménez, Ph.D.: He is professor of Department of Computer Science and Artificial Intelligence at University of Seville, where he is the head of the Group of Research on Natural Computing, He has published 8 books of Mathematics and Computation, and more than 90 scientific articles in prestigious scientific journals. He is member of European Molecular Computing Consortium. Fernando Sancho-Caparrini: He is a member of the Department of Computer Science and Artificial Intelligence at the University of Sevilla (Spain). He is also a member of the research group on Natural Computing of the University of Seville. His research interest includes Complex Systems, DNA Computing, Logic in Computer Science, and Membrane Computing, both from a theoretical and from a practical point of view.     

Remarks on “optimal stochastic control for discrete-time linear system with interrupted observations”

In the paper by Fujita and Fukao [1], a proof of the separation theorem for discrete-time linear systems with interrupted observations was presented. The theorem is based heavily on [1, Lemma]. This note points out errors of the proof of [1, Lemma] and disproves the separation theorem.     

Program proving: Coroutines

Summary Proof methods adequate for a wide range of computer programs have been given in [1–6]. This paper develops a method suitable for programs which incorporate coroutines. The implementation of coroutines described follows closely that given in SIMULA [7, 8], a language in which such features may be used to great advantage. Proof rules for establishing the correctness of coroutines are given and the method is illustrated by the proof of a useful program for histogram compilation.     

Systematic studies on responses of metal-oxide sensor surfaces to straight chain alkanes, alcohols, aldehydes, ketones, acids and esters using the SOMMSA approach

Metal oxide sensors are widely used in the so-called “electronic noses”, and it is proposed that these equipment can be used to objectify food aromas.

Due to the fact that, up to now, systematic approaches to correlate the intensity of sensor responses with the structure of a given volatile have scarcely been performed [K. Suzuki, T. Takada, Highly sensitive odour sensors using various SnO₂ thick films, Sens. Actuators, B 24–25 (1995) 773–776; B. Lalauze et al., High sensitivity materials for gas detection, Sens. Actuators, B 8 (1992) 237–243; K. Fukui, Detection and measurement of odor by sintered tin oxide gas sensor, Sens. Actuators, B 5 (1991) 27–32; J.W. Gardner, A. Pike et al., Integrated array sensor for detecting organic solvents, Sens. Actuators, B 13–14 (1993) 355–357.], it is as yet not possible to predict the sensitivity and the specivity of metal oxide preparations vs. a given chemical structure.

Using the SOMMSA approach [T. Hofmann et al., High resolution gas chromatography/selective odorant measurement by multisensor array (HRGC/SOMSA): a useful approach to standardize multisensor arrays for the use in the detection of key food odorants, Sens. Actuators, B 41 (1997) 81–87.], mixtures of alkanes, alcohols, aldehydes (all with chain length of 8–14 carbon atoms) and acids (chain length of 2–10 carbon atoms) were applied to different self-prepared metal oxide mixtures and the signal intensities were monitored. In addition, quantitative experiments were performed to determine the detection threshold of sensors. E.g. (E,E)-2,4-nonadienal, one of the most important odorants in fresh cucumbers, could be clearly detected at a level below 4.0 ng/ml (He) by a sensor containing a mixture of ZnO and SnO₂.     

Conservative constraint satisfaction re-revisited

Conservative constraint satisfaction problems (CSPs) constitute an important particular case of the general CSP, in which the allowed values of each variable can be restricted in an arbitrary way. Problems of this type are well studied for graph homomorphisms. A dichotomy theorem characterizing conservative CSPs solvable in polynomial time and proving that the remaining ones are NP-complete was proved by Bulatov (2003) in [4]. Its proof, however, is quite long and technical. A shorter proof of this result based on the absorbing subuniverses technique was suggested by Barto (2011) in [1]. In this paper we give a short elementary proof of the dichotomy theorem for conservative CSPs.     

A causal approach to nonmonotonic reasoning

We introduce logical formalisms of production and causal inference relations based on input/output logics of Makinson and Van der Torre [J. Philos. Logic 29 (2000) 383–408]. These inference relations will be assigned, however, both standard semantics (giving interpretation to their rules), and natural nonmonotonic semantics based on the principle of explanation closure. The resulting nonmonotonic formalisms will be shown to provide a logical representation of abductive reasoning, and a complete characterization of causal nonmonotonic reasoning from McCain and Turner [Proc. AAAI-97, Providence, RI, 1997, pp. 460–465]. The results of the study suggest production and causal inference as general nonmonotonic formalisms providing an alternative representation for a significant part of nonmonotonic reasoning.     

What evolutionary game theory tells us about multiagent learning

This paper discusses If multi-agent learning is the answer, what is the question? [Y. Shoham, R. Powers, T. Grenager, If multi-agent learning is the answer, what is the question? Artificial Intelligence 171 (7) (2007) 365-377, this issue] from the perspective of evolutionary game theory. We briefly discuss the concepts of evolutionary game theory, and examine the main conclusions from [Y. Shoham, R. Powers, T. Grenager, If multi-agent learning is the answer, what is the question? Artificial Intelligence 171 (7) (2007) 365-377, this issue] with respect to some of our previous work. Overall we find much to agree with, concluding, however, that the central concerns of multiagent learning are rather narrow compared with the broad variety of work identified in [Y. Shoham, R. Powers, T. Grenager, If multi-agent learning is the answer, what is the question? Artificial Inteligence 171 (7) (2007) 365-377, this issue].     

Equivalence of the Gries and Martin proof rules for procedure calls

Summary In this note we prove the equivalence of the proof rules for procedure calls as given by D. Gries [1] and A.J. Martin [2]. We also discuss a modification of these proof rules for the case that the specification of a procedure contains free constants.