UDC 519.713.1
1 V.M. Glushkov Institute of Cybernetics, National Academy of Sciences of Ukraine, Kyiv, Ukraine
 ancheb@gmail.com
|
|
DETECTING FICTITIOUS STATES IN A ∑-AUTOMATON SYNTHESIZED
FROM THE SPECIFICATION IN THE LANGUAGE LP
Abstract. Synthesis of a deterministic ∑-automaton specified in the language LP consists in the execution of two consecutive procedures.
The first one constructs the automaton that has a subautomaton, which is identical to the specified automaton, and the other deletes the states
that do not belong to this subautomaton. Such states are called fictitious. The method for detecting fictitious states is considered.
The obtained results allow reducing detection of fictitious states to finding so-called basic cycles and eventually to checking
the membership of a periodic –ω -word in some –ω -regular set
.
Keywords: ∑-automaton, fictitious state, initial strongly connected subautomaton, normal form, –ω -regular set, basic cycle
.
FULL TEXT
REFERENCES
- Chebotarev A.N. Synthesis of ∑-automata specified in the first order logical languages LP and LF. Kibernetika i sistemnyj analiz. 2018. Vol. 54, N 4. P. 16–31.
- Chebotarev A.N. Synthesis of the procedural representation of the automaton specified in the logical language L. II. Kibernetika i sistemnyj analiz. 1997. N 6. P. 115–127.
- Perrin D., Pin J.-E. Infinite words. Automata, semigroups, logic and games. Pure and applied mathematics series. Amsterdam: Elsevier, 2004. Vol. 141. 550 p.
- Bresolin D., Montanari A., Puppis G. A theory of ultimately periodic languages and automata with an application to time granularity. Acta Informatica. 2009. Vol. 46, N 5. P. 331–360.
- Chebotarev A.N. Some subsets of monadic first order logic (MFO) used for specification and synthesis of ∑-automata. Kibernetika i sistemnyj analiz. 2017. Vol. 53, N 4. P. 22–36.
- Calbrix H., Nivat M., Podelsky A. Ultimately periodic words of rational ∑-languages. Lecture Notes in Computer Science. 1994. Vol. 802. P. 554–566.
- Chebotarev A.N. Problems of synthesis of ∑-automata specified in languages LP and LF of first order logic. Kibernetika i sistemnyj analiz. 2017. Vol. 53, N 5. P. 22–33.
