44358650
Banishing Robust Turing Completeness
This paper proves that “promise classes” are so fragilely structured that they do not robustly (i.e. with respect to all oracles) possess Turinghard sets even in classes far larger than themselves. In particular, this paper shows that FewP does not robustly possess Turing hard sets for UP∩coUP and IP∩coIP does not robustly possess Turing hard sets for ZPP. It follows that ZPP, R, coR, UP∩coUP, UP, FewP∩coFewP, FewP, and IP∩coIP do not robustly possess Turing complete sets. This both resolves open questions of whether promise classes lacking robust downward closure under Turing reductions (e.g., R, UP, FewP) might robustly have Turing complete sets, and extends the range of classes known not to robustly contain many-one complete sets.
39847140
Team Learning of Recursive Languages
A team of learning machines is a multiset of learning machines. A team is said to successfully learn a concept just in case each member of some nonempty subset, of predetermined size, of the team learns the concept. Team learning of languages turns out to be a suitable theoretical model for studying computational limits on multi-agent machine learning. Team learning of recursively enumerable languages has been extensively studied. However, it may be argued that from a practical point of view all languages of interest are recursive. 
 
This paper gives theoretical results about team learnability of recursive languages. These results are mainly about two issues: redundancy and aggregation. The issue of redundancy deals with the impact of increasing the size of a team and increasing the number of machines required to be successful. The issue of aggregation deals with conditions under which a team may be replaced by a single machine without any loss in learning ability. The learning scenarios considered are: (a) Identification in the limit of accepting grammars for recursive languages. (b) Identification in the limit of decision procedures for recursive languages. (c) Identification in the limit of accepting grammars for indexed families of recursive languages. (d) Identification in the limit of accepting grammars for indexed families with enumerable class of grammars for the family as the hypothesis space. Scenarios which can be modeled by team learning are also presented.
644359
Anomalous Learning Helps Succinctness
Abstract It is shown that allowing a bounded number of anomalies (mistakes) in the final programs learned by an algorithmic procedure can considerably “succinctify” those final programs. Naturally, only those contexts are investigated in which the presence of anomalies is not actually required for successful inference (learning). The contexts considered are certain infinite subclasses of the class of characteristic functions of finite sets. For each finite set D , these subclasses have a finite set containing D . This latter prevents the anomalies from wiping out all the information in the sets featured in these subclasses and shows the context to be fairly robust. Some of the results in the present paper are shown to be provably more constructive than others. The results of this paper can also be interpreted as facts about succinctness of coding finite sets, which facts have interesting consequences for learnability of decision procedures for finite sets.
145211
Computational Limits on Team Identification of Languages
A team of learning machines is a multiset of learning machines. A team is said to successfully identify a concept just in case each member of some nonempty subset, of predetermined size, of the team identifies the concept. Team identification of programs for computable functions from their graphs has been investigated by Smith. Pitt showed that this notion is essentially equivalent to function identification by a single probabilistic machine. The present paper introduces, motivates, and studies the more difficult subject of team identification of grammars for languages from positive data. It is shown that an analog of Pitt's result about equivalence of team function identification and probabilistic function identification does not hold for language identification, and the results in the present paper reveal a very complex structure for team language identification. It is also shown that for certain cases probabilistic language identification is strictly more powerful than team language identification. Proofs of many results in the present paper involve very sophisticated diagonalization arguments. Two very general tools are presented that yield proofs of new results from simple arithmetic manipulation of the parameters of known ones.
122230605
On the intrinsic complexity of learning recursive functions
The intrinsic complexity of learning compares the difficulty of learning classes of objects by using some reducibility notion. For several types of learning recursive functions, both natural complete classes are exhibited and necessary and sufficient conditions for completeness are derived. Informally, a class is complete iff both its topological structure is highly complex while its algorithmic structure is easy. Some self-describing classes turn out to be complete. Furthermore, the structure of the intrinsic complexity is shown to be much richer than the structure of the mind change complexity, though in general, intrinsic complexity and mind change complexity can behave "orthogonally".
5851955
Vacillatory Learning of Nearly Minimal Size Grammars
In Gold's influential language learning paradigm a learning machine converges in the limit to one correct grammar. In an attempt to generalize Gold's paradigm, Case considered the question whether people might converge to vacillating between up to (some integer) n > 1 distinct, but equivalent, correct grammars. He showed that larger classes of languages can be algorithmically learned (in the limit) by converging to up to n + 1 rather than up to n correct grammars. He also argued that, for ''small'' n>1, it is plausible that people might sometimes converge to vacillating between up to n grammars. The insistence on small n was motivated by the consideration that, for ''large'' n, at least one of n grammars would be too large to fit in people's heads. Of course, even for Gold's n = 1 case, the single grammar converged to in the limit may be infeasibly large. An interesting complexity restriction to make, then, on the final grammar(s) converged to in the limit is that they all have small size. In this paper we study some of the trade-offs in learning power involved in making a well-defined version of this restriction. We show and exploit as a tool the desirable property that the learning power under our size-restricted criteria (for successful learning) is independent of the underlying acceptable programming systems. We characterize the power of our size-restricted criteria and use this characterization to prove that some classes of languages, which can be learned by converging in the limit to up to n + 1 nearly minimal size correct grammars, cannot be learned by converging to up to n unrestricted grammars even if these latter grammars are allowed to have a finite number of anomalies (i.e., mistakes) per grammar. We also show that there is no loss of learning power in demanding that the final grammars be nearly minimal size iff one is willing to tolerate an unbounded, finite number of anomalies in the final grammars and there is a constant bound on the number of different grammars converged to in the limit. Hence, if we allow an unbounded, finite number of anomalies in the final grammars and the number of different grammars converged to in the limit is unbounded but finite (or if there is a constant bound on the number of anomalies allowed in the final grammars), then there is a loss of learning power in requiring that the final grammars be nearly minimal size. These results do not always match what might be expected from the cases, previously examined by Freivalds, Kinber, and Chen, of learning nearly minimal size programs for functions.
195860327
Criticality of detailed modeling in semiconductor supply chain simulation
Supply chain management offers a large potential for organizations to reduce costs and improve customer service performance. Simulation of supply chains can help in these objectives by evaluating the impact of alternative inventory control policies. Supply chain simulation involves the modeling of multiple factories across the chain and can get quite complex. Analysts typically carry out such simulation at a coarse level of detail to keep the complexity and computing resources manageable. However, modeling at coarse levels may reduce the accuracy of outputs and affect the quality of decisions. In this paper, we report on a study to compare the quality of results at different levels of detail in a semiconductor supply chain simulation.
1156882
Analytic evaluation of the expectation and variance of different performance measures of a schedule on a single machine under processing time variability
Abstract
In this paper, we present closed-form expressions, wherever possible, or devise algorithms otherwise, to determine the expectation and variance of a given schedule on a single machine. We consider a variety of completion time and due date-based objectives. The randomness in the scheduling process is due to variable processing times with known means and variances of jobs and, in some cases, a known underlying processing time distribution. The results that we present in this paper can enable evaluation of a schedule in terms of both the expectation and variance of a performance measure considered, and thereby, aid in obtaining a stable schedule. Additionally, the expressions and algorithms that are presented, can be incorporated in existing scheduling algorithms in order to determine expectation-variance efficient schedules.

