Learning counting functions with queries

We investigate the problem of learning disjunctions of counting functions, which are general cases of parity and modulo functions, with equivalence and membership queries. We prove that, for any prime number p, the class of disjunctions of integer-weighted counting functions with modulus p over the domain Z_qⁿ (or Zⁿ) for any given integer q 2 is polynomial time learnable using at most n + 1 equivalence queries, where the hypotheses issued by the learner are disjunctions of at most n counting functions with weights from Z_p. In general, a counting function may have a composite modulus. We prove that, for any given integer q 2, over the domain Z₂ⁿ, the class of read-once disjunctions of Boolean-weighted counting functions with modulus q is polynomial-time learnable with only one equivalence query and O(n^q) membership queries.     

Learning erasing pattern languages with queries

A pattern is a finite string of constant and variable symbols. The non-erasing language generated by a pattern is the set of all strings of constant symbols that can be obtained by substituting non-empty strings for variables. In order to build the erasing language generated by a pattern, it is also admissible to substitute the empty string.The present paper deals with the problem of learning erasing pattern languages within Angluin's model of learning with queries. Moreover, the learnability of erasing pattern languages with queries is studied when additional information is available. The results obtained are compared with previously known results in case non-erasing pattern languages have to be learned.First, when regular pattern languages have to be learned, it is shown that the learnability results for the non-erasing case remain valid, if the proper superclass of all erasing regular pattern languages is the object of learning. Second, in the general case, serious differences have been observed. For instance, it turns out that arbitrary erasing pattern languages cannot be learned in settings in which, in the non-erasing case, even polynomially many queries will suffice.     

Learning with errors in answers to membership queries

We study the learning models defined in [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255]: Learning with equivalence and limited membership queries and learning with equivalence and malicious membership queries.We show that if a class of concepts that is closed under projection is learnable in polynomial time using equivalence and (standard) membership queries then it is learnable in polynomial time in the above models. This closes the open problems in [D. Angluin, M. Krikis, R.H. Sloan, G. Turán, Malicious omissions and errors in answering to membership queries, Machine Learning 28 (2–3) (1997) 211–255].Our algorithm can also handle errors in the equivalence queries.     

Learning via finitely many queries

This work introduces a new query inference model that can access data and communicate with the teacher by asking finitely many Boolean queries in a language L. In this model the parameters of interest are the number of queries used and the expressive power of L. We study how the learning power varies with these parameters. Results suggest that this model may help studying query inference in a resource bounded environment.AMS subject classification 68Q05, 68Q32, 68T05, 03D10, 03D80     

Control and observation structures for analog circuits

No previously proposed analog built-in self-test method allows simultaneous control of all test points, the basic diagnosis capability required for analog circuits. This paper provides an approach that allows observation and control of DC voltage levels of all test points simultaneously, with a calibration process that ensures accuracy     

Hierarchical ATPG for analog circuits and systems

Automatic test-pattern generation (ATPG) algorithms for analog circuits have been under intense investigation for the last several years. As system design aggressively moves to system-on-a-chip (SoC) and core-based integration, hierarchical analog ATPG emerges as an even more difficult challenge. Attempts to develop an effective algorithm have had varying degrees of success. This article reviews some fundamental issues and recent work in hierarchical analog ATPG and presents an algorithm based on controllability and observability computation. This algorithm has been implemented in a prototype tool, and results based on several case studies show the application of the technique     

Monitoring properties of analog and mixed-signal circuits

In this paper, we present a comprehensive overview of the property-based monitoring framework for analog and mixed-signal systems. Our monitoring approach is centered around the Signal Temporal Logic (Stl) specification language, and is implemented in a stand-alone monitoring tool (Amt). We apply this property-based methodology to two industrial case studies and briefly present some recent extensions of Stl that were motivated by practical needs of analog designers.     

Learning two-tape automata from queries and counterexamples

