{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,10,2]],"date-time":"2024-10-02T04:16:12Z","timestamp":1727842572310},"reference-count":31,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2023,9,7]],"date-time":"2023-09-07T00:00:00Z","timestamp":1694044800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/academic.oup.com\/pages\/standard-publication-reuse-rights"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2024,9,25]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>This paper presents four state-of-art methods for the finite-state automaton inference based on a sample of labeled strings. The first algorithm is Exbar, and the next three are mathematical models based on ASP, SAT and SMT theories. The potentiality of using multiprocessor computers in the context of automata inference was our research\u2019s primary goal. In a series of experiments, we showed that our parallelization of the exbar algorithm is the best choice when a multiprocessor system is available. Furthermore, we obtained a superlinear speedup for some of the prepared datasets, achieving almost a 5-fold speedup on the median, using 12 and 24 processes.<\/jats:p>","DOI":"10.1093\/jigpal\/jzad014","type":"journal-article","created":{"date-parts":[[2023,9,9]],"date-time":"2023-09-09T00:01:21Z","timestamp":1694217681000},"page":"909-935","source":"Crossref","is-referenced-by-count":0,"title":["Report on the exact methods for finding minimum-sized DFA"],"prefix":"10.1093","volume":"32","author":[{"given":"Wojciech","family":"Wieczorek","sequence":"first","affiliation":[{"name":"Department of Computer Science and Automatics , University of Bielsko-Biala, Willowa 2, Bielsko-Biala, 43-309, \u015al\u0105sk, , wwieczorek@ath.bielsko.pl","place":["Poland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"\u0141ukasz","family":"Str\u0105k","sequence":"additional","affiliation":[{"name":"Faculty of Science and Technology , University of Silesia in Katowice, Bankowa 14, Katowice, 40-007, \u015al\u0105sk,","place":["Poland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Arkadiusz","family":"Nowakowski","sequence":"additional","affiliation":[{"name":"Faculty of Science and Technology , University of Silesia in Katowice, Bankowa 14, Katowice, 40-007, \u015al\u0105sk, , arkadiusz.nowakowski@us.edu.pl","place":["Poland"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"286","published-online":{"date-parts":[[2023,9,7]]},"reference":[{"key":"2024100113463855500_ref1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511543357","volume-title":"Knowledge Representation, Reasoning and Declarative Problem Solving","author":"Baral","year":"2003"},{"key":"2024100113463855500_ref2","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/BFb0054081","article-title":"Pattern discovery in biosequences","volume-title":"Grammatical Inference","author":"Brazma","year":"1998"},{"key":"2024100113463855500_ref3","doi-asserted-by":"crossref","first-page":"783","DOI":"10.1017\/S147106841400009X","article-title":"Predicate logic as a modeling language: modeling and solving some machine learning and data mining problems with IDP3","volume":"15","author":"Bruynooghe","year":"2014","journal-title":"Theory and Practice of Logic Programming"},{"volume-title":"IDP-Z3: A Reasoning Engine for FO(.)","year":"2022","author":"Carbonnelle","key":"2024100113463855500_ref4"},{"key":"2024100113463855500_ref5","first-page":"5539","article-title":"ASP-based declarative process mining","volume-title":"Proceedings of the AAAI Conference on Artificial Intelligence","author":"Chiariello","year":"2022"},{"volume-title":"Regular Inference as a Graph Coloring Problem","year":"1997","author":"Coste","key":"2024100113463855500_ref6"},{"key":"2024100113463855500_ref7","first-page":"148","article-title":"Symmetry-breaking predicates for search problems","volume-title":"Proceedings of the Fifth International Conference on Principles of Knowledge Representation and Reasoning","author":"Crawford","year":"1996"},{"key":"2024100113463855500_ref8","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1007\/BFb0054077","article-title":"Learning regular grammars to model musical style: Comparing different coding schemes","volume-title":"Grammatical Inference","author":"Cruz-Alc\u00e1zar","year":"1998"},{"key":"2024100113463855500_ref9","doi-asserted-by":"crossref","first-page":"1332","DOI":"10.1016\/j.patcog.2005.01.003","article-title":"A bibliographical study of grammatical inference","volume":"38","author":"de la Higuera","year":"2005","journal-title":"Pattern Recognition"},{"key":"2024100113463855500_ref10","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139194655","volume-title":"Grammatical Inference: Learning Automata and Grammars","author":"de la Higuera","year":"2010"},{"key":"2024100113463855500_ref11","first-page":"7","article-title":"An introduction to the analysis of ranked response data","volume":"27","author":"Finch","year":"2022","journal-title":"Practical Assessment, Research, and Evaluation"},{"key":"2024100113463855500_ref12","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1007\/978-3-031-01561-8","article-title":"Answer set solving in practice","volume":"6","author":"Gebser","year":"2012","journal-title":"Synthesis Lectures on Artificial Intelligence and Machine Learning"},{"key":"2024100113463855500_ref13","doi-asserted-by":"crossref","first-page":"302","DOI":"10.1016\/S0019-9958(78)90562-4","article-title":"Complexity of automaton identification from given data","volume":"37","author":"Gold","year":"1978","journal-title":"Information and Control"},{"key":"2024100113463855500_ref14","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1007\/BF02523693","article-title":"Greed is good: approximating independent sets in sparse and bounded-degree graphs","volume":"18","author":"Halld\u00f3rsson","year":"1997","journal-title":"Algorithmica"},{"volume-title":"Deterministic Parallel DPLL (DP2LL)","year":"2011","author":"Hamadi","key":"2024100113463855500_ref15"},{"key":"2024100113463855500_ref16","first-page":"66","article-title":"Exact DFA identification using SAT solvers","volume-title":"Grammatical Inference: Theoretical Results and Applications 10th International Colloquium, ICGI 2010","author":"Heule","year":"2010"},{"key":"2024100113463855500_ref17","doi-asserted-by":"crossref","DOI":"10.4135\/9781849208499","volume-title":"100 Statistical Tests","author":"Kanji","year":"2006"},{"key":"2024100113463855500_ref18","doi-asserted-by":"crossref","DOI":"10.1145\/3191315","volume-title":"Declarative Logic Programming: Theory, Systems, and Applications","author":"Kifer","year":"2018"},{"volume-title":"Faster Algorithms for Finding Minimal Consistent DFAs","year":"1999","author":"Lang","key":"2024100113463855500_ref19"},{"key":"2024100113463855500_ref20","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-24658-7","volume-title":"Answer Set Programming","author":"Lifschitz","year":"2019"},{"key":"2024100113463855500_ref21","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/s10601-012-9121-3","article-title":"An overview of parallel SAT solving","volume":"17","author":"Martins","year":"2012","journal-title":"Constraints"},{"key":"2024100113463855500_ref22","first-page":"269","article-title":"Finite-state transducers in language and speech processing","volume":"23","author":"Mohri","year":"1997","journal-title":"Computational Linguistics"},{"key":"2024100113463855500_ref23","doi-asserted-by":"crossref","first-page":"321","DOI":"10.3233\/FI-2019-1788","article-title":"Applying modern SAT-solvers to solving hard problems","volume":"165","author":"Niewiadomski","year":"2019","journal-title":"Fundamenta Informaticae"},{"key":"2024100113463855500_ref24","doi-asserted-by":"crossref","first-page":"1619","DOI":"10.1109\/43.806807","article-title":"A new algorithm for exact reduction of incompletely specified finite state machines","volume":"18","author":"Pena","year":"1999","journal-title":"IEEE Trans. on CAD of Integrated Circuits and Systems"},{"key":"2024100113463855500_ref25","article-title":"Combinatorial search","volume-title":"Parallel Programming in C with MPI and OpenMP, Chapter 16","author":"Quinn","year":"2003"},{"key":"2024100113463855500_ref26","doi-asserted-by":"crossref","DOI":"10.4135\/9781412961288","volume-title":"Encyclopedia of Research Design","author":"Salkind","year":"2010"},{"key":"2024100113463855500_ref27","first-page":"182","article-title":"Model learning as a satisfiability modulo theories problem","volume-title":"Language and Automata Theory and Applications \u2013 12th International Conference, LATA 2018, Ramat Gan, Israel, April 9-11, 2018, Proceedings","author":"Smetsers","year":"2018"},{"key":"2024100113463855500_ref28","doi-asserted-by":"crossref","first-page":"444","DOI":"10.1016\/j.scico.2014.05.008","article-title":"A survey of grammatical inference in software engineering","volume":"96","author":"Stevenson","year":"2014.","journal-title":"Science of Computer Programming"},{"key":"2024100113463855500_ref29","doi-asserted-by":"crossref","DOI":"10.3390\/app10217700","article-title":"Answer set programming for regular inference","volume":"10","author":"Wieczorek","year":"2020","journal-title":"Applied Sciences"},{"key":"2024100113463855500_ref30","doi-asserted-by":"crossref","first-page":"50","DOI":"10.1007\/978-3-030-77967-2_5","article-title":"Exact searching for the smallest deterministic automaton","volume-title":"Computational Science \u2013 ICCS 2021","author":"Wieczorek","year":"2021"},{"key":"2024100113463855500_ref31","doi-asserted-by":"crossref","first-page":"117","DOI":"10.1007\/978-3-319-74781-1_9","article-title":"Finding all minimum-size DFA consistent with given examples: SAT-based approach","volume-title":"Software Engineering and Formal Methods","author":"Zakirzyanov","year":"2018"}],"container-title":["Logic Journal of the IGPL"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/32\/5\/909\/59463951\/jzad014.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/jigpal\/article-pdf\/32\/5\/909\/59463951\/jzad014.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,10,1]],"date-time":"2024-10-01T13:46:57Z","timestamp":1727790417000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/jigpal\/article\/32\/5\/909\/7260056"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,9,7]]},"references-count":31,"journal-issue":{"issue":"5","published-online":{"date-parts":[[2023,9,7]]},"published-print":{"date-parts":[[2024,9,25]]}},"URL":"https:\/\/doi.org\/10.1093\/jigpal\/jzad014","relation":{},"ISSN":["1367-0751","1368-9894"],"issn-type":[{"type":"print","value":"1367-0751"},{"type":"electronic","value":"1368-9894"}],"subject":[],"published-other":{"date-parts":[[2024,10]]},"published":{"date-parts":[[2023,9,7]]}}}