Automata recognition in effectively defined classes

MaRDI QIDQ2735907zbMATH OpenFDO

Authors I. I. Maksimenko

Publication date 23 September 2001

Published in Trudy Instituta Prikladnoĭ Matematiki i Mekhaniki (Search for Journal in Brave)

zbMATH Keywords

finite state machineidentificationinfinite classes of FSMs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Fault detection; testing in circuits and networks (94C12)

Review text

The paper deals with recognizing or identifying experiments on infinite classes of Mealy Finite State Machines (FSM). The class for which the experiments exist is called recognizable. The author shows that any recursively enumerable class \(B\) with Bair metric has a sequence of recursively enumerable recognizable subclasses \(B_1,\dots, B_n,\dots\) and \(B_{n-1}= \lim B_n\). The central point of the paper is investigation of the FSM's class defined by an nondeterministic FSM, and called finitely definable. It is shown that for any such class \(B\) the subclass \(\lim B\) is finitely definable too and opening subclass \(]\lim B[\) is recognizable.

Recommendations

• scientific article; zbMATH DE number 1537560
• Experiments with automata when the upper bound of the number of their states is unknown
• Finite automata
• scientific article; zbMATH DE number 1165603
• Regular Growth Automata: Properties of a Class of Finitely Induced Infinite Machines

Cited in

(4)

• Recognizability for automata
• On the class of L\(^*\)-language formulas that specify finite-memory finite-state machines
• scientific article; zbMATH DE number 3860401 (Why is no real title available?)
• scientific article; zbMATH DE number 1537560 (Why is no real title available?)

This page was built for publication: Automata recognition in effectively defined classes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2735907)