Search results for "Computer Science::Formal Languages and Automata Theory"
showing 10 items of 228 documents
Word assembly through minimal forbidden words
2006
AbstractWe give a linear-time algorithm to reconstruct a finite word w over a finite alphabet A of constant size starting from a finite set of factors of w verifying a suitable hypothesis. We use combinatorics techniques based on the minimal forbidden words, which have been introduced in previous papers. This improves a previous algorithm which worked under the assumption of stronger hypothesis.
Mathematical logic and quantum finite state automata
2009
AbstractThis paper is a review of the connection between formulas of logic and quantum finite-state automata in respect to the language recognition and acceptance probability of quantum finite-state automata. As is well known, logic has had a great impact on classical computation, it is promising to study the relation between quantum finite-state automata and mathematical logic. After a brief introduction to the connection between classical computation and logic, the required background of the logic and quantum finite-state automata is provided and the results of the connection between quantum finite-state automata and logic are presented.
From Nerode's congruence to Suffix Automata with mismatches
2009
AbstractIn this paper we focus on the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with Sk. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of Sk to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the…
Motzkin subposets and Motzkin geodesics in Tamari lattices
2014
The Tamari lattice of order n can be defined by the set D n of Dyck words endowed with the partial order relation induced by the well-known rotation transformation. In this paper, we study this rotation on the restricted set of Motzkin words. An upper semimodular join semilattice is obtained and a shortest path metric can be defined. We compute the corresponding distance between two Motzkin words in this structure. This distance can also be interpreted as the length of a geodesic between these Motzkin words in a Tamari lattice. So, a new upper bound is obtained for the classical rotation distance between two Motzkin words in a Tamari lattice. For some specific pairs of Motzkin words, this b…
On Sets of Words of Rank Two
2019
Given a (finite or infinite) subset X of the free monoid A∗ over a finite alphabet A, the rank of X is the minimal cardinality of a set F such that X⊆ F∗. A submonoid M generated by k elements of A∗ is k-maximal if there does not exist another submonoid generated by at most k words containing M. We call a set X⊆ A∗ primitive if it is the basis of a |X|-maximal submonoid. This extends the notion of primitive word: indeed, w is a primitive set if and only if w is a primitive word. By definition, for any set X, there exists a primitive set Y such that X⊆ Y∗. The set Y is therefore called a primitive root of X. As a main result, we prove that if a set has rank 2, then it has a unique primitive …
"Table 54" of "Search for light top squark pair production in final states with leptons and b-jets with the ATLAS detector in sqrt(s) = 7 TeV proton-…
2013
observed CLs values for the 2LSR2 region in the M(chargino), M(neutralino) plane in the scenario where M(stop) = 180 GEV.
"Table 52" of "Search for light top squark pair production in final states with leptons and b-jets with the ATLAS detector in sqrt(s) = 7 TeV proton-…
2013
observed CLs values for the 2LSR1 region in the M(chargino), M(neutralino) plane in the scenario where M(stop) = 180 GEV.
"Table 62" of "Search for light top squark pair production in final states with leptons and b-jets with the ATLAS detector in sqrt(s) = 7 TeV proton-…
2013
observed CLs values for the 2LSR1 region in the M(stop), M(neutralino) plane in the scenario where M(chargino) = 106 GEV.
"Table 64" of "Search for light top squark pair production in final states with leptons and b-jets with the ATLAS detector in sqrt(s) = 7 TeV proton-…
2013
observed CLs values for the 2LSR2 region in the M(stop), M(neutralino) plane in the scenario where M(chargino) = 106 GEV.
"Table 50" of "Search for light top squark pair production in final states with leptons and b-jets with the ATLAS detector in sqrt(s) = 7 TeV proton-…
2013
observed CLs values for the 1LSR region in the M(chargino), M(neutralino) plane in the scenario where M(stop) = 180 GEV.