The Infona portal uses cookies, i.e. strings of text saved by a browser on the user's device. The portal can access those files and use them to remember the user's data, such as their chosen settings (screen view, interface language, etc.), or their login data. By using the Infona portal the user accepts automatic saving and using this information for portal operation purposes. More information on the subject can be found in the Privacy Policy and Terms of Service. By closing this window the user confirms that they have read the information on cookie usage, and they accept the privacy policy and the way cookies are used by the portal. You can change the cookie settings in your browser.
Tiling systems that recognize two-dimensional languages are intrinsically non-deterministic models. We introduce the notion of deterministic tiling system that generalizes deterministic automata for strings. The corresponding family of languages matches all the requirements of a robust deterministic class. Furthermore we show that, differently from the one-dimensional case, there exist many classes...
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...
The regular language (a + b)*a (the words in alphabet {a, b} having a as the last letter) is at the moment a classical example of a language not recognizable by a one-way quantum finite automaton (QFA). Up to now, there have been introduced many different models of QFAs, with increasing capabilities, but none of them can cope with this language. We introduce a new, quite simple modification...
The “mean speedup” of a trace monoid can be interpreted as an index of the “intrinsic parallelism”. We study the problem of computing the mean speedup under two conditions: (1) uniform distribution on the words of given length and (2) uniform distribution on the traces of given height. In the first case, we give an approximability result showing a probabilistic fully polynomial time approximation...
We study the dynamics of cellular automata, and more specifically their transitivity and expansivity, when the set of configurations is endowed with a shift-invariant (pseudo-)distance. We first give an original proof of the non-transitivity of cellular automata when the set of configurations is endowed with the Besicovitch pseudo-distance. We then show that the Besicovitch pseudo-distance induces...
The notion of an unavoidable set of words appears frequently in the fields of mathematics and theoretical computer science, in particular with its connection to the study of combinatorics on words. The theory of unavoidable sets has seen extensive study over the past twenty years. In this paper we extend the definition of unavoidable sets of words to unavoidable sets of partial words. Partial words,...
We introduce and investigate nondeterministic finite automata with the additional ability to apply the hairpin inversion operation to the remaining part of the input. We consider three different modes of hairpin operations, namely left-most hairpin, general hairpin, and right-most hairpin. We show that these operations do not increase the computation power, when the number of operations is bounded...
The biological process of gene assembly has been modeled based on three types of string rewriting rules, called string pointer rules, defined on so-called legal strings. It has been shown that reduction graphs, graphs that are based on the notion of breakpoint graph in the theory of sorting by reversal, for legal strings provide valuable insights into the gene assembly process. We characterize which...
Visibly Pushdown Automata (VPA) are a special case of pushdown machines where the stack operations are driven by the input. In this paper, we consider VPA with two stacks, namely 2-VPA. These automata introduce a useful model to effectively describe concurrent pushdown systems using a simple communication mechanism between stacks. We show that 2-VPA are strictly more expressive than VPA. Indeed, 2-VPA...
The aim of this paper is to describe a quadratic algorithm to compute the equation -automaton of a regular -expression as defined by Lombardy and Sakarovitch. Our construction is based on an extension to regular -expressions of the notion of c-continuation that we introduced to compute the equation automaton of a regular expression as a quotient of its...
Fixed point equations x = F(x) over ω-continuous semirings are a natural mathematical foundation of interprocedural program analysis. Equations over the semiring of the real numbers can be solved numerically using Newton’s method. We generalize the method to any ω-continuous semiring and show that it converges faster to the least fixed point than the Kleene...
Size (the number of states) of finite probabilistic automata with an isolated cut-point can be exponentially smaller than the size of any equivalent finite deterministic automaton. The result is presented in two versions. The first version depends on Artin’s Conjecture (1927) in Number Theory. The second version does not depend on conjectures but the numerical estimates are worse. In both versions...
A segmented morphism $\sigma_n: \Delta^* \longrightarrow \{ {\ensuremath{\mathtt{a}}}, {\ensuremath{\mathtt{b}}} \}^*$ , n ∈ ℕ, maps each symbol in Δ onto a word which consists of n distinct subwords in . In the present paper, we examine the impact of n on the unambiguity of σn...
We solve the commutation equation AB = BA for binary factorial languages A and B. As we show, the situations when such languages commute can be naturally classified. The result is based on the existence and uniqueness of a canonical decomposition of a factorial language, proved by S. V. Avgustinovich and the author in 2005. It continues investigation of the semigroup of factorial languages.
Inapproximability results concerning minimization of nondeterministic finite automata relative to given deterministic finite automata were obtained only recently, modulo cryptographic assumptions [4]. Here we give upper and lower bounds on the approximability of this problem utilizing only the common assumption P ≠ NP, in the setup where the input is a finite language specified by a truth table. To...
We investigate the state complexity of union and intersection for finite languages. Note that the problem of obtaining the tight bounds for both operations was open. We compute the upper bounds based on the structural properties of minimal deterministic finite-state automata (DFAs) for finite languages. Then, we show that the upper bounds are tight if we have a variable sized alphabet that can depend...
We generalise existing forward and backward bisimulation minimisation algorithms for tree automata to weighted tree automata. The obtained algorithms work for all semirings and retain the time complexity of their unweighted variants for all additively cancellative semirings. On all other semirings the time complexity is slightly higher (linear instead of logarithmic in the number of states). We discuss...
Conjunctive grammars were introduced by A. Okhotin in [1] as a natural extension of context-free grammars with an additional operation of intersection in the body of any production of the grammar. Several theorems and algorithms for context-free grammars generalize to the conjunctive case. Still some questions remained open. A. Okhotin posed nine problems concerning those grammars. One of them was...
We show that for all integers n and α such that there exists a minimal nondeterministic finite automaton of n states with a four-letter input alphabet whose equivalent minimal deterministic finite automaton has exactly α states. It follows that in the case of a four-letter alphabet, there are no “magic numbers”, i.e., the holes in the hierarchy. This improves...
We consider the following decision problem: “Is a rational ω-language generated by a code ?” Since 1994, the codes admit a in terms of infinite words. We derive from this result the definition of a new class of languages, the reduced languages. A code is a reduced language but the converse does not hold. The idea is to “reduce” easy-to-obtain minimal ω-generators in order to obtain codes as ω-generators.
Set the date range to filter the displayed results. You can set a starting date, ending date or both. You can enter the dates manually or choose them from the calendar.