Page 1 Next

Displaying 1 – 20 of 21

Showing per page

An upper bound for transforming self-verifying automata into deterministic ones

Ira Assent, Sebastian Seibert (2007)

RAIRO - Theoretical Informatics and Applications

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 ( 2 n n ) .

Computing the jth solution of a first-order query

Guillaume Bagan, Arnaud Durand, Etienne Grandjean, Frédéric Olive (2008)

RAIRO - Theoretical Informatics and Applications

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...

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Consensual languages and matching finite-state computations

Stefano Crespi Reghizzi, Pierluigi San Pietro (2011)

RAIRO - Theoretical Informatics and Applications

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...

Deterministic blow-ups of minimal NFA's

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

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...

Finite models and finitely many variables

Anuj Dawar (1999)

Banach Center Publications

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, modal logic and complexities

Eugénie Foustoucos, Irène Guessarian (2009)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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, Modal Logic and Complexities

Eugénie Foustoucos, Irène Guessarian (2007)

RAIRO - Theoretical Informatics and Applications

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...

Lower bounds for Las Vegas automata by information theory

Mika Hirvensalo, Sebastian Seibert (2003)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 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...

Lower Bounds for Las Vegas Automata by Information Theory

Mika Hirvensalo, Sebastian Seibert (2010)

RAIRO - Theoretical Informatics and Applications

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...

Note on the complexity of Las Vegas automata problems

Galina Jirásková (2006)

RAIRO - Theoretical Informatics and Applications

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....

Note on the succinctness of deterministic, nondeterministic, probabilistic and quantum finite automata

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We investigate the succinctness of several kinds of unary automata by studying their state complexity in accepting the family { L m } of cyclic languages, where L m = { a k m | k } . 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 α 1 + p 2 α 2 + + p s α s , with p 1 α 1 p 2 α 2 p s α 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...

Note on the Succinctness of Deterministic, Nondeterministic, Probabilistic and Quantum Finite Automata

Carlo Mereghetti, Beatrice Palano, Giovanni Pighizzini (2010)

RAIRO - Theoretical Informatics and Applications

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 α 1 + p 2 α 2 + + p s α s , with p 1 α 1 p 2 α 2 p s α s being the factorization of m. To prove this result, we give a general state lower bound for accepting unary languages...

On the size of one-way quantum finite automata with periodic behaviors

Carlo Mereghetti, Beatrice Palano (2002)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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 6 n + 25 states inducing the event a p + 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 6 n + 26 states. Our results give added evidence of the strength of measure-once...

On the Size of One-way Quantum Finite Automata with Periodic Behaviors

Carlo Mereghetti, Beatrice Palano (2010)

RAIRO - Theoretical Informatics and Applications

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 6 n + 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 6 n + 26 states. Our results give added evidence of the...

On the state complexity of semi-quantum finite automata

Shenggen Zheng, Jozef Gruska, Daowen Qiu (2014)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Quantum finite automata with control language

Carlo Mereghetti, Beatrice Palano (2006)

RAIRO - Theoretical Informatics and Applications

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...

Series which are both max-plus and min-plus rational are unambiguous

Sylvain Lombardy, Jean Mairesse (2006)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

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...

Series which are both max-plus and min-plus rational are unambiguous

Sylvain Lombardy, Jean Mairesse (2010)

RAIRO - Theoretical Informatics and Applications

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.

State complexity of cyclic shift

Galina Jirásková, Alexander Okhotin (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

The cyclic shift of a language L , defined as s h i f t ( L ) = { v u | u v 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...

Currently displaying 1 – 20 of 21

Page 1 Next