Adjoint machines,state-behavior machines,and duality

A process X: $\text{K}$→$\text{K}$ is output if Dyn(X)→$\text{K}$ has a right adjoint; state-behavior if Dyn(X)→X has both left and right adjoints; and adjoint if X has a right adjoint and $\text{K}$ has countable coproducts. Output processes provide the proper setting for a general theory of state observability. We give a minimal realization theory using image factorization of a total response map. We give an adjointness theory for state-behavior machines and a duality theory for adjoint machines which clarifies classical linear system duality and yields an improved duality for nondeterministic automata. Adjoint machines (machines with adjoint input processes) provide the first integration of classical sequential machines (the only state-behavior machines in the category, Set, of sets), metric machines, topological machines, linear systems, nondeterministic automata and Boolean machines. There exist state-behavior machines which are not adjoint (but not in Set).     

Adding machines and endpoints

In this paper we consider continuous maps on graphs. We give sufficient conditions for a point in the inverse limit space to be a local endpoint in terms of the dynamics of f. In particular we explore the relationship between the existence of adding machine dynamics and local endpoints.     

Flowchart machines

Let denote a conventional flowchart. Any algorithm can be represented by a flowchart. If action nodes in call then is a recursive flowchart. We show how to decompose arbitrary non-self-modifying programs into structure and atomic parts. We specifically give the synthesis procedure for a controller . can serve as the only sequencer in an execution of . If is recursive then is a pushdown machine, otherwise is a finite state machine. The next-state functionf and the output functiong of represent respectively all of the structure-, i.e. the programmer-oriented-, and all of the atomic-, i.e. the data-oriented-, parts of .f defines the flow or pattern of computations andg the actual transformations or operations on data. Thus we construct and analyze programs by constructing and analyzing their sequencers .     

Aparallel digraphs and splicing machines

The concepts of a splicing machine and of an aparalled digraph are introduced. A splicing machine is basically a means to uniquely obtain all circular sequences on a finite alphabet by splicing together circular sequences from a small finite set of “generators”. The existence and uniqueness of the central object related to an aparallel digraph, the strong component, is proved, and this strong component is shown to be the unique fixed point of a natural operator defined on sets of vertices of the digraph. A digraph is shown to be a splicing machine if and only if it is the strong component of an aparallel digraph. Motivation comes, on the applied side, from the splicing of circular sequences on a finite alphabet and, on the theoretical side, from the Banach fixed point theorem.     

Matrices, machines and behaviors

