The search session has expired. Please query the service again.
The search session has expired. Please query the service again.
A key element of microscopic traffic flow simulation is the so-called car-following model, describing the way in which a typical driver interacts with other vehicles on the road. This model is typically continuous and traffic micro-simulator updates its vehicle positions by a numerical integration scheme. While increasing the order of the scheme should lead to more accurate results, most micro-simulators employ the simplest Euler rule. In our contribution, inspired by [1], we will provide some additional...
We study the succinctness of monadic second-order logic and a variety of monadic fixed point logics on trees. All these languages are known to have the same expressive power on trees, but some can express the same queries much more succinctly than others. For example, we show that, under some complexity theoretic assumption, monadic second-order logic is non-elementarily more succinct than monadic least fixed point logic, which in turn is non-elementarily more succinct than monadic datalog.
Succinctness...
We study the succinctness of monadic second-order logic and a variety
of monadic fixed point logics on trees. All these languages are known to have
the same expressive power on trees, but some can express the same
queries much more succinctly than others. For example, we show that, under
some complexity theoretic assumption, monadic second-order logic is
non-elementarily more succinct than monadic least fixed point logic,
which in turn is non-elementarily more succinct than monadic datalog.
Succinctness...
For a given partial solution, the partial inverse problem is to modify the coefficients such that there is a full solution containing the partial solution, while the full solution becomes optimal under new coefficients, and the total modification is minimum. In this paper, we show that the partial inverse assignment problem and the partial inverse minimum cut problem are NP-hard if there are bound constraints on the changes of coefficients.
For a given partial solution,
the partial inverse problem is to modify the coefficients
such that there is a full solution containing the partial solution,
while the full solution becomes optimal under new coefficients, and
the total modification is minimum.
In this paper, we show that the partial inverse
assignment problem and the partial inverse minimum cut problem are NP-hard if
there are bound constraints on the changes of coefficients.
Resolving an open problem of Ravikumar and Quan, we show that equivalence of prefix grammars is complete in PSPACE. We also show that membership for these grammars is complete in P (it was known that this problem is in P) and characterize the complexity of equivalence and inclusion for monotonic grammars. For grammars with several premises we show that membership is complete in EXPTIME and hard for PSPACE for monotonic grammars.
Resolving an open problem of Ravikumar and Quan, we show that
equivalence of prefix grammars is complete in PSPACE. We also show
that membership for these grammars is complete in P
(it was known that this problem is in P) and characterize the
complexity of equivalence and inclusion for monotonic grammars.
For grammars with several premises we show that membership
is complete in EXPTIME and hard for PSPACE for monotonic
grammars.
Currently displaying 1 –
8 of
8