9869945
The Logic of Automata—Part II
The transition part of a net controls the passage of the net from state to state and is therefore the heart of the net. In this subsection we introduce "the transition matr ix," a table which describes a net by showing the various ways in which it may pass from one delay state to another. We use a characterizing table with M input (state) words I, N internalstate words S, and M X N rows, each of the form <<I, S > , S ' > , to define N 2 direct-transition expressions I~j as follows. I ~ is a disjunction of all those I~ such tha t <<Ik, S~>, S i > is a row of the characterizing table; if there are no such Ik , then I~s is ¢ ("the false"). Tha t is, I~i is a disjunction of all those input words (if any) which can cause the net to pass from state S~ at time t to state Sj at t ime t + 1; it is allowed that i equals j . I t is clear that each I~i is a disjunctive normal form expression of the input function variables. Note tha t the direct-transition expression "~b" is distinct from the directtransition expressions "0", "00", "000", etc.; the former means that no direct transition between the two states is possible, while the latter mean that such a transition is brought about by making all the inputs zero. A direct transition from S~ to S~ in a net is a passage from state S~ at t to state S~ at t + 1. Such a transition is possible only in the case where I~i ~ ¢. We say that < I k , S~> (or Ik S~) at time t directly produces Si at time t -~ 1 only in the case where the net makes a direct transition from S~ to Sy under the influence of input Ik at t. A transition from S~ to Si in a net is a passage from state S~ at t to state S~ at t ~ w (w > 0). Such a transition is possible only where there exists a sequence of direct-transition expressions, none of which are ¢, of the form I~o, , I,~o~, . . . , I ~ j . We say that I~S~(t) , I~,~(t -q1), . . . , I~s(t -k w 1) produces S j at t "-k w if and only if there is a transition from S~(t) to Si(t -k w) under the direction of the hsted inputs; this is a transition of w steps (or, alternatively, a transition of length w). I t is convenient to arrange the information in an M N characterizing table in a direct-transition matrix of order N by arranging the N * direct-transi-
14517479
The Logic of Automata—Part I
We are concerned in this paper with the use of logical systems and techniques in the analysis of the structure and behavior of automata. In Section 2 we discuss automata in general. A new kind of automaton is introduced, the growing automaton, of which Turing machines and self-duplicating automata are special cases. Thereafter we limit the discussion to fixed, deterministic automata and define their basic features. We give methods of analyzing these automata in terms of their states. Four kinds of state tables--complete tables, admissibility trees, characterizing tables, and output tables--are used for this purpose. These methods provide a decision procedure for determining whether or not two automaton junctions behave the same. Finally, a class of well-formed automaton nets is defined, and it is shown how to pass from nets to state tables and vice versa. A coded normal form for nets is given. In Section 3* we show how the information contained in the state tables can be expressed in matrix form. The (i, j) element of a transition matrix gives those inputs which cause state S~ to produce state Sj. Various theorems are proved about these matrices and a corresponding normal form (the decoded normal form or matrix form) for nets is introduced. In Section 4* we first show how to decompose a net into one or more subnets which contain cycles but which are not themselves interconnected cyclically. We then discuss the relation of cycles in nets to the use of truth functions and quantifiers for describing nets. We conclude by relating nerve nets to other automaton nets.
10510054
Words in the History of a Turing Machine with a Fixed Input
The usual decision (halting or printing) problems for Turing machines (T.M.) are relative to an infinite class of them or an infinite class of inputs or1 a single T.M. We consider now a new type of problem (the consequence problem) con-neeted with a single input on a single T.M. It is known that in a definite sense everything which an erasing T.3{. can do can also be done by a nonerasing T.M., e.g., the halting problem is undeeidable in both bases. It turns out that for the consequence problem erasing does make an essential difference: decidable without erasing, but undecidable Mth erasing. From the undeeidability of the consequence problem for a T.M., it also follows that the same problem is undeeidable for certain simple monogenie normal systems. Consider a fixed finite alphabet A including a symbol b for the blank squares on a tape. For definiteness, we may assume that A = {b, ,, a}. Assume some familiar formulation of Turing machines. Definition. The word at any moment t in the history of a T.M. is the string consisting of the contents of the squares in the minimum block on the tape at t that includes all the marked squares and the square scanned at the initial moment (the origin). THEOREM 1. For arty fixed (finite) word at the initial moment, we can find a T.M. such that the set of words in its subsequent history is not ~cursive. Ullian shows [1] that there exists some nonrecursive but recursively enumerable set S such that there is a general recursive function f such that S = {f(0), f(f(O)), f(f(f(O))),-.. }. We can now give a T.M. which first erases the finitely many marks on the initial tape and returns to the origin, then it puts down the representation of 0 on tape, calculates the value of f(0), erasing everything else except the representation of f(0), calculates f2(0). In particular, we can do it in such a way that the symbol a is used, after the initial tape content is erased, only to mark f(0), f2(0), etc; it is erased before we evaluate f(f (0)) from f(0). Moreover, the string of a followed by the representation of f(0) always begins at the origin. Clearly the set of words in the history of this T.M. cannot be recursive because otherwise the set S would be recursive, whether a 'gd(0) ' belongs to the …
24771249
Parallel Approximate Matrix Factorization for Kernel Methods
The kernel methods play a pivotal role in machine learning algorithms. Unfortunately, working with the kernel methods must deal with an n times n kernel matrix, which is memory intensive. In this paper, we present a parallel, approximate matrix factorization algorithm, which loads only essential data to individual processors to enable parallel processing of data. Our method reduces space requirement for the kernel matrix from O(n2) to O(np/m), where n is the amount of data, p the reduced matrix dimension (p << n), and m the number of processors.
27202859
Affective interaction based on person-independent facial expression space
This paper proposes a person-independent facial expression space (PIFES) to analyze and synthesize facial expressions based on supervised locality preserving projections (SLPP), which aligns different subjects and different intensities of facial expressions on one generalized expression manifold. Interactive curves of different patterns are generated according to the input facial expression image sequence, and target responsive expression images are synthesized for different emotions. In order to synthesize arbitrary expressions for a new person with natural details, a novel approach based on local geometry preserving between the input face image and the target expression image is proposed. Experimental results clearly demonstrate the efficiency of the proposed algorithm.
7017728
Indexing Genomic Databases for Fast Homology Searching
Genomic sequence databases has been widely used by molecular biologists for homology searching. However, as amino acid and nucleotide databases are growing in size at an alarming rate, traditional brute force approach of comparing a query sequence against each of the database sequences is becoming prohibitively expensive. In this paper, we re-examine the problem of searching for homology in large protein databases. We proposed a novel filter-and-refine approach to speed up the search process. The scheme operates in two phases. In the filtering phase, a small set of candidate database sequences (as compared to all sequences in the database) is quickly identified. This is realized using a signature-based scheme. In the refinement phase, the query sequence is matched against the sequences in the candidate set using any local alignment strategies. Our preliminary experimental results show that the proposed method results in significant savings in computation without sacrificing on the accuracy of the answers as compared to FASTA.
1622406
Structure Analysis and SNR-Variance Evolution for Parallel Concatenated Coded IDMA Systems
This paper is concerned with parallel concatenated coded interleave-division multiple-access (IDMA) systems. We briefly present the transmitter/receiver structure of these systems and propose an efficient SNR-variance evolution scheme for bit-error-rate (BER) performance evaluation. The proposed evolution scheme is also useful for system performance optimization. Numerical results show that the BER performance curves obtained by simulation and evolution are quite close when the data length is long enough.