47220301
Expert simulation for on-line scheduling
The state-of-the-art in manufacturing has moved toward flexibility, automation and integration. The efforts spent on bringing computer-integrated manufacturing (CIM) to plant floors have been motivated by the overall thrust to increase the speed of new products to market. One of the links in CIM is plant floor scheduling, which is concerned with efficiently orchestrating the plant floor to meet the customer demand and responding quickly to changes on the plant floor and changes in customer demand. The Expert System Scheduler (ESS) has been developed to address this link in CIM. The scheduler utilizes real-time plant information to generate plant floor schedules which honor the factory resource constraints while taking advantage of the flexibility of its components.
The scheduler uses heuristics developed by an experienced human factory scheduler for most of the decisions involved in scheduling. The expertise of the human scheduler has been built into the computerized version using the expert system approach of the discipline of artificial intelligence (AI). Deterministic simulation concepts have been used to develop the schedule and determine the decision points. As such, simulation modeling and AI techniques share many concepts, and the two disciplines can be used synergistically. Examples of some common concepts are the ability of entities to carry attributes and change dynamically (simulation—entities/attributes or transaction/parameters versus AI—frames/slots); the ability to control the flow of entities through a model of the system (simulation—conditional probabilities versus AI—production rules); and the ability to change the model based upon state variables (simulation—language constructs based on variables versus AI—pattern-invoked programs). Shannon [6] highlights similarities and differences between conventional simulation and an AI approach. Kusiak and Chen [3] report increasing use of simulation in development of expert systems.
ESS uses the synergy between AI techniques and simulation modeling to generate schedules for plant floors. Advanced concepts from each of the two areas are used in this endeavor. The expert system has been developed using frames and object-oriented coding which provides knowledge representation flexibility. The concept of “backward” simulation, similar to the AI concept of backward chaining, is used to construct the events in the schedule. Some portions of the schedule are constructed using forward or conventional simulation.
The implementation of expert systems and simulation concepts is intertwined in ESS. However, the application of the concepts from these two areas will be treated separately for ease of presentation. We will first discuss the expert system approach and provide a flavor of the heuristics. The concept of backward simulation and the motive behind it will then be explored along with some details of the implementation and the plant floor where the scheduler is currently being used. We will then highlight some advantages and disadvantages of using the expert simulation approach for scheduling, and, finally, the synergetic relationship between expert systems and simulation.
17397415
Analyzing the supply chain for a large logistics operation using simulation
This paper presents a case study of using simulation for analyzing the impact of proposed changes in the supply chain processes for a large logistics operation. The major changes explored include business process changes, and use of new supply chain software. The results of the analysis indicate that the changes in forecast accuracy provide much larger savings compared to process automation changes. A number of insights are drawn from the results of the analyses.
18971661
Development of a high-level supply chain simulation model
This paper describes an effort that involved development of a simulation model for evaluating the business processes and inventory control parameters of a logistics and distribution supply chain. A generic simulation tool, rather than a supply chain simulator, was developed for meeting customized needs of the effort. The paper describes, the approaches used to model at the selected level of abstraction, the development of interfaces for data and experimentation and the development and delivery of animation for communicating the approach and results to the client.