Detecting Fictitious States in a Σ-Automaton Synthesized from Its Specification in the Language LP

Synthesizing a deterministic Σ-automaton specified in the language LP consists in sequentially executing two procedures. The first constructs an automaton with a subautomaton identical to the automaton specified, and the other eliminates the states that do not belong to this subautomaton. Such state...

Full description

Saved in:
Bibliographic Details
Published in:Cybernetics and systems analysis 2019-09, Vol.55 (5), p.742-751
Main Author: Chebotarev, A. N.
Format: Article
Language:English
Subjects:
Artificial Intelligence
Automata theory
Control
Cybernetics
Mathematics
Mathematics and Statistics
Processor Architectures
Software Engineering/Programming and Operating Systems
Synthesis
Systems Theory
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Synthesizing a deterministic Σ-automaton specified in the language LP consists in sequentially executing two procedures. The first constructs an automaton with a subautomaton identical to the automaton specified, and the other eliminates the states that do not belong to this subautomaton. Such states are called fictitious. A method for detecting fictitious states is considered. The obtained results allow to reduce the detection of fictitious states to finding the so-called basic cycles and eventually to checking the membership of a periodic left-infinite word in some – ω -regular set.
ISSN:1060-0396
1573-8337
DOI:10.1007/s10559-019-00184-x