SYNTHESIS OF A NONDETERMINISTIC AUTOMATON FROM ITS LOGICAL SPECIFICATION .2.

Authors
Citation
An. Chebotarev, SYNTHESIS OF A NONDETERMINISTIC AUTOMATON FROM ITS LOGICAL SPECIFICATION .2., Cybernetics and systems analysis, 31(6), 1995, pp. 793-801
Citations number
2
Categorie Soggetti
Controlo Theory & Cybernetics","Computer Science Cybernetics
ISSN journal
10600396
Volume
31
Issue
6
Year of publication
1995
Pages
793 - 801
Database
ISI
SICI code
1060-0396(1995)31:6<793:SOANAF>2.0.ZU;2-G
Abstract
In Part I [1] we described an algorithm to construct the reduced form of the automaton A(F(t)) specified by the formula vr F(t) where the ra nk of the formula F(t) does not exceed 1. Part II considers two algori thms that construct an automaton with a number of states close to the reduced form of the automaton A(F(t)) for the case of arbitrary formul as F(t) allowed by the specification language. Both algorithms rely on the same idea of decomposing the formula F(t) as the algorithm of [1] , but examination of formulas of a more general kind required a substa ntial refinement of the decomposition idea, leading to two different a lgorithms. The last section of the article demonstrates how the algori thm of [1] can be applied in the general case after transforming the g iven formula to a formula of rank 1. The concepts and notation that ar e given without definition correspond to their usage in [1].