Search results for "Automata Theory"

Exact results for accepting probabilities of quantum automata

2001

One of the properties of Kondacs-Watrous model of quantum finite automata (QFA) is that the probability of the correct answer for a QFA cannot be amplified arbitrarily. In this paper, we determine the maximum probabilities achieved by QFAs for several languages. In particular, we show that any language that is not recognized by an RFA (reversible finite automaton) can be recognized by a QFA with probability at most 0.7726...

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.

Local Normal Forms for First-Order Logic with Applications to Games and Automata

1999

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…

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…

Extending formal language hierarchies to higher dimensions

1999

Connecting Granular and Topological Relations through Description Logics

2021

Granularity deals with organizing in greater or lesser detail data, information, and knowledge that resides at a granular level. This organization is carried out according to certain criteria, which thereby provide a context view or dimension also called granular perspective. Topological relations express spatial associations among geospatial features (points, polylines, and polygons); they represent a horizontal spatial analysis. The two domains allow scientists to conceive different perspectives of the world. In this article, we aim to combine the two representations through Description Logics (DL) rules to relate granular (vertical representation) and geospatial topological (horizontal r…

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.