Microcontroller software typically consists of a few hundred lines of code only, but, it is rather different from standard application code.. the software is highly hardware and platform specific, and bugs are often a...
详细信息
ISBN:
(纸本)9783540958901
Microcontroller software typically consists of a few hundred lines of code only, but, it is rather different from standard application code.. the software is highly hardware and platform specific, and bugs are often a consequence of neglecting subtle specifications of the microcontroller architecture. currently, there are hardly any tools for analyzing such software automatically. Tu this paper, we outline Specifies of microcontroller software that explain why those programs are different to standard C/C++ code. We develop a static program analysis for a specific microcontroller, in our case the ATmega16, to spot code deficiencies, and integrate it into our generic static analyzer Comma. Finally, we illustrate the results by a case study of an automotive application. the case study highlights that even without formal proof the proposed static techniques can be valuable in pinpointing software bugs that are otherwise hard to find.
A novel set-membersbip-based smoothing method for state estimation using the optimal bounding ellipsoid(OBE)algorithms is *** filters have been proven to be effective in state estimation problems with unknown but bo...
详细信息
ISBN:
(纸本)9781538629185
A novel set-membersbip-based smoothing method for state estimation using the optimal bounding ellipsoid(OBE)algorithms is *** filters have been proven to be effective in state estimation problems with unknown but bounded *** with filtering methods,smoothing methods provide a much more accurate and reliable state estimate because observations beyond the current estimation time are *** new method is a Rauch-Tung-Striebel(RTS)-type smoother which employs both forward and backward passes to estimate the system *** forward pass is performed using the OBE filter,while the backward pass maintains the fundamental spirit of OBE algorithm in the backward *** minimum-volume and minimum-trace bounding ellipsoids containing the feasible state set are derived from this *** results show the performance of the proposed smoother is superior to boththe traditional OBE filter and Kalman filter for state estimation.
this paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the othe...
详细信息
ISBN:
(数字)9783540775669
ISBN:
(纸本)9783540775652
this paper studies two problems on compressed strings described in terms of straight line programs (SLPs). One is to compute the length of the longest common substring of two given SLP-compressed strings, and the other is to compute all palindromes of a given SLP-compressed string. In order to solve these problems efficiently (in polynomial time w.r.t. the compressed size) decompression is never feasible, since the decompressed size can be exponentially large. We develop combinatorial algorithms that solve these problems in O(n(4) log n) time with O(n(3)) space, and in O(n(4)) time with O(n(2)) space, respectively, where n is the size of the input SLP-compressed strings.
Discovering interaction effects on a response of interest is a fundamental problem faced in biology, medicine, economics, and many other scientific disciplines. In theory, Bayesian methods for discovering pairwise int...
详细信息
this book constitutes the refereed proceedings of the 24th Seminar on currenttrends in theory and practice of Informatics, SOFSEM'97, held in Milovy, Czech Republic, in November 1997. SOFSEM is special in being a...
详细信息
ISBN:
(数字)9783540696452
ISBN:
(纸本)9783540637745
this book constitutes the refereed proceedings of the 24th Seminar on currenttrends in theory and practice of Informatics, SOFSEM'97, held in Milovy, Czech Republic, in November 1997. SOFSEM is special in being a mix of a winter school, an international conference, and an advanced workshop meeting the demand for ongoing education in the area of computerscience. the volume presents 22 invited contributions by leading experts together with 24 revised contributed papers selected from 63 submissions. the invited presentations are organized in topical sections on foundations, distributed and parallel computing, software engineering and methodology, and databases and information systems.
In [2], Backofen et al. propose the MRSO problem, that is to compute an mRNA sequence of maximal similarity to a given rnRNA and a given protein, that additionally satisfies some secondary structure constraints. the s...
详细信息
ISBN:
(纸本)3540207791
In [2], Backofen et al. propose the MRSO problem, that is to compute an mRNA sequence of maximal similarity to a given rnRNA and a given protein, that additionally satisfies some secondary structure constraints. the study of this problem is motivated by an application in the area of protein engineering. Modeled in a mathematical framework, we would like to compute a string s is an element of {a, b, (a) over bar, (b) over bar}(3n) which maximizes the sum of the values of n functions, which are blockwise applied to triples of s, and additionally satisfies some complementary constraints on the characters of s given in terms of position pairs. While the decision version of this problem is known to be NP-complete (see [2]), we prove here the APX-hardness of the general as well as of a restricted version of the problem. Moreover, we attack the problem by proposing a 4-approximation algorithm.
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressi...
详细信息
ISBN:
(纸本)9783031521126;9783031521133
An arithmetic progression is a sequence of integers in which the difference between any two consecutive elements is the same. We investigate the parameterized complexity of two problems related to arithmetic progressions, called COVER BY ARIthMETIC PROGRESSIONS (CAP) and EXACT COVER BY ARIthMETIC PROGRESSIONS (XCAP). In both problems, we are given a set X consisting of n integers along with an integer k, and our goal is to find k arithmetic progressions whose union is X. In XCAP we additionally require the arithmetic progressions to be disjoint. Both problems were shown to be NP-complete by Heath [IPL'90]. We present a 2(O(k2)) poly(n) time algorithm for CAP and a 2(O(k3)) poly(n) time algorithm for XCAP. We also give a fixed parameter tractable algorithm for CAP parameterized below some guaranteed solution size. We complement these findings by proving that CAP is Strongly NP-complete in the field Z(p), if p is a prime number part of the input.
this paper presents a complete account of positive and negative results on the finite axiomatizability of weak complete simulation semantics over the language BCCSP. We offer finite (un)conditional ground-complete axi...
详细信息
ISBN:
(纸本)9783642276590;9783642276606
this paper presents a complete account of positive and negative results on the finite axiomatizability of weak complete simulation semantics over the language BCCSP. We offer finite (un)conditional ground-complete axiomatizations for the weak complete simulation pre-congruence. In sharp contrast to this positive result, we prove that, in the presence of at least one observable action, the (in)equational theory of the weak complete simulation precongruence over BCCSP does not have a finite (in)equational basis. In fact, the set of (in)equations in at most one variable that hold in weak complete simulation semantics over BCCSP does not have an (in)equational basis of 'bounded depth', let alone a finite one.
We study the rendezvous problem in the asynchronous setting in the graph of infinite line following the model introduced in [13]. We formulate general lemmas about deterministic rendezvous algorithms in this setting w...
详细信息
ISBN:
(纸本)9783540958901
We study the rendezvous problem in the asynchronous setting in the graph of infinite line following the model introduced in [13]. We formulate general lemmas about deterministic rendezvous algorithms in this setting which characterize the algorithms in which the agents have the shortest routes. We also improve rendezvous algorithms in the infinite line which formulated in [13]. Two agents have distinct labels L-min, L-max and vertical bar L-min vertical bar <= vertical bar L-max vertical bar. When the initial distance D between the agents is known, our algorithm has cost D vertical bar L-min vertical bar(2) which is ail improvement in the constant. If the initial distance is unknown we give an algorithm of cost O(D log(2) D + D log D vertical bar L-max vertical bar + D vertical bar L-min vertical bar(2) + vertical bar L-max vertical bar vertical bar L-min vertical bar log vertical bar L-min vertical bar) which is an asymptotic improvement.
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the...
详细信息
ISBN:
(纸本)9783319042978;9783319042985
the well-known Disjoint Paths problem takes as input a graph G and a set of k pairs of terminals in G, and the task is to decide whether there exists a collection of k pairwise vertex-disjoint paths in G such that the vertices in each terminal pair are connected to each other by one of the paths. this problem is known to NP-complete, even when restricted to planar graphs or interval graphs. Moreover, although the problem is fixed-parameter tractable when parameterized by k due to a celebrated result by Robertson and Seymour, it is known not to admit a polynomial kernel unless NP subset of coNP/poly. We prove that Disjoint Paths remains NP-complete on split graphs, and show that the problem admits a kernel with O(k(2)) vertices when restricted to this graph class. We furthermore prove that, on split graphs, the edge-disjoint variant of the problem is also NP-complete and admits a kernel with O(k(3)) vertices. To the best of our knowledge, our kernelization results are the first non-trivial kernelization results for these problems on graph classes.
暂无评论