A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse Strategy

A resurgent interest for grammatical inference aka automaton learning has emerged in several intriguing areas of computer sciences such as machine learning, software engineering, robotics and internet of things. An automaton learning algorithm commonly uses queries to learn the regular grammar of a...

Full description

Bibliographic Details
Main Authors: Farah Haneef, Muddassar Azam Sindhu
Format: Article
Language:English
Published: IEEE 2023-01-01
Series:IEEE Access
Subjects:
Online Access:https://ieeexplore.ieee.org/document/10036086/
_version_ 1811163528418033664
author Farah Haneef
Muddassar Azam Sindhu
author_facet Farah Haneef
Muddassar Azam Sindhu
author_sort Farah Haneef
collection DOAJ
description A resurgent interest for grammatical inference aka automaton learning has emerged in several intriguing areas of computer sciences such as machine learning, software engineering, robotics and internet of things. An automaton learning algorithm commonly uses queries to learn the regular grammar of a Deterministic Finite Automaton (DFA). These queries are posed to a Minimum Adequate Teacher (MAT) by the learner (Learning Algorithm). The membership and equivalence queries which the learning algorithm may pose, are often capable of having their answers provided by the MAT. The three main categories of learning algorithms are incremental, sequential, and complete learning algorithms. In the presence of a MAT, the time complexity of existing DFA learning algorithms is polynomial. Therefore, in some applications these algorithms may fail to learn the system. In this study, we have reduced the time complexity of DFA learning from polynomial to logarithmic form. For this, we propose an efficient complete DFA learning algorithm; the Block based DFA Learning through Inverse Query (BDLIQ) using block based delta inverse strategy, which is based on the idea of inverse queries that John Hopcroft introduced for state minimization of a DFA. The BDLIQ algorithm possess <inline-formula> <tex-math notation="LaTeX">$O(\vert \Sigma \vert N.log N)$ </tex-math></inline-formula> complexity when a MAT is available. The MAT is also made capable of responding to inverse queries. We provide theoretical and empirical analysis of the proposed algorithm. Results show that our suggested approach for complete learning; BDLIQ algorithm, is more efficient than the ID algorithm in terms of time complexity.
first_indexed 2024-04-10T15:07:45Z
format Article
id doaj.art-aca12302051a44888f57e7efc8985c99
institution Directory Open Access Journal
issn 2169-3536
language English
last_indexed 2024-04-10T15:07:45Z
publishDate 2023-01-01
publisher IEEE
record_format Article
series IEEE Access
spelling doaj.art-aca12302051a44888f57e7efc8985c992023-02-15T00:00:21ZengIEEEIEEE Access2169-35362023-01-0111125251253510.1109/ACCESS.2023.324212410036086A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse StrategyFarah Haneef0https://orcid.org/0000-0002-3538-2622Muddassar Azam Sindhu1https://orcid.org/0000-0002-3411-9224Department of Computer Science, Quaid-i-Azam University, Islamabad, PakistanDepartment of Computer Science, Quaid-i-Azam University, Islamabad, PakistanA resurgent interest for grammatical inference aka automaton learning has emerged in several intriguing areas of computer sciences such as machine learning, software engineering, robotics and internet of things. An automaton learning algorithm commonly uses queries to learn the regular grammar of a Deterministic Finite Automaton (DFA). These queries are posed to a Minimum Adequate Teacher (MAT) by the learner (Learning Algorithm). The membership and equivalence queries which the learning algorithm may pose, are often capable of having their answers provided by the MAT. The three main categories of learning algorithms are incremental, sequential, and complete learning algorithms. In the presence of a MAT, the time complexity of existing DFA learning algorithms is polynomial. Therefore, in some applications these algorithms may fail to learn the system. In this study, we have reduced the time complexity of DFA learning from polynomial to logarithmic form. For this, we propose an efficient complete DFA learning algorithm; the Block based DFA Learning through Inverse Query (BDLIQ) using block based delta inverse strategy, which is based on the idea of inverse queries that John Hopcroft introduced for state minimization of a DFA. The BDLIQ algorithm possess <inline-formula> <tex-math notation="LaTeX">$O(\vert \Sigma \vert N.log N)$ </tex-math></inline-formula> complexity when a MAT is available. The MAT is also made capable of responding to inverse queries. We provide theoretical and empirical analysis of the proposed algorithm. Results show that our suggested approach for complete learning; BDLIQ algorithm, is more efficient than the ID algorithm in terms of time complexity.https://ieeexplore.ieee.org/document/10036086/Automaton learning algorithmcomplete learninginverse querymachine learningreinforcement learning
spellingShingle Farah Haneef
Muddassar Azam Sindhu
A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse Strategy
IEEE Access
Automaton learning algorithm
complete learning
inverse query
machine learning
reinforcement learning
title A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse Strategy
title_full A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse Strategy
title_fullStr A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse Strategy
title_full_unstemmed A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse Strategy
title_short A Reinforcement Learning Based Grammatical Inference Algorithm Using Block-Based Delta Inverse Strategy
title_sort reinforcement learning based grammatical inference algorithm using block based delta inverse strategy
topic Automaton learning algorithm
complete learning
inverse query
machine learning
reinforcement learning
url https://ieeexplore.ieee.org/document/10036086/
work_keys_str_mv AT farahhaneef areinforcementlearningbasedgrammaticalinferencealgorithmusingblockbaseddeltainversestrategy
AT muddassarazamsindhu areinforcementlearningbasedgrammaticalinferencealgorithmusingblockbaseddeltainversestrategy
AT farahhaneef reinforcementlearningbasedgrammaticalinferencealgorithmusingblockbaseddeltainversestrategy
AT muddassarazamsindhu reinforcementlearningbasedgrammaticalinferencealgorithmusingblockbaseddeltainversestrategy