Search results for "Computer Science::Formal Languages and Automata Theory"
showing 10 items of 228 documents
New Results on Vector and Homing Vector Automata
2019
We present several new results and connections between various extensions of finite automata through the study of vector automata and homing vector automata. We show that homing vector automata outperform extended finite automata when both are defined over $ 2 \times 2 $ integer matrices. We study the string separation problem for vector automata and demonstrate that generalized finite automata with rational entries can separate any pair of strings using only two states. Investigating stateless homing vector automata, we prove that a language is recognized by stateless blind deterministic real-time version of finite automata with multiplication iff it is commutative and its Parikh image is …
Online Computation of Abelian Runs
2015
Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. We give an algorithm that finds all the abelian runs of period $\mathcal{P}$ in a word of length $n$ in time $O(n\times |\mathcal{P}|)$ and space $O(\sigma+|\mathcal{P}|)$.
A Fast Algorithm Finding the Shortest Reset Words
2012
In this paper we present a new fast algorithm finding minimal reset words for finite synchronizing automata. The problem is know to be computationally hard, and our algorithm is exponential. Yet, it is faster than the algorithms used so far and it works well in practice. The main idea is to use a bidirectional BFS and radix (Patricia) tries to store and compare resulted subsets. We give both theoretical and practical arguments showing that the branching factor is reduced efficiently. As a practical test we perform an experimental study of the length of the shortest reset word for random automata with $n$ states and 2 input letters. We follow Skvorsov and Tipikin, who have performed such a s…
Superiority of exact quantum automata for promise problems
2011
In this note, we present an infinite family of promise problems which can be solved exactly by just tuning transition amplitudes of a two-state quantum finite automata operating in realtime mode, whereas the size of the corresponding classical automata grow without bound.
Fast computation of abelian runs
2016
Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. Our main result is an online algorithm that, given a word $w$ of length $n$ over an alphabet of cardinality $\sigma$ and a Parikh vector $\mathcal{P}$, returns all the abelian runs of period $\mathcal{P}$ in $w$ in time $O(n)$ and space $O(\sigma+p)$, where $p$ is the norm of $\mathcal{P}$, i.e., the sum of its components. We also present an online algorithm that computes all the abelian runs with periods of norm $p$ in $w$ in time $O(np)$, for any given norm $p$. Finally, we give an $O(n^2)$-time offline randomi…
On generalized Lyndon words
2018
Abstract A generalized lexicographical order on infinite words is defined by choosing for each position a total order on the alphabet. This allows to define generalized Lyndon words. Every word in the free monoid can be factorized in a unique way as a nonincreasing factorization of generalized Lyndon words. We give new characterizations of the first and the last factor in this factorization as well as new characterization of generalized Lyndon words. We also give more specific results on two special cases: the classical one and the one arising from the alternating lexicographical order.
Abelian-Square-Rich Words
2017
An abelian square is the concatenation of two words that are anagrams of one another. A word of length $n$ can contain at most $\Theta(n^2)$ distinct factors, and there exist words of length $n$ containing $\Theta(n^2)$ distinct abelian-square factors, that is, distinct factors that are abelian squares. This motivates us to study infinite words such that the number of distinct abelian-square factors of length $n$ grows quadratically with $n$. More precisely, we say that an infinite word $w$ is {\it abelian-square-rich} if, for every $n$, every factor of $w$ of length $n$ contains, on average, a number of distinct abelian-square factors that is quadratic in $n$; and {\it uniformly abelian-sq…
On the least number of palindromes contained in an infinite word
2013
We investigate the least number of palindromic factors in an infinite word. We first consider general alphabets, and give answers to this problem for periodic and non-periodic words, closed or not under reversal of factors. We then investigate the same problem when the alphabet has size two.
On the Lie complexity of Sturmian words
2022
Bell and Shallit recently introduced the Lie complexity of an infinite word $s$ as the function counting for each length the number of conjugacy classes of words whose elements are all factors of $s$. They proved, using algebraic techniques, that the Lie complexity is bounded above by the first difference of the factor complexity plus one; hence, it is uniformly bounded for words with linear factor complexity, and, in particular, it is at most 2 for Sturmian words, which are precisely the words with factor complexity $n+1$ for every $n$. In this note, we provide an elementary combinatorial proof of the result of Bell and Shallit and give an exact formula for the Lie complexity of any Sturmi…
On the Structure of Bispecial Sturmian Words
2013
A balanced word is one in which any two factors of the same length contain the same number of each letter of the alphabet up to one. Finite binary balanced words are called Sturmian words. A Sturmian word is bispecial if it can be extended to the left and to the right with both letters remaining a Sturmian word. There is a deep relation between bispecial Sturmian words and Christoffel words, that are the digital approximations of Euclidean segments in the plane. In 1997, J. Berstel and A. de Luca proved that \emph{palindromic} bispecial Sturmian words are precisely the maximal internal factors of \emph{primitive} Christoffel words. We extend this result by showing that bispecial Sturmian wo…