We introduce a notion of higher-order parity automaton which extends to infinitary simply-typed λ-terms the traditional notion of parity tree automaton on infinitary ranked trees. Our main result is that the acceptan...
详细信息
ISBN:
(纸本)9781509030187
We introduce a notion of higher-order parity automaton which extends to infinitary simply-typed λ-terms the traditional notion of parity tree automaton on infinitary ranked trees. Our main result is that the acceptance of an infinitary λ-term by a higher-order parity automaton A is decidable, whenever the infinitary λ-term is generated by a finite and simply-typed λY-term. The decidability theorem is established by combining ideas coming from linear logic, from denotational semantics and from infinitary rewriting theory.
Representing the sharing and exchanging data withmachine-readable format allows cooperative taskautomation. In this paper we propose an XML Schemaand semantic based relational data translation approach,which aims at p...
详细信息
ISBN:
(纸本)0780379411
Representing the sharing and exchanging data withmachine-readable format allows cooperative taskautomation. In this paper we propose an XML Schemaand semantic based relational data translation approach,which aims at providing a coherent and meaningful viewof the relational data and enabling distributed users tocooperate on large data volumes online. We define adirected-graph data model as the common data model,present a key-based relational schema reversereconstruction arithmetic to capture the full structuresand semantic constraints in relational schema, andpropose a constraints-preserving mapping algorithm totranslate relational data into the global XMLrepresentations.
Predictive models are fundamental to engineering reliable software systems. However, designing conservative, computable approximations for the behavior of programs (static analyses) remains a difficult and error-prone...
详细信息
Predictive models are fundamental to engineering reliable software systems. However, designing conservative, computable approximations for the behavior of programs (static analyses) remains a difficult and error-prone process for modern high-level programminglanguages. What analysis designers need is a principled method for navigating the gap between semantics and analytic models: analysis designers need a method that tames the interaction of complex languages features such as higher-order functions, recursion, exceptions, continuations, objects and dynamic allocation. We contribute a systematic approach to program analysis that yields novel and transparently sound static analyses. Our approach relies on existing derivational techniques to transform high-level languagesemantics into low-level deterministic state-transition systems (with potentially infinite state spaces). We then perform a series of simple machine refactorings to obtain a sound, computable approximation, which takes the form of a non-deterministic state-transition systems with finite state spaces. The approach scales up uniformly to enable program analysis of realistic language features, including higher-order functions, tail calls, conditionals, side effects, exceptions, first-class continuations, and even garbage collection.
Formal methods advocate the crucial role played by the algebra of programs in specification and implementation of programs. Study leads to the conclusion that both the top-down approach (with denotational model as its...
详细信息
ISBN:
(纸本)9781509050826
Formal methods advocate the crucial role played by the algebra of programs in specification and implementation of programs. Study leads to the conclusion that both the top-down approach (with denotational model as its origin) and the bottom-up approach (a journey started from operational model) can meet in the middle with a program algebra. This paper proposes a new approach on linking theories of programming. Given a program algebra, we construct a test operator taking a test case and the testing program as its arguments. The operator yields a collection of observations of the test outcomes. The denotational model of a program can be derived as a binary relation which relates the test cases with their outcomes. An operational model is considered as consistent if its step relation is consistent with the algebraic semantics.
We describe a means of presenting hierarchically organized formal definitions of programminglanguages using the denotational approach of D. Scott and C. Strachey. As an example of our approach, we give the semantics ...
详细信息
The semantics are defined for a number of meta-instructions which perform operations essential to the writing of programs in multiprogrammed computer systems. These meta-instructions relate to parallel processing, pro...
详细信息
The designer of a computing system should adopt explicit criteria for accepting or rejecting proposed system features. Three possible criteria af this kind are input recordability, input specifiability, and asynchrono...
详细信息
The designer of a computing system should adopt explicit criteria for accepting or rejecting proposed system features. Three possible criteria af this kind are input recordability, input specifiability, and asynchronous reproducibility of output. These criteria imply that a user can, if he desires, either know or control all the influences affecting the content and extent of his computer's output. To define the scope of the criteria, the notion of an abstract machine of a programminglanguage and the notion of a virtual computer are explained. Examples of applications of the criteria concern the reading of a time-of-day clock, the synchronization of parallel processes, protection in multipragrammed systems, and the assignment of capability indexes. [ABSTRACT FROM AUTHOR]
暂无评论