We investigate the learning problem of two-tape deterministic finite automata (2-tape DFAs) from queries and counterexamples. Instead of accepting a subset of ∑*, a 2-tape DFA over an alphabet ∑ accepts a subset of ∑* × ∑*, and therefore, it can specify a binary relation on ∑*. In [3] Angluin showed that the class of deterministic finite automata (DFAs) is learnable in polynomial time from membership queries and equivalence queries, namely, from a minimally adequate teacher (MAT). In this article we show that the class of 2-tape DFAs is learnable in polynomial time from MAT. More specifically, we show an algorithm that, given any languageL accepted by an unknown 2-tape DFAM, learns from MAT a two-tape nonde-terministic finite automaton (2-tape NFA)M′ acceptingL in time polynomial inn andl, wheren is the size ofM andl is the maximum length of any counterexample provided during the learning process. This work was supported in part by Grants-in-Aid for Scientific Research No. 04229105 from the Ministry of Education, Science, and Culture, Japan.     

Functional fault models for analog circuits

For devices containing analog integrated circuits, the appropriate fault models are those that describe components at the functional level. Functional models proposed in the past have been too complicated for practical use. The models proposed here form the basis of simpler test selection techniques for analog ICs     

Fast fault simulation for nonlinear analog circuits

A new method of transient fault simulation uses dc bias grouping of faulty circuits and decreases the number of Newton-Raphson iterations needed to reach a solution. An experimental tool implementing this method achieves a speedup of 20% to 30% on a flat netlist.     

DC built-in self-test for linear analog circuits

DC testing of analog circuits is cheaper than AC testing and covers many fault classes, including some that AC tests cannot detect. This efficient, low-cost, built-in self-test (BIST) methodology uses the checksum encodings of matrix representations to uncover faults that affect a circuit's DC transfer function     

Multifrequency analysis of faults in analog circuits

Testability analysis of analog circuits in the presence of soft, large-deviation, and hard faults greatly facilitates production of testable systems. The authors analyze these faults by observing their symptoms at the circuit's output, an approach that uses the same test methodology to analyze all three fault types. Their algorithm indicates the set of adequate test frequencies and nodes that increase fault observability. They conclude by generating test vectors for observing and covering these faults     

Techniques for synthesis of analog integrated circuits

The CAD tools that have been developed for automated analog synthesis are reviewed. The synthesis process is described. The major techniques employed by the tools are examined. They are knowledge-based hierarchical design, analytic design, and placement/routing. Critical design issues are identified. It is shown how the technique discussed could be combined in a comprehensive framework supporting design from specification to physical layout     

Advanced methods for equivalence checking of analog circuits with strong nonlinearities

In this contribution two extensions for an analog equivalence checking method are proposed, enabling the checking of strongly nonlinear circuits with floating nodes such as digital library cells. Therefore, a structural recognition and mapping of eigenvalues, representing the dynamics, to circuit elements via circuit variables is presented. Additionally, the introduction of reachability analysis is significantly restricting the investigated state space to the relevant parts, avoiding false negatives. The newly introduced methods are compared to existing ones by application to industrial examples.     

Learning a subclass of k-quasi-Horn formulas with membership queries

Boolean formulas have been widely studied in the field of learning theory. We focus on the model of learning with queries, and study a restriction of the class of k-quasi-Horn formulas, that is, conjunctive normal form formulas where the number of unnegated literals per clause is at most k. This class is known to be as hard to learn as the general class CNF of conjunctive normal form formulas. By imposing some constraints, we define a fragment of this logic that can be learned using only membership queries. Also we prove that none of these constraints makes by itself the class learnable.     

Learning tree languages from positive examples and membership queries

We investigate regular tree languages’ exact learning from positive examples and membership queries. Input data are trees of the language to infer. The learner computes new trees from the inputs and asks the oracle whether or not they belong to the language. From the answers, the learner may ask further membership queries until he finds the correct grammar that generates the target language. This paradigm was introduced by Angluin in the seminal work [D. Angluin, A note on the number of queries needed to identify regular languages, Information and Control 51 (1981) 76–87] for the case of regular word languages. Neither negative examples, equivalence queries nor counter-examples are allowed in this paradigm.     

Current-mode subthreshold MOS circuits for analog VLSI neuralsystems

An overview of the current-mode approach for designing analog VLSI neural systems in subthreshold CMOS technology is presented. Emphasis is given to design techniques at the device level using the current-controlled current conveyor and the translinear principle. Circuits for associative memory and silicon retina systems are used as examples. The design methodology and how it relates to actual biological microcircuits are discussed.     

Digital-compatible BIST for analog circuits using transientresponse sampling

For complex mixed-signal designs, BIST is becoming a necessity. The BIST scheme presented here maximizes coverage of parametric and catastrophic failures and provides an all-digital BIST solution to analog circuits