Active learning for extended finite state machines

We present a black-box active learning algorithm for inferring extended finite state machines (EFSM)s by dynamic black-box analysis. EFSMs can be used to model both data flow and control behavior of software and hardware components. Different dialects of EFSMs are widely used in tools for model-based software development, verification, and testing. Our algorithm infers a class of EFSMs called register automata. Register automata have a finite control structure, extended with variables (registers), assignments, and guards. Our algorithm is parameterized on a particular theory, i.e., a set of operations and tests on the data domain that can be used in guards.Key to our learning technique is a novel learning model based on so-called tree queries. The learning algorithm uses tree queries to infer symbolic data constraints on parameters, e.g., sequence numbers, time stamps, identifiers, or even simple arithmetic. We describe sufficient conditions for the properties that the symbolic constraints provided by a tree query in general must have to be usable in our learning model. We also show that, under these conditions, our framework induces a generalization of the classical Nerode equivalence and canonical automata construction to the symbolic setting. We have evaluated our algorithm in a black-box scenario, where tree queries are realized through (black-box) testing. Our case studies include connection establishment in TCP and a priority queue from the Java Class Library.     

Generating feature spaces for linear algorithms with regularized sparse kernel slow feature analysis

Without non-linear basis functions many problems can not be solved by linear algorithms. This article proposes a method to automatically construct such basis functions with slow feature analysis (SFA). Non-linear optimization of this unsupervised learning method generates an orthogonal basis on the unknown latent space for a given time series. In contrast to methods like PCA, SFA is thus well suited for techniques that make direct use of the latent space. Real-world time series can be complex, and current SFA algorithms are either not powerful enough or tend to over-fit. We make use of the kernel trick in combination with sparsification to develop a kernelized SFA algorithm which provides a powerful function class for large data sets. Sparsity is achieved by a novel matching pursuit approach that can be applied to other tasks as well. For small data sets, however, the kernel SFA approach leads to over-fitting and numerical instabilities. To enforce a stable solution, we introduce regularization to the SFA objective. We hypothesize that our algorithm generates a feature space that resembles a Fourier basis in the unknown space of latent variables underlying a given real-world time series. We evaluate this hypothesis at the example of a vowel classification task in comparison to sparse kernel PCA. Our results show excellent classification accuracy and demonstrate the superiority of kernel SFA over kernel PCA in encoding latent variables.     

Strongdeco: Expansion of analytical,strongly correlated quantum states into a many-body basis

We provide a Mathematica code for decomposing strongly correlated quantum states described by a first-quantized, analytical wave function into many-body Fock states. Within them, the single-particle occupations refer to the subset of Fock–Darwin functions with no nodes. Such states, commonly appearing in two-dimensional systems subjected to gauge fields, were first discussed in the context of quantum Hall physics and are nowadays very relevant in the field of ultracold quantum gases. As important examples, we explicitly apply our decomposition scheme to the prominent Laughlin and Pfaffian states. This allows for easily calculating the overlap between arbitrary states with these highly correlated test states, and thus provides a useful tool to classify correlated quantum systems. Furthermore, we can directly read off the angular momentum distribution of a state from its decomposition. Finally we make use of our code to calculate the normalization factors for Laughlin?s famous quasi-particle/quasi-hole excitations, from which we gain insight into the intriguing fractional behavior of these excitations.Program summaryProgram title: StrongdecoCatalogue identifier: AELA_v1_0Program summary URL: http://cpc.cs.qub.ac.uk/summaries/AELA_v1_0.htmlProgram obtainable from: CPC Program Library, Queen?s University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 5475No. of bytes in distributed program, including test data, etc.: 31 071Distribution format: tar.gzProgramming language: MathematicaComputer: Any computer on which Mathematica can be installedOperating system: Linux, Windows, MacClassification: 2.9Nature of problem: Analysis of strongly correlated quantum states.Solution method: The program makes use of the tools developed in Mathematica to deal with multivariate polynomials to decompose analytical strongly correlated states of bosons and fermions into a standard many-body basis. Operations with polynomials, determinants and permanents are the basic tools.Running time: The distributed notebook takes a couple of minutes to run.     

Linear Bidirectional On-Line Construction of Affix Trees

Affix trees are a generalization of suffix trees that are based on the inherent duality of suffix trees induced by the suffix links. An algorithm is presented that constructs affix trees on-line by expanding the underlying string in both directions and that is the first known algorithm to do this with linear time complexity.     

User preference mining techniques for personalized applications

Advanced personalized e-applications require comprehensive knowledge about their users’ likes and dislikes in order to provide individual product recommendations, personal customer advice, and custom-tailored product offers. In our approach we model such preferences as strict partial orders with “A is better than B” semantics, which has been proven to be very suitable in various e-applications. In this paper we present preference mining techniques for detecting strict partial order preferences in user log data. Real-life e-applications like online shops or financial services usually have large log data sets containing the transactions of their customers. Since the preference miner uses sophisticated SQL operations to execute all data intensive operations on database layer, our algorithms scale well even for such large log data sets. With preference mining personalized e-applications can gain valuable knowledge about their customers’ preferences, which can be applied for personalized product recommendations, individual customer service, or one-to-one marketing.     

Print your atomic force microscope

Progress in scanning probe microscopy profited from a flourishing multitude of new instrument designs, which lead to novel imaging modes and as a consequence to innovative microscopes. Often these designs were hampered by the restrictions, which conventional milling techniques impose. Modern rapid prototyping techniques, where layer by layer is added to the growing piece either by light driven polymerization or by three-dimensional printing techniques, overcome this constraint, allowing highly concave or even embedded and entangled structures. We have employed such a technique to manufacture an atomic force microscopy (AFM) head, and we compared its performance with a copy milled from aluminum. We tested both AFM heads for single molecule force spectroscopy applications and found little to no difference in the signal-to-noise ratio as well as in the thermal drift. The lower E modulus seems to be compensated by higher damping making this material well suited for low noise and low drift applications. Printing an AFM thus offers unparalleled freedom in the design and the rapid production of application-tailored custom instruments.     

Genetic Dissection of Light-Regulated Adventitious Root Induction in Arabidopsis thaliana Hypocotyls

Photomorphogenic responses of etiolated seedlings include the inhibition of hypocotyl elongation and opening of the apical hook. In addition, dark-grown seedlings respond to light by the formation of adventitious roots (AR) on the hypocotyl. How light signaling controls adventitious rooting is less well understood. Hereto, we analyzed adventitious rooting under different light conditions in wild type and photomorphogenesis mutants in Arabidopsis thaliana. Etiolation was not essential for AR formation but raised the competence to form AR under white and blue light. The blue light receptors CRY1 and PHOT1/PHOT2 are key elements contributing to the induction of AR formation in response to light. Furthermore, etiolation-controlled competence for AR formation depended on the COP9 signalosome, E3 ubiquitin ligase CONSTITUTIVELY PHOTOMORPHOGENIC (COP1), the COP1 interacting SUPPRESSOR OF PHYA-105 (SPA) kinase family members (SPA1,2 and 3) and Phytochrome-Interacting Factors (PIF). In contrast, ELONGATED HYPOCOTYL5 (HY5), suppressed AR formation. These findings provide a genetic framework that explains the high and low AR competence of Arabidopsis thaliana hypocotyls that were treated with dark, and light, respectively. We propose that light-induced auxin signal dissipation generates a transient auxin maximum that explains AR induction by a dark to light switch.