309 research outputs found
Charakterisazija sgivich rescienii sinchronnovo avtomatnovo uravnenija(Caratterizzazione delle soluzioni progressive di un'equazione sincrona su macchine a stati finiti)
No full textTesting in contest and synthesis of the unknown component: two faces ofthe same coin
No full textIn the paper, a test derivation method is briefly described for testing
in context when the system components are Finite State Machines (FSMs).
In order to alleviate the problem of infeasible machines, tests are derived
directly from the embedded component machine as proposed by Petrenko et al.
A component FSM can be tested up to the reduction relation
of the largest set of permissible behaviors, i.e., the largest solution
of the FSM equation computing all valid replacement of the component under test
with respect to the specification FSM.
As the largest solution usually is a nondeterministic FSM,
the methods presented by Petrenko et al.
can be used for deriving test sequences with guaranteed fault coverage.
However, tests generated by all of the above methods are given in the form
of sequences defined over the input/output alphabets of the embedded machine,
i.e., over internal alphabets. These tests are then translated into external
tests defined over the external observable input/output alphabets of the
overall system
Discussion on supervisory control by solving automata equations
No full textIn this paper we consider the supervisory control
problem through language equation solving. The
equation solving approach allows to find a largest
supervisor which can be used as a reservoir for
deriving an optimal controller. It is shown how
supervisory control problems with partial
controllability and partial observability can be solved
by equation solving methods
A new algorithm to solve synchronous FSM equations
No full textMany problems over discrete event systems can be reduced to solving
a synchronous FSM inequality A & X <= S or a synchronous FSM
equation A & X = S, where X is a free variable and &
is the synchronous composition operator. In this paper we address the problem
of solving a multi-component FSM equation,
We study the most general solution of a synchronous FSM equation defined
over several FSMs.
In particular, we show that a solvable equation has always a largest solution,
then we consider the largest alphabet of actions over which a solution exists,
from which it is possible to extract the largest solution over a restricted
set of alphabets
Deriving a module of a multi agent system via Finite State Machine equation solving
No full textIn multiagent systems, there is a problem of constructing an agent that can work in different contexts satisfying different specifications. One of ways is to solve a system of corresponding automata equations. Since in general, the complexity of solving such equations is exponential w.r.t. to the number of states of the context and specification, the question arises whether a system of equations can be reduced to a single equation. In this paper, we consider two special cases when a system of equations under the parallel composition over Finite State Machines can be reduced to a single equation. For each case, it is shown how a corresponding single equation can be derived
A new approach to the treatment of separatrix chaos
No full textWe review an approach to separatrix chaos that has allowed us to solve some significant problems by: (i) finding analytically the maximum width of the chaotic layer, a problem that lay unsolved for 40 years, and showing that the maximum may be much larger than had previously been assumed; (ii) describing the drastic facilitation of the onset of global chaos between neighboring separatrices, a phenomenon discovered eight years ago
Equisolvability of Series vs. Controller’s Topology in Synchronous Language Equations
No full textThe paper discusses conditions for equisolvability of language equations for series vs. controller topology
Component-Based Design by Solving Language Equations
No full textAn important step in the design of a complex system is its decompositioninto a number of interacting components, of which some are given (known)and some need to be synthesized (unknown).Then a basic task in the design flow is to synthesize an unknown componentthat when combined with the known part of the system (the context)satisfies a given specification.This problem arises in several applications ranging from sequentialsynthesis to the design of discrete controllers.There are different formulations of the problem, depending on the formalmodels to specify the system and its components,the composition operators, and the conformance relations of the composedsystem vs. the specification.Various behavioural models have been studied in the literature,e.g., finite state machines and automata, omega-automata,process algebras; various forms of synchronous andasynchronous (interleaving/parallel) composition have been considered;the conformance relations include language containment and equality,and notions of simulation.In this paper we give an overview of the problem (a.k.a., the unkown componentproblem, or submodule construction, etc.), and we focus on its reductionto solving equations over languages, as a key technologyfor supporting synthesis of compositional systems.We survey the state-of-art and highlight open problems requiring furtherinvestigation
Efficient Solution of Language Equations using Partitioned Representations
No full textA class of discrete event synthesis problems can be reduced to solving language equations involving a fixed component F and a specification S. Sequential synthesis deals with FSMs when the automata for F and S are prefix closed, and are naturally represented by multi-level networks with latches. For this special case, we present an efficient computation, using partitioned representations, of the most general prefix-closed solution of the above class of language equations. The transition and the output relations of the FSMs for F and S in their partitioned form are represented by the sets of output and next state functions of the corresponding networks. Experimentally, we show that using partitioned representations is much faster than using monolithic representations, as well as applicable to larger problem instances
- …
