Optimal path queries are queries to obtain an optimal path specified by a given criterion of optimality. There have been many studies to give efficient algorithms for classes of optimal path problem. In this paper, we...
详细信息
Optimal path queries are queries to obtain an optimal path specified by a given criterion of optimality. There have been many studies to give efficient algorithms for classes of optimal path problem. In this paper, we propose a generic framework for optimal path queries. We offer a domain-specific language to describe optimal path queries, together with an algorithm to find an optimal path specified in our language. One of the most distinct features of our framework is the use of recursive functions to specify queries. recursive functions reinforce expressiveness of our language so that we can describe many problems including known ones;thus, we need not learn existing results. Moreover, we can derive an efficient querying algorithm from the description of a query written in recursive functions. Our algorithm is a generalization of existing algorithms, and answers a query in O(n log n) time on a graph of O(n) size. We also explain our implementation of an optimal path querying system, and report some experimental results.
Optimal path queries are queries to obtain an optimal path specified by a given criterion of optimality. There have been many studies to give efficient algorithms for classes of optimal path problem. In this paper, we...
详细信息
ISBN:
(纸本)9781595939197
Optimal path queries are queries to obtain an optimal path specified by a given criterion of optimality. There have been many studies to give efficient algorithms for classes of optimal path problem. In this paper, we propose a generic framework for optimal path queries. We offer a domain-specific language to describe optimal path queries, together with an algorithm to find an optimal path specified in our language. One of the most distinct features of our framework is the use of recursive functions to specify queries. recursive functions reinforce expressiveness of our language so that we can describe many problems including known ones;thus, we need not learn existing results. Moreover, we can derive an efficient querying algorithm from the description of a query written in recursive functions. Our algorithm is a generalization of existing algorithms, and answers a query in O(n log n) time on a graph of O(n) size. We also explain our implementation of an optimal path querying system, and report some experimental results.
Although formal specification techniques are very useful in software development, the acquisition of formal specifications is a difficult task. This paper presents the formal specification language LFC, which is desig...
详细信息
Although formal specification techniques are very useful in software development, the acquisition of formal specifications is a difficult task. This paper presents the formal specification language LFC, which is designed to facilitate the acquisition and validation of formal specifications. LFC uses context-free languages for syntactic aspect and relies on a new kind of recursive functions, i.e. recursive functions on context-free languages, for semantic aspect of specifications. Construction and validation of LFC specifications are machine-aided. The basic ideas behind LFC, the main aspects of LFC, and the use of LFC and illustrative examples are described. (c) 2005 Elsevier B.V. All rights reserved.
Many structures used in computer science and software can be represented by context-free languages. This paper discusses computable functions on such languages, which give a useful model for studies of computability a...
详细信息
ISBN:
(纸本)3540340211
Many structures used in computer science and software can be represented by context-free languages. This paper discusses computable functions on such languages, which give a useful model for studies of computability and algorithms involving complex data structures. This paper further tackles some practical issues for using the functions. Some practical schemes of the functions are presented. A subclass of functions is provided, which can be implemented efficiently.
Background: Structure matching plays an important part in understanding the functional role of biological structures. Bioinformatics assists in this effort by reformulating this process into a problem of finding a max...
详细信息
Background: Structure matching plays an important part in understanding the functional role of biological structures. Bioinformatics assists in this effort by reformulating this process into a problem of finding a maximum common subgraph between graphical representations of these structures. Among the many different variants of the maximum common subgraph problem, the maximum common induced subgraph of two graphs is of special interest. Results: Based on current research in the area of parameterized computation, we derive a new lower bound for the exact algorithms of the maximum common induced subgraph of two graphs which is the best currently known. Then we investigate the upper bound and design techniques for approaching this problem, specifically, reducing it to one of finding a maximum clique in the product graph of the two given graphs. Considering the upper bound result, the derived lower bound result is asymptotically tight. Conclusion: Parameterized computation is a viable approach with great potential for investigating many applications within bioinformatics, such as the maximum common subgraph problem studied in this paper. With an improved hardness result and the proposed approaches in this paper, future research can be focused on further exploration of efficient approaches for different variants of this problem within the constraints imposed by real applications.
The classical propositional logic is known to be sound and complete with respect to the set semantics that interprets connectives as set operations. The paper extends propositional language by a new binary modality th...
详细信息
In this paper, we initially recall a tool of calculus, the backwards differences, and we show how it allows to obtain some useful relations. We make a first application and we find a recursive relation for (sic). Afte...
详细信息
In this paper, we initially recall a tool of calculus, the backwards differences, and we show how it allows to obtain some useful relations. We make a first application and we find a recursive relation for (sic). Afterwards we make a second application and we prove the relation (sic) with (sic). It allows toto optimize the previous calculus and to obtain the latter relation in a easier way by means of the distribution of the number of goals scored in a table-football game.
Background: Systems Biology Markup Language (SBML) is gaining broad usage as a standard for representing dynamical systems as data structures. The open source statistical programming environment R is widely used by bi...
详细信息
Background: Systems Biology Markup Language (SBML) is gaining broad usage as a standard for representing dynamical systems as data structures. The open source statistical programming environment R is widely used by biostatisticians involved in microarray analyses. An interface between SBML and R does not exist, though one might be useful to R users interested in SBML, and SBML users interested in R. Results: A model structure that parallels SBML to a limited degree is defined in R. An interface between this structure and SBML is provided through two function definitions: write. SBML() which maps this R model structure to SBML level 2, and read. SBML() which maps a limited range of SBML level 2 files back to R. A published model of purine metabolism is provided in this SBML-like format and used to test the interface. The model reproduces published time course responses before and after its mapping through SBML. Conclusions: List infrastructure preexisting in R makes it well-suited for manipulating SBML models. Further developments of this SBML-R interface seem to be warranted.
The shortest definition of a number by a first order formula with one free variable, where the notion of a formula defining a number extends a notion used by Boolos in a proof of the Incompleteness Theorem, is shown t...
详细信息
The shortest definition of a number by a first order formula with one free variable, where the notion of a formula defining a number extends a notion used by Boolos in a proof of the Incompleteness Theorem, is shown to be non computable. This is followed by an examination of the complexity of sets associated with this function.
An expression for reliability of K-out-of-N:G system is proposed. An algorithm for computing reliability of K-out-of-N system is given. It is an easy to implement, fast and memory efficient algorithm and helps to impr...
详细信息
An expression for reliability of K-out-of-N:G system is proposed. An algorithm for computing reliability of K-out-of-N system is given. It is an easy to implement, fast and memory efficient algorithm and helps to improve the computational efficiency considerably. (C) 2002 Elsevier Science Ltd. All rights reserved.
暂无评论