Search

The main functionality of a compiler is to translate source code to an executable machine code correctly and efficiently. Compiler construction is an advanced research area due to size and complexity of the code generated from the source program. Design and construction of error-free and verified compiler will remain a challenge of the current century. Verification of a source program does not assure that the generated code is correct because the compiler may lead to an incorrect target program due to bugs and errors in itself. Hence verification of a compiler is more important than verifying the source program. Lexical analyzer is a main part of compiler used for scanning input stream of characters and grouping into tokens. In this paper, formal construction of syntax tree is described directly from the regular expression to verify the lexical analyzer. At first, augmented regular expression is described then an abstract syntax tree is defined based on the regular expression. Finally formal description of some important operators checking null-ability and computing first and last positions of the internal nodes of the tree are formalized. The specification is described using Z notation then validated using Z/Eves toolset. Formal model is analyzed using powerful techniques of reduction and rewriting available in the Z/Eves toolset. [ABSTRACT FROM AUTHOR]

A software product line describes explicitly the commonalities of and differences between different products in a family of (software) systems. A formalization of these commonalities and differences amounts to reduced development, analysis and maintenance costs in the practice of software engineering. An important feature common to next-generation real-time software systems is the need of application-level control over scheduling for optimized utilization of resources provided by for example many-core and cloud infrastructures. In this paper, we introduce a formal model of real-time software product lines which supports variability in scheduling policies and rigorous and efficient techniques for modular schedulability analysis. [ABSTRACT FROM PUBLISHER]

in this paper, we researched the status of the Visitor Locations Register (VLR) in the third generation communication system (3G). Basing on automata theory, we offer the statues modeling of the VLR, is called Visitor Locations Register Automata (VLRA), which formally describes the states, the behavior, and the variation of the VLR in the authentication protocol. Finally, we formally analyzed the VLRA in the authentication process. [ABSTRACT FROM PUBLISHER]

Bounded model checking (BMC) is a highly successful bug-finding method that examines paths of bounded length for violations of a given regular or omega-regular specification. A completeness threshold for a given model M and specification phi is a bound k such that, if no counterexample to phi of length k or less can be found in M, then M in fact satisfies phi. The quest for 'small' completeness thresholds in BMC goes back to the very inception of the technique, over a decade ago, and remains a topic of active research. For a fixed specification, completeness thresholds are typically expressed in terms of key attributes of the models under consideration, such as their diameter (length of the longest shortest path) and especially their recurrence diameter (length of the longest loop-free path). A recent research paper identified a large class of LTL specifications having completeness thresholds linear in the models' recurrence diameter. However, the authors left open the question of whether linearity is in general even decidable. In the present paper, we settle the problem in the affirmative, by showing that the linearity problem for both regular and omega-regular specifications (provided as automata and Buechi automata respectively is PSPACE-complete. Moreover, we establish the following dichotomies: for regular specifications, completeness thresholds are either linear or exponential, whereas for omega-regular specifications, completeness thresholds are either linear or at least quadratic. [ABSTRACT FROM PUBLISHER]

Interiors of neurons are occupied and organized by dynamic networks, called cytoskeletons, of protein polymers. These biomolecular networks (microtubules, or MT, actin, intermediate filaments, centrioles, etc.) are coupled to membrane events and regulate cellular activities, including synaptic plasticity. Models of purposeful behavior in the cytoskeleton include MT automata, in which cooperative coupling among MT subunit dipole/conformational states gives rise to computational patterns. The authors model MT automata interconnected by microtubular associated proteins. These cytoskeletal networks are capable of adaptive learning, association, and retrograde signaling. It is pointed out that MT automata may provide a subneural dimension in the brain's hierarchical organization and that artificial neural nets may more closely approximate the brain by including subneural processing [ABSTRACT FROM PUBLISHER]

The problem of which functions can be computed by a neural network is considered. The answers to this question determine the capabilities and limitations of a neural network as a general-purpose computer. A computation process is defined as the dynamic motion of input states to output states. Several types of deterministic neural network models are compared with the classical computational model of the Turing machine, and their computational capabilities are determined [ABSTRACT FROM PUBLISHER]

The authors have been developing a theory of learning automata that is applicable to studying goal-seeking systems of many types. The stepwise convergence of such systems to a goal state can be mapped into the training sequences of an appropriate learning automaton. This theory has been expanded to include infinite sets of states. The learning automaton may have an infinite characteristic semigroup of state transitions. The algebraic properties of the automaton are determined by this semigroup. A topology is introduced into the characteristic semigroup, S'. The latter can be considered as a function space of transformations of S. Behavior characteristics of the learning automaton be defined rigorously. In special cases, they can be related to the topological properties of S' and S, such as continuity of the transition function, separation properties and compactness [ABSTRACT FROM PUBLISHER]