Page 1 Next
Keijo Ruohonen (2008)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of -rational sequences.
Keijo Ruohonen (2007)
RAIRO - Theoretical Informatics and Applications
A new algorithm is presented for the D0L sequence equivalence problem which, when the alphabets are fixed, works in time polynomial in the rest of the input data. The algorithm uses a polynomial encoding of words and certain well-known properties of -rational sequences.
Henning Fernau, Klaus Reinhardt, Ludwig Staiger (2007)
RAIRO - Theoretical Informatics and Applications
We explore the borderline between decidability and undecidability of the following question: “Let C be a class of codes. Given a machine of type X, is it decidable whether the language lies in C or not?” for codes in general, ω-codes, codes of finite and bounded deciphering delay, prefix, suffix and bi(pre)fix codes, and for finite automata equipped with different versions of push-down stores and counters.
Jean-Jacques Pansiot (1986)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Fabien Durand (2013)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
In this paper we prove the decidability of the HD0L ultimate periodicity problem.
Petr Jančar (1989)
Commentationes Mathematicae Universitatis Carolinae
Bruno Courcelle, Jean H. Gallier (1987)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Manfred Schmidt-Schauss, David Sabel, Marko Schütz (2007)
RAIRO - Theoretical Informatics and Applications
Various static analyses of functional programming languages that permit infinite data structures make use of set constants like Top, Inf, and Bot, denoting all terms, all lists not eventually ending in Nil, and all non-terminating programs, respectively. We use a set language that permits union, constructors and recursive definition of set constants with a greatest fixpoint semantics in the set of all, also infinite, computable trees, where all term constructors are non-strict. This...
Mouhebeddine Berrima, Narjes Ben Rajeb, Véronique Cortier (2011)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
In the last decade, formal methods have proved their interest when analyzing security protocols. Security protocols require in particular to reason about the attacker knowledge. Two standard notions are often considered in formal approaches: deducibility and indistinguishability relations. The first notion states whether an attacker can learn the value of a secret, while the latter states whether an attacker can notice some difference between protocol runs with different values of the secret. Several...
Mouhebeddine Berrima, Narjes Ben Rajeb, Véronique Cortier (2011)
RAIRO - Theoretical Informatics and Applications
In the last decade, formal methods have proved their interest when analyzing security protocols. Security protocols require in particular to reason about the attacker knowledge. Two standard notions are often considered in formal approaches: deducibility and indistinguishability relations. The first notion states whether an attacker can learn the value of a secret, while the latter states whether an attacker can notice some difference between protocol runs with different values of the secret. Several...
Pálvölgyi, Dömötör (2009)
Acta Universitatis Sapientiae. Mathematica
Christian Choffrut (2008)
RAIRO - Theoretical Informatics and Applications
We consider logics on and which are weaker than Presburger arithmetic and we settle the following decision problem: given a k-ary relation on and which are first order definable in Presburger arithmetic, are they definable in these weaker logics? These logics, intuitively, are obtained by considering modulo and threshold counting predicates for differences of two variables.
Jacques Justin, Giuseppe Pirillo (1997)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Olivier Carton, Christian Choffrut, Serge Grigorieff (2006)
RAIRO - Theoretical Informatics and Applications
We consider the four families of recognizable, synchronous, deterministic rational and rational subsets of a direct product of free monoids. They form a strict hierarchy and we investigate the following decision problem: given a relation in one of the families, does it belong to a smaller family? We settle the problem entirely when all monoids have a unique generator and fill some gaps in the general case. In particular, adapting a proof of Stearns, we show that it is recursively decidable whether...
Peter Vojtáš (2000)
Kybernetika
In this paper we argue that for fuzzy unification we need a procedural and declarative semantics (as opposed to the two valued case, where declarative semantics is hidden in the requirement that unified terms are syntactically – letter by letter – identical). We present an extension of the syntactic model of unification to allow near matches, defined using a similarity relation. We work in Hájek’s fuzzy logic in narrow sense. We base our semantics on a formal model of fuzzy logic programming extended...
Andreas Weber (1996)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
S. Kasangian, R. Rosebrugh (1986)
Cahiers de Topologie et Géométrie Différentielle Catégoriques
Jiří Kopřiva (1970)
Kybernetika
Seyed-Kazem Lellahi, Nicolas Spyratos (1993)
Diagrammes
Włodzimierz Moczurad (2007)
RAIRO - Theoretical Informatics and Applications
We consider the defect theorem in the context of labelled polyominoes, i.e., two-dimensional figures. The classical version of this property states that if a set of n words is not a code then the words can be expressed as a product of at most n - 1 words, the smaller set being a code. We survey several two-dimensional extensions exhibiting the boundaries where the theorem fails. In particular, we establish the defect property in the case of three dominoes (n × 1 or 1 × n rectangles).
Page 1 Next