Deterministic finite automata with recursive calls and DPDAs

We study deterministic finite automata (DFA) with recursive calls, that is, finite sequences of component DFAs that can call each other recursively. DFAs with recursive calls are akin to recursive state machines and unrestricted hierarchic state machines. We show that they are language equivalent to deterministic pushdown automata (DPDA).     

A layered algorithm for quantifier elimination from linear modular constraints

Linear equalities, disequalities and inequalities on fixed-width bit-vectors, collectively called linear modular constraints, form an important fragment of the theory of fixed-width bit-vectors. We present a practically efficient and bit-precise algorithm for quantifier elimination from conjunctions of linear modular constraints. Our algorithm uses a layered approach, whereby sound but incomplete and cheaper layers are invoked first, and expensive but complete layers are called only when required. We then extend this algorithm to work with arbitrary Boolean combinations of linear modular constraints as well. Experiments on an extensive set of benchmarks demonstrate that our techniques significantly outperform alternative quantifier elimination techniques based on bit-blasting and linear integer arithmetic.     

Efficient algorithms for approximate time separation of events

Finding bounds on time separation of events is a fundamental problem in the verification and analysis of asynchronous and concurrent systems. Unfortunately, even for systems without repeated events or choice, computing exact bounds on time separation of events is an intractable problem when both min and max type timing constraints are present. In this paper, we describe a method for approximating min and max type constraints, and develop a polynomial-time algorithm for computing approximate time separation bounds in choice-free systems without repeated events. Next, we develop a pseudo-polynomial time technique for analysing a class of asynchronous systems in which events repeat over time. Unlike earlier works, our algorithms can analyse systems with both min and max type timing constraints efficiently. Although the computed bounds are conservative in the worst-case, experimental results indicate that they are fairly accurate in practice. We present formal proofs of correctness of our algorithms, and demonstrate their efficiency and accuracy by applying them to a suite of benchmarks. A complete asynchronous chip has been modelled and analysed using the proposed technique, revealing potential timing problems (already known to designers) in the datapath design.     

Learning Sparse Feature Representations Using Probabilistic Quadtrees and Deep Belief Nets

Learning sparse feature representations is a useful instrument for solving an unsupervised learning problem. In this paper, we present three labeled handwritten digit datasets, collectively called n-MNIST by adding noise to the MNIST dataset, and three labeled datasets formed by adding noise to the offline Bangla numeral database. Then we propose a novel framework for the classification of handwritten digits that learns sparse representations using probabilistic quadtrees and Deep Belief Nets. On the MNIST, n-MNIST and noisy Bangla datasets, our framework shows promising results and outperforms traditional Deep Belief Networks.     

Static generation of UML sequence diagrams

UML sequence diagrams are visual representations of object interactions in a system and can provide valuable information for program comprehension, debugging, maintenance, and software archeology. Sequence diagrams generated from legacy code are independent of existing documentation that may have eroded. We present a framework for static generation of UML sequence diagrams from object-oriented source code. The framework provides a query refinement system to guide the user to interesting interactions in the source code. Our technique involves constructing a hypergraph representation of the source code, traversing the hypergraph with respect to a user-defined query, and generating the corresponding set of sequence diagrams. We implemented our framework as a tool, StaticGen (supporting software: StaticGen), analyzing a corpus of 30 Android applications. We provide experimental results demonstrating the efficacy of our technique (originally appeared in the Proceedings of Fundamental Approaches to Software Engineering—20th International Conference, FASE 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017).

     

A Nondeterministic Extension over Finitely Recursive Process Model

This paper extends the Finitely Recursive Process framework introduced by Inan and Varaiya for modelling Discrete Event Systems to encompass nondeterministic processes. Nondeterminism has been captured as a set of possible deterministic futures instead of using the standard failure model of Communicating Sequential Processes. In the beginning a general structure of finitely recursive process space is provided with some important modifications. Next, the nondeterministic process space has been introduced as a special case of the general algebraic process space. A collection of operators has been defined over this nondeterministic process space that enables its characterisation in a finitely recursive manner. Finally, the advantages and disadvantages of the proposed model vis-a-vis other nondeterministic models of discrete event systems are discussed.     

Efficient guided symbolic reachability using reachability expressions

Asynchronous systems consist of a set of transitions which are non-deterministically chosen and executed. We present a theory of guiding symbolic reachability in such systems by scheduling clusters of transitions. A theory of reachability expressions which specify the schedules is presented. This theory allows proving equivalence of different schedules which may have radically different performance in BDD-based search. We present experimental evidence to show that optimized reachability expressions give rise to significant performance advantages. The profiling is carried out in the NuSMV framework using examples from discrete timed automata and circuits with delays. A variant tool called NuSMVDP has been developed for interpreting reachability expressions to carry out the experiments.     

Automated operation sequencing in intelligent process planning: A case-based reasoning approach

This paper addresses the methodology development for achieving one of the important functions in automated process planning: automated determination of sequence of machining operations for prismatic parts containing various types of form features. A framework of using the case-based reasoning approach to support learning capability in operation sequencing is first proposed. The methodology to accomplish various issues in case-based operation sequencing is then discussed. In particular, the following issues are considered: 1. Representation of operation sequencing cases. 2. Indexing and retrieval of operation sequencing cases. 3. Adaptation of operation sequencing cases. Finally, the implementation issues are addressed and the learning functions of the intelligent operation sequencing system are demonstrated.     

Measurement of carrier mobility in silicon nanowires

We report the first direct capacitance measurements of silicon nanowires (SiNWs) and the consequent determination of field carrier mobilities in undoped-channel SiNW field-effect transistors (FETs) at room temperature. We employ a two-FET method for accurate extraction of the intrinsic channel resistance and intrinsic channel capacitance of the SiNWs. The devices used in this study were fabricated using a top-down method to create SiNW FETs with up to 1000 wires in parallel for increasing the raw capacitance while maintaining excellent control on device dimensions and series resistance. We found that, compared with the universal mobility curves for bulk silicon, the electron and hole mobilities in nanowires are comparable to those of the surface orientation that offers a lower mobility.