Search results for " deterministic"
showing 10 items of 31 documents
Nondeterministic Moore automata and Brzozowski's minimization algorithm
2012
AbstractMoore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. We propose an algorithm that is a variant of Brzozowski’s minimization algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice. Moreover, we explore more general classes of NMA and analyze the applicability of the algorithm. For some of such classes the algorith…
Automata with Extremal Minimality Conditions
2010
It is well known that the minimality of a deterministic finite automaton (DFA) depends on the set of final states. In this paper we study the minimality of a strongly connected DFA by varying the set of final states. We consider, in particular, some extremal cases. A strongly connected DFA is called uniformly minimal if it is minimal, for any choice of the set of final states. It is called never-minimal if it is not minimal, for any choice of the set of final states. We show that there exists an infinite family of uniformly minimal automata and that there exists an infinite family of never-minimal automata. Some properties of these automata are investigated and, in particular, we consider t…
A graph theoretic approach to automata minimality
2012
AbstractThe paper presents a graph-theoretic approach to test the minimality of a deterministic automaton. In particular, we focus on problems concerning the dependence of the minimality of an automaton on the choice of the set F of final states or on the cardinality of the set F. We introduce different minimality conditions of an automaton and show that such conditions can be characterized in graph-theoretic terms.
Nondeterministic Moore Automata and Brzozowski’s Algorithm
2011
Moore automata represent a model that has many applications. In this paper we define a notion of coherent nondeterministic Moore automaton (NMA) and show that such a model has the same computational power of the classical deterministic Moore automaton. We consider also the problem of constructing the minimal deterministic Moore automaton equivalent to a given NMA. In this paper we propose an algorithm that is a variant of Brzozowski's algorithm in the sense that it is essentially structured as reverse operation and subset construction performed twice.
Reinforcement Learning Your Way: Agent Characterization through Policy Regularization
2022
The increased complexity of state-of-the-art reinforcement learning (RL) algorithms has resulted in an opacity that inhibits explainability and understanding. This has led to the development of several post hoc explainability methods that aim to extract information from learned policies, thus aiding explainability. These methods rely on empirical observations of the policy, and thus aim to generalize a characterization of agents’ behaviour. In this study, we have instead developed a method to imbue agents’ policies with a characteristic behaviour through regularization of their objective functions. Our method guides the agents’ behaviour during learning, which results in a…
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.
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.
Representation of Autonomous Automata
2001
An autonomous automaton is a finite automaton with output in which the input alphabet has cardinality one when special reduced. We define the transition from automata to semigroups via a representation successful if given two incomparable automata (neither simulate the other), the semigroups representing the automata are distinct. We show that representation by the transition semigroup is not successful. We then consider a representation of automata by semigroups of partial transformations. We show that in general transition from automata to semigroups by this representation is not successful either. In fact, the only successful transition presented is the transiton to this semigroup of par…
On the Size Complexity of Deterministic Frequency Automata
2013
Austinat, Diekert, Hertrampf, and Petersen [2] proved that every language L that is (m,n)-recognizable by a deterministic frequency automaton such that m > n/2 can be recognized by a deterministic finite automaton as well. First, the size of deterministic frequency automata and of deterministic finite automata recognizing the same language is compared. Then approximations of a language are considered, where a language L′ is called an approximation of a language L if L′ differs from L in only a finite number of strings. We prove that if a deterministic frequency automaton has k states and (m,n)-recognizes a language L, where m > n/2, then there is a language L′ approximating L such that L′ c…