This paper describes a modification of the power set construction for the transformation of self-verifying nondeterministic finite automata to deterministic ones. Using a set counting argument, the upper bound for this transformation can be lowered from $2^n$ to $O\left(\frac{2^n}{\sqrt{n}}\right).$

We design algorithms of “optimal" data complexity for several natural problems about first-order queries on structures of bounded degree. For that purpose, we first introduce a framework to deal with logical or combinatorial problems R ⊂ I x O whose instances x ∈ I may admit of several solutions R(x) = {y ∈ O : (x,y) ∈ R}. One associates to such a problem several specific tasks: compute a random (for the uniform probability distribution) solution y ∈ R(x); enumerate without repetition each solution...

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet can be interpreted...

An ever present, common sense idea in language modelling research is that, for a word to be a valid phrase, it should comply with multiple constraints at once. A new language definition model is studied, based on agreement or consensus between similar strings. Considering a regular set of strings over a bipartite alphabet made by pairs of unmarked/marked symbols, a match relation is introduced, in order to specify when such strings agree. Then a regular set over the bipartite alphabet can be interpreted...

The paper treats the question whether there always exists a minimal nondeterministic finite automaton of n states whose equivalent minimal deterministic finite automaton has α states for any integers n and α with n ≤ α ≤ 2n. Partial answers to this question were given by Iwama, Kambayashi, and Takaki (2000) and by Iwama, Matsuura, and Paterson (2003). In the present paper, the question is completely solved by presenting appropriate automata for all values of n and α. However, in order to...

This paper is a survey of results on finite variable logics in finite model theory. It focusses on the common underlying techniques that unite many such results.

Inf-Datalog extends the usual least fixpoint semantics of Datalog with greatest fixpoint semantics: we defined inf-Datalog and characterized the expressive power of various fragments of inf-Datalog in [16]. In the present paper, we study the complexity of query evaluation on finite models for (various fragments of) inf-Datalog. We deduce a unified and elementary proof that global model-checking (i.e. computing all nodes satisfying a formula in a given structure) has 1. quadratic data complexity...

Inf-Datalog extends the usual least fixpoint semantics of Datalog with greatest fixpoint semantics: we defined inf-Datalog and characterized the expressive power of various fragments of inf-Datalog in [CITE]. In the present paper, we study the complexity of query evaluation on finite models for (various fragments of) inf-Datalog. We deduce a unified and elementary proof that global model-checking (i.e. computing all nodes satisfying a formula in a given structure) has 1. quadratic data complexity...

We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language $L$ is accepted by a Las Vegas automaton having $r$ states such that the probability for a definite answer to occur is at least $p$, then $r\ge n^p$, where $n$ is the number of the states of the minimal deterministic automaton accepting $L$. Earlier this result has been obtained in [2] by using a reduction...

We show that the size of a Las Vegas automaton and the size of a complete, minimal deterministic automaton accepting a regular language are polynomially related. More precisely, we show that if a regular language L is accepted by a Las Vegas automaton having r states such that the probability for a definite answer to occur is at least p, then r ≥ np, where n is the number of the states of the minimal deterministic automaton accepting L. Earlier this result has been obtained in [2] by using a reduction...

We investigate the complexity of several problems concerning Las Vegas finite automata. Our results are as follows. (1) The membership problem for Las Vegas finite automata is in NL. (2) The nonemptiness and inequivalence problems for Las Vegas finite automata are NL-complete. (3) Constructing for a given Las Vegas finite automaton a minimum state deterministic finite automaton is in NP. These results provide partial answers to some open problems posed by Hromkovič and Schnitger [Theoret....

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family $\left\{L_m\right\}$ of cyclic languages, where $L_m=\left\{a^{km}\right|k\in \mathbb{N}\}$. In particular, we show that, for any $m$, the number of states necessary and sufficient for accepting the unary language $L_m$ with isolated cut point on one-way probabilistic finite automata is $p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ being the factorization of $m$. To prove this result, we give a general state lower bound for accepting unary languages with isolated cut point on...

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family {Lm} of cyclic languages, where Lm = akm | k ∈ N. In particular, we show that, for any m, the number of states necessary and sufficient for accepting the unary language Lm with isolated cut point on one-way probabilistic finite automata is $p_1^{{\alpha }_1}+p_2^{{\alpha }_2}+\cdots +p_s^{{\alpha }_s}$, with $p_1^{{\alpha }_1}{p}_2^{{\alpha }_2}\cdots p_s^{{\alpha }_s}$ being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages...

We show that, for any stochastic event $p$ of period $n$, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event $ap+b$, for constants $a\>0$, $b\ge 0$, satisfying $a+b\le 1$. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period $n$ can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the strength of measure-once...

We show that, for any stochastic event p of period n, there exists a measure-once one-way quantum finite automaton (1qfa) with at most $2\sqrt{6n}+25$ states inducing the event ap+b, for constants a>0, b ≥ 0, satisfying a+b ≥ 1. This fact is proved by designing an algorithm which constructs the desired 1qfa in polynomial time. As a consequence, we get that any periodic language of period n can be accepted with isolated cut point by a 1qfa with no more than $2\sqrt{6n}+26$ states. Our results give added evidence of the...

Some of the most interesting and important results concerning quantum finite automata are those showing that they can recognize certain languages with (much) less resources than corresponding classical finite automata. This paper shows three results of such a type that are stronger in some sense than other ones because (a) they deal with models of quantum finite automata with very little quantumness (so-called semi-quantum one- and two-way finite automata); (b) differences, even comparing with probabilistic...

Bertoni et al.  introduced in Lect. Notes Comput. Sci.2710 (2003) 1–20 a new model of 1-way quantum finite automaton (1qfa) called 1qfa with control language (1qfc). This model, whose recognizing power is exactly the class of regular languages, generalizes main models of 1qfa's proposed in the literature. Here, we investigate some properties of 1qfc's. In particular, we provide algorithms for constructing 1qfc's accepting the inverse homomorphic images and quotients of languages accepted...

Consider partial maps ${\Sigma }^{*}$$\to$$ℝ$ with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure...

Consider partial maps ∑* → $ℝ$ with a rational domain. We show that two families of such series are actually the same: the unambiguous rational series on the one hand, and the max-plus and min-plus rational series on the other hand. The decidability of equality was known to hold in both families with different proofs, so the above unifies the picture. We give an effective procedure to build an unambiguous automaton from a max-plus automaton and a min-plus one that recognize the same series.

The cyclic shift of a language $L$, defined as $shift\left(L\right)$=$\left\{vu\right|uv\in L\}$, is an operation known to preserve both regularity and context-freeness. Its descriptional complexity has been addressed in Maslov’s pioneering paper on the state complexity of regular language operations [Soviet Math. Dokl. 11 (1970) 1373–1375], where a high lower bound for partial DFAs using a growing alphabet was given. We improve this result by using a fixed 4-letter alphabet, obtaining a lower bound (n-1)! $·$ 2${}^{(n-1)(n-2)}$, which shows that the state complexity...