Limit probabilities for random sparse bit strings.
Limiting characterizations of low level space complexity classes
Linear Algorithms for Testing the Sign Stability of a Matrix and for Finding Z-Maximum Matchings in Acyclic Graphs.
Linear Space Data Structures for Two Types of Range Search.
Local transition functions of quantum Turing machines
Local Transition Functions of Quantum Turing Machines
Foundations of the notion of quantum Turing machines are investigated. According to Deutsch's formulation, the time evolution of a quantum Turing machine is to be determined by the local transition function. In this paper, the local transition functions are characterized for fully general quantum Turing machines, including multi-tape quantum Turing machines, extending the results due to Bernstein and Vazirani.
Locally testable semigroups.
Logarithmic frequency in morphic sequences
We study the logarithmic frequency of letters and words in morphic sequences and show that this frequency must always exist, answering a question of Allouche and Shallit.
Logic and functional programming by retractions : operational semantics
Logic and -recognizable sets of integers.
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...
Loops in automata and HDTOL relations
L'ordre de Dehornoy sur les tresses
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