Search results for " Languages"
showing 10 items of 1859 documents
On Horn spectra
1991
Abstract A Horn spectrum is a spectrum of a Horn sentence. We show that to solve Asser's problem, and consequently the EXPTIME = ? NEXPTIME question it suffices to consider the class of Horn spectra. We also pose the problem whether or not the generator of every Horn spectrum is a spectrum. We prove that from a negative solution of the generator problem, a negative answer for the EXPTIME = ? NEXPTIME question follows. Some other relations between the generator problem and Asser's problem are given. Finally, the relativized version of the generator problem is formulated and it is shown that it has an affirmative solution for some oracles, and a negative solution for some others.
The dual equivalence of equations and coequations for automata
2015
The transition structure α : X ? X A of a deterministic automaton with state set X and with inputs from an alphabet A can be viewed both as an algebra and as a coalgebra. We use this algebra-coalgebra duality as a common perspective for the study of equations and coequations. For every automaton ( X , α ) , we define two new automata: free ( X , α ) and cofree ( X , α ) representing, respectively, the greatest set of equations and the smallest set of coequations satisfied by ( X , α ) . Both constructions are shown to be functorial. Our main result is that the restrictions of free and cofree to, respectively, preformations of languages and to quotients A * / C of A * with respect to a congr…
The Spread of English
2013
English descends from a set of Germanic dialects spoken 4,000 years or so ago in a small area of the far south of Scandinavia. The arrival of Germanic speakers on the island of Britain a millennium and a half ago led to the growth of the language we now call English. This language remained confined to this island for most of its history and, indeed, was not spoken in all parts of the island until extremely recently. During the last five centuries native-speaker English also spread to the Western Hemisphere and then to the Southern Hemisphere, leading to the development of new varieties of the language in the colonised areas, but also to the massive loss of indigenous languages in the Americ…
Languages with mismatches
2007
AbstractIn this paper we study some combinatorial properties of a class of languages that represent sets of words occurring in a text S up to some errors. More precisely, we consider sets of words that occur in a text S with k mismatches in any window of size r. The study of this class of languages mainly focuses both on a parameter, called repetition index, and on the set of the minimal forbidden words of the language of factors of S with errors. The repetition index of a string S is defined as the smallest integer such that all strings of this length occur at most in a unique position of the text S up to errors. We prove that there is a strong relation between the repetition index of S an…
Balance Properties and Distribution of Squares in Circular Words
2008
We study balance properties of circular words over alphabets of size greater than two. We give some new characterizations of balanced words connected to the Kawasaki-Ising model and to the notion of derivative of a word. Moreover we consider two different generalizations of the notion of balance, and we find some relations between them. Some of our results can be generalised to non periodic infinite words as well.
Hamming, Permutations and Automata
2007
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than superexponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We prove that there is an infinite sequence of distinct int…
Super-Exponential Size Advantage of Quantum Finite Automata with Mixed States
2008
Quantum finite automata with mixed states are proved to be super-exponentially more concise rather than quantum finite automata with pure states. It was proved earlier by A.Ambainis and R.Freivalds that quantum finite automata with pure states can have exponentially smaller number of states than deterministic finite automata recognizing the same language. There was a never published "folk theorem" proving that quantum finite automata with mixed states are no more than super-exponentially more concise than deterministic finite automata. It was not known whether the super-exponential advantage of quantum automata is really achievable. We use a novel proof technique based on Kolmogorov complex…
Coding Partitions: Regularity, Maximality and Global Ambiguity
2007
The canonical coding partition of a set of words is the finest partition such that the words contained in at least two factorizations of a same sequence belong to a same class. In the case the set is not uniquely decipherable, it partitions the set into one unambiguous class and other parts that localize the ambiguities in the factorizations of finite sequences. We firstly prove that the canonical coding partition of a regular set contains a finite number of regular classes. We give an algorithm for computing this partition. We then investigate maximality conditions in a coding partition and we prove, in the regular case, the equivalence between two different notions of maximality. As an ap…
Symbolic Dynamics of Geodesic Flows on Trees
2019
In this chapter, we give a coding of the discrete-time geodesic ow on the nonwandering sets of quotients of locally finite simplicial trees X without terminal vertices by nonelementary discrete subgroups of Aut(X) by a subshift of finite type on a countable alphabet.
On bijections vs. unary functions
1996
A set of finite structures is in Binary NP if it can be characterized by existential second order formulas in which second order quantification is over relations of arity 2. In [DLS95] subclasses of Binary NP were considered, in which the second order quantifiers range only over certain classes of relations. It was shown that many of these subclasses coincide and that all of them can be ordered in a three-level linear hierarchy, the levels of which are represented by bijections, successor relations and unary functions respectively.