Logic and -recognizable sets of integers.
Logical Aggregation Based on Interpolative Boolean Algebra.
Logics for stable and unstable mereological relations
In this paper we present logics about stable and unstable versions of several well-known relations from mereology: part-of, overlap and underlap. An intuitive semantics is given for the stable and unstable relations, describing them as dynamic counterparts of the base mereological relations. Stable relations are described as ones that always hold, while unstable relations hold sometimes. A set of first-order sentences is provided to serve as axioms for the stable and unstable relations, and representation...
Logique combinatoire et linguistique : grammaire catégorielle combinatoire applicative
La Grammaire Catégorielle Combinatoire Applicative étend la Grammaire Catégorielle Combinatoire de Steedman par une association canonique entre les règles et des combinateurs de Curry d'une part et l'utilisation de métarègles qui contrôlent les opérations de changement de type d'autre part. Ce modèle est inclus dans le modèle général de la Grammaire Applicative et Cognitive (Desclés) avec trois niveaux de représentation : (i) le phénotype (expressions concaténées) ; (ii) le génotype (expressions...
Look and Say Fibonacci
The (Look and Say) derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, (two , one , two ). We start the study of the behaviour of binary words generated by morphisms under the operator, focusing in particular on the Fibonacci word.
Look and Say Fibonacci
The LS (Look and Say) derivative of a word is obtained by writing the number of consecutive equal letters when the word is spelled from left to right. For example, LS( 1 1 2 3 3) = 2 1 1 2 2 3 (two 1, one 2, two 3). We start the study of the behaviour of binary words generated by morphisms under the LS operator, focusing in particular on the Fibonacci word.
Loops in automata and HDTOL relations
L'ordre de Dehornoy sur les tresses
Lossless image compression based on multiple-tables arithmetic coding.
Lossless joins of relational database views.
Low-degree graph partitioning via local search with applications to constraint satisfaction, max cut, and coloring.
Low-distortion embeddings of trees.
Lower and upper bounds of shortest paths in reachability graphs.
Lower bounds for Las Vegas automata by information theory
We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language is accepted by a Las Vegas automaton having states such that the probability for a definite answer to occur is at least , then , where is the number of the states of the minimal deterministic automaton accepting . Earlier this result has been obtained in [2] by using a reduction...
Lower Bounds for Las Vegas Automata by Information Theory
We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language L is accepted by a Las Vegas automaton having r states such that the probability for a definite answer to occur is at least p, then r ≥ np, where n is the number of the states of the minimal deterministic automaton accepting L. Earlier this result has been obtained in [2] by using a reduction...
Lower bounds for sparse matrix vector multiplication on hypercubic networks.
Lower Bounds on Moving a Ladder in Two and Three Dimensions.
Lower bounds on the complexity of real-time branching programs
Lower bounds to the graph partitioning problem through generalized linear programming and network flows
Lower space bounds for accepting shuffle languages