All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 23 Next

Displaying 441 – 460 of 2186

Showing per page

Comparing numerical integration schemes for a car-following model with real-world data

Přikryl, Jan, Vaniš, Miroslav (2017)

Programs and Algorithms of Numerical Mathematics

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...

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2004)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Comparing the succinctness of monadic query languages over finite trees

Martin Grohe, Nicole Schweikardt (2010)

RAIRO - Theoretical Informatics and Applications

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...

Compatibility relations on codes and free monoids

Tomi Kärki (2008)

RAIRO - Theoretical Informatics and Applications

A compatibility relation on letters induces a reflexive and symmetric relation on words of equal length. We consider these word relations with respect to the theory of variable length codes and free monoids. We define an (R,S)-code and an (R,S)-free monoid for arbitrary word relations R and S. Modified Sardinas-Patterson algorithm is presented for testing whether finite sets of words are (R,S)-codes. Coding capabilities of relational codes are measured algorithmically by finding minimal and maximal relations....

Complexité et automates cellulaires linéaires

Valérie Berthé (2010)

RAIRO - Theoretical Informatics and Applications

The aim of this paper is to evaluate the growth order of the complexity function (in rectangles) for two-dimensional sequences generated by a linear cellular automaton with coefficients in ℤ / l ℤ , and polynomial initial condition. We prove that the complexity function is quadratic when l is a prime and that it increases with respect to the number of distinct prime factors of l.

Complexity classes for membrane systems

Antonio E. Porreca, Giancarlo Mauri, Claudio Zandron (2006)

RAIRO - Theoretical Informatics and Applications

We compare various computational complexity classes defined within the framework of membrane systems, a distributed parallel computing device which is inspired from the functioning of the cell, with usual computational complexity classes for Turing machines. In particular, we focus our attention on the comparison among complexity classes for membrane systems with active membranes (where new membranes can be created by division of existing membranes) and the classes PSPACE, EXP, and EXPSPACE.

Currently displaying 441 – 460 of 2186