Sabadini, Walters and others have developed a categorical, machine based theory of concurrency in which there are four essential aspects: a distributive category of data-types; a bicategory Mach whose objects are data types, and whose arrows are input-output machines built from data types; a semantic category (or categories) Sem, suitable to contain the behaviors of machines, and a functor, behavior: MachSem. Suitable operations on machines and semantics are found so that the behavior functor preserves these operations. Then, if each machine is decomposable into primitive machines using these operations, the behavior of a general machine is deducible from the behavior of its parts. The theory of non-deterministic finite state automata provides an example of the paradigm and also throws some light on the classical theory of finite state automata.We describe a bicategory whose objects are natural numbers, in which an arrow M: np is a finite state automaton with n input states, p output states, and some additional internal states; we require that no transitions begin at output states or end at input states. A machine is represented by an q+n by q+p matrix. The bicategory supports additional operations: non-deterministic choice, parallel interleaving, and feedback. Enough operations are imposed on machines to show that each machine may be obtained from some atomic ones by means of the operations.The semantic category is the (Bloom-Ésik) iteration theory Mat _(X whose objects are natural numbers and whose arrows from n to p are n×p matrices with entries in the semiring of languages. The behavior functor associates to a machine M: np a matrix |M| of languages, one language to each pair of input and output states. Behavior preserves composition, feedback, takes non-deterministic choice to union, and parallel-interleaving to shuffle. Thus, behavior gives a compositional semantics to a primitive notion of concurrent processes.This work has been supported by the Australian Research Council, by CEC under grant number 6317, ASMICS II, by Italian MURST, and by the Italian CNR.Visit to Sydney supported by a grant from the Australian Research Council.Presented at the European Colloquium of Category Theory, Tours, France, 25–31 July 1994.     

OnTL-finite state machines

In this paper we introduce the notions of aTL-finite state machine,TL-retrievability,TL-separability,TL-connectivity and discuss their basic properties.     

Synergy in machines

The capability of a finite state machine constructed of component machines in a composition with feedback is shown to be greater than the capabilities of series-parallel (or cascade) compositions of these same components. A measure of the amount of feedback in a construction is defined and a hierarchy of classes of machines is obtained by increasing the amount of feedback permitted in the members of each class.     

Nonlinear optimization and support vector machines

Support Vector Machine (SVM) is one of the most important class of machine learning models and algorithms, and has been successfully applied in various fields. Nonlinear optimization plays a crucial role in SVM methodology, both in defining the machine learning models and in designing convergent and efficient algorithms for large-scale training problems. In this paper we present the convex programming problems underlying SVM focusing on supervised binary classification. We analyze the most important and used optimization methods for SVM training problems, and we discuss how the properties of these problems can be incorporated in designing useful algorithms.     

Products and decompositions of adding machines

In this paper we give several necessary and sufficient conditions for the product fK of a countable family of adding machines to be topologically conjugate to an adding machine fK. We also study decompositions of adding machines fK, of carry systems K and of K-adic topological groups ΣK, investigate the relation between these decompositions, and obtain some necessary and sufficient conditions for a K-adic topological group ΣK to be decomposable to the direct product of a family of its compact subgroups. In addition, equivalent conditions of an adding machine having a non-trivial periodic orbit factor are given, and the calculation of elements of finite orders in K-adic topological groups ΣK is discussed.     

Ordinal machines and admissible recursion theory

We generalize standard Turing machines, which work in time ω on a tape of length ω, to α-machines with time α and tape length α, for α some limit ordinal. We show that this provides a simple machine model adequate for classical admissible recursion theory as developed by G. Sacks and his school. For α an admissible ordinal, the basic notions of α-recursive or α-recursively enumerable are equivalent to being computable or computably enumerable by an α-machine, respectively. We emphasize the algorithmic approach to admissible recursion theory by indicating how the proof of the Sacks–Simpson theorem, i.e., the solution of Post’s problem in α-recursion theory, could be based on α-machines, without involving constructibility theory.     

On the synthesis of finite sequential machines

Starting from the studies of Kleene and Mealy on sequential machines, in this paper is presented a formalism which, in a sense, unifies their treatments. From the specification of the required machine behaviour in terms of events and associated output states, a uniform procedure is given for obtaining a transition table and from that a minimal machine, whenever such a complete reduction is possible. The various steps of the synthesis procedure are so stated that they can be easily programmed on a computer.     

OnTL-subsystems ofTL-finite state machines

In this paper we introduce the notions ofTL-subsystems, strongTL-subsystems and discuss their basic properties.     

Modeling the interrelationship between downtimes and uptimes of CNC machines

Plant and equipment represent over 50% of the assets in most manufacturing industries. New technologies such as FMS are having a pervasive effect on technology adoption rates and the resultant productivity gains. The acquisition of CNC machines, which is an integral part of FMS, has been justified on financial grounds; however, this does not take the breakdown behavior of these machines into consideration. The downtime resulting from these breakdown leads to loss of productivity. In this paper an attempt has been made to determine the interrelationship between the downtimes and uptimes of CNC machines using transfer function modeling. The models are tested using data from a farm equipment manufacturer.     

Semismooth support vector machines

Support vector machines can be posed as quadratic programming problems in a variety of ways. This paper investigates a formulation using the two-norm for the misclassification error that leads to a positive definite quadratic program with a single equality constraint under a duality construction. The quadratic term is a small rank update to a diagonal matrix with positive entries. The optimality conditions of the quadratic program are reformulated as a semismooth system of equations using the Fischer-Burmeister function and a damped Newton method is applied to solve the resulting problem. The algorithm is shown to converge from any starting point with a Q-quadratic rate of convergence. At each iteration, the Sherman-Morrison-Woodbury update formula is used to solve the key linear system. Results for a large problem with 60 million observations are presented demonstrating the scalability of the proposed method on a personal computer. Significant computational savings are realized as the inactive variables are identified and exploited during the solution process. Further results on a small problem separated by a nonlinear surface are given showing the gains in performance that can be made from restarting the algorithm as the data evolves.Accepted: December 8, 2003This work partially supported by NSF grant number CCR-9972372; AFOSR grant number F49620-01-1-0040; the Mathematical, Information, and Computational Sciences Division subprogram of the Office of Advanced Scientific Computing, U.S. Department of Energy, under Contract W-31-109-Eng-38; and Microsoft Corporation.     

Register machines with counters

Register machines with counters (RC machines) are studied. It is shown that any computable function can be strictly computed on RC machines with a bounded number of counters and programs. The place in the Kleene–Mostowski hierarchy of certain algorithmic problems related to RC machines is determined.     

Optimisation of multi-position machines and transfer lines

A new optimisation problem for design of multi-position machines and automatic transfer lines is considered. To reduce the number of pieces of equipment, machining operations are grouped into blocks. The operations of the same block are performed simultaneously by one piece of equipment (multi-spindle head). At the studied design stage, constraints related to the design of blocks and workstations, as well as precedence constraints for operations are known. The problem consists in an optimal grouping of the operations into blocks minimizing the total number of blocks and workstations while reaching a given cycle time (productivity). A constrained shortest path algorithm is developed and tested.