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...
Main Authors: | , |
---|---|
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 |