Search results for "deterministic"

Exact affine counter automata

2017

We introduce an affine generalization of counter automata, and analyze their ability as well as affine finite automata. Our contributions are as follows. We show that there is a language that can be recognized by exact realtime affine counter automata but by neither 1-way deterministic pushdown automata nor realtime deterministic k-counter automata. We also show that a certain promise problem, which is conjectured not to be solved by two-way quantum finite automata in polynomial time, can be solved by Las Vegas affine finite automata. Lastly, we show that how a counter helps for affine finite automata by showing that the language MANYTWINS, which is conjectured not to be recognized by affin…

Complexity of probabilistic versus deterministic automata

2005

Amount of nonconstructivity in deterministic finite automata

2010

AbstractWhen D. Hilbert used nonconstructive methods in his famous paper on invariants (1888), P. Gordan tried to prevent the publication of this paper considering these methods as non-mathematical. L.E.J. Brouwer in the early twentieth century initiated intuitionist movement in mathematics. His slogan was “nonconstructive arguments have no value for mathematics”. However, P. Erdös got many exciting results in discrete mathematics by nonconstructive methods. It is widely believed that these results either cannot be proved by constructive methods or the proofs would have been prohibitively complicated. The author (Freivalds, 2008) [10] showed that nonconstructive methods in coding theory are…

Local Normal Forms for First-Order Logic with Applications to Games and Automata

1999

Building on work of Gaifman [Gai82] it is shown that every first-order formula is logically equivalent to a formula of the form ∃ x_1,...,x_l, \forall y, φ where φ is r-local around y, i.e. quantification in φ is restricted to elements of the universe of distance at most r from y. \par From this and related normal forms, variants of the Ehrenfeucht game for first-order and existential monadic second-order logic are developed that restrict the possible strategies for the spoiler, one of the two players. This makes proofs of the existence of a winning strategy for the duplicator, the other player, easier and can thus simplify inexpressibility proofs. \par As another application, automata mode…

From Nerode's congruence to Suffix Automata with mismatches

2009

AbstractIn this paper we focus on the minimal deterministic finite automaton Sk that recognizes the set of suffixes of a word w up to k errors. As first result we give a characterization of the Nerode’s right-invariant congruence that is associated with Sk. This result generalizes the classical characterization described in [A. Blumer, J. Blumer, D. Haussler, A. Ehrenfeucht, M. Chen, J. Seiferas, The smallest automaton recognizing the subwords of a text, Theoretical Computer Science, 40, 1985, 31–55]. As second result we present an algorithm that makes use of Sk to accept in an efficient way the language of all suffixes of w up to k errors in every window of size r of a text, where r is the…

Extending formal language hierarchies to higher dimensions

1999

SIMULATING DEMOGRAPHY AND HUMAN DEVELOPMENT DYNAMICS

2014

[EN] A deterministic/stochastic model in which the demographic and the well-being subsystems of a country are involved and related is presented as a way to approach human development. The demographic subsystem is a side-by-side, single-gender, age-structured population dynamic model. The well-being subsystem states the dynamics of the United Nations Hybrid Human Development Index. The model has been validated in the case of Spain and Belgium. Some simulations have been performed with the model for the case of Spain in the 2009-2020 period to determine strategies and scenarios that could increase the life expectancy at birth per gender. Copyright © 2014 Taylor & Francis Group, LLC.

The Occurrence and Dietary Exposure Assessment of Mycotoxins, Biogenic Amines, and Heavy Metals in Mould-Ripened Blue Cheeses

2020

The occurrence and dietary exposure assessment of 16 mycotoxins, 6 biogenic amines (BAs), and 13 metallic elements in blue-veined cheeses (n = 46) is reported. Co-occurrence of mycophenolic acid (&le

Optimal estimation of losses at the ultimate quantum limit with non-Gaussian states

2009

We address the estimation of the loss parameter of a bosonic channel probed by arbitrary signals. Unlike the optimal Gaussian probes, which can attain the ultimate bound on precision asymptotically either for very small or very large losses, we prove that Fock states at any fixed photon number saturate the bound unconditionally for any value of the loss. In the relevant regime of low-energy probes, we demonstrate that superpositions of the first low-lying Fock states yield an absolute improvement over any Gaussian probe. Such few-photon states can be recast quite generally as truncations of de-Gaussified photon-subtracted states.

On Extremal Cases of the Hopcroft's Algorithm

2010

In this paper we consider the problem of minimization of deterministic finite automata (DFA) with reference to Hopcroft’s algorithm. Hopcroft’s algorithm has several degrees of freedom, so there can exist different executions that can lead to different sequences of refinements of the set of the states up to the final partition. We find an infinite family of binary automata for which such a process is unique, whatever strategy is chosen. Some recent papers (cf. Berstel and Carton (2004) [3], Castiglione et al. (2008) [6] and Berstel et al. (2009) [1]) have been devoted to find families of automata for which Hopcroft’s algorithm has its worst execution time. They are unary automata associated…