Using Structure of Automata for Faster Synchronizing Heuristics

被引：1

作者：

Cirisci, Berk ^{[1
]}

Kahraman, Muhammed Kerem ^{[1
]}

Yildirimoglu, Cagri Uluc ^{[1
]}

Kaya, Kamer ^{[1
]}

Yenigun, Husnu ^{[1
]}

机构：

[1] Sabanci Univ, Fac Engn & Nat Sci, Comp Sci & Engn, Istanbul, Turkey

来源：

PROCEEDINGS OF THE 6TH INTERNATIONAL CONFERENCE ON MODEL-DRIVEN ENGINEERING AND SOFTWARE DEVELOPMENT | 2018年

关键词：

Finite State Automata; Synchronizing Sequences; Strongly Connected Component; SEQUENCES;

D O I：

10.5220/0006660805440551

中图分类号：

TP31 [计算机软件];

学科分类号：

081202 ; 0835 ;

摘要：

The problem of finding a synchronizing sequence for an automaton is an interesting problem studied widely in the literature. Finding a shortest synchronizing sequence is an NP-Hard problem. Therefore, there are heuristics to find short synchronizing sequences. Some heuristics work fast but produce long synchronizing sequences, whereas some heuristics work slow but produce relatively shorter synchronizing sequences. In this paper we propose a method for using these heuristics by considering the connectedness of automata. Applying the proposed approach of using these heuristics make the heuristics work faster than their original versions, without sacrificing the quality of the synchronizing sequences.

引用

页码：544 / 551

页数：8

共 50 条

[31] Call classification using recurrent neural networks, support vector machines and finite state automata
Garfield, S
Wermter, S
KNOWLEDGE AND INFORMATION SYSTEMS, 2006, 9 (02) : 131 - 156
[32] Call classification using recurrent neural networks, support vector machines and finite state automata
Sheila Garfield
Stefan Wermter
Knowledge and Information Systems, 2006, 9 : 131 - 156
[33] Cayley-Graph-based Data Centers and Space Requirements of a Routing Scheme using Automata
Camelo, Miguel
Vila, Pere
Fabrega, Lluis
Papadimitriou, Dimitri
2014 IEEE 34TH INTERNATIONAL CONFERENCE ON DISTRIBUTED COMPUTING SYSTEMS WORKSHOPS (ICDCSW), 2014, : 63 - 69
[34] Modelling of Robot Attention Demand in Human-Robot Interaction Using Finite Fuzzy State Automata
Abou Saleh, Jamil
Karray, Fakhreddine
Morckos, Michael
2012 IEEE INTERNATIONAL CONFERENCE ON FUZZY SYSTEMS (FUZZ-IEEE), 2012,
[35] Spelling Correction for Text Documents in Bahasa Indonesia Using Finite State Automata and Levinshtein Distance Method
Mawardi, Viny Christanti
Susanto, Niko
Naga, Dali Santun
3RD INTERNATIONAL CONFERENCE ON ELECTRICAL SYSTEMS, TECHNOLOGY AND INFORMATION (ICESTI 2017), 2018, 164
[36] Using Finite Automata to Compute the Base-b Representation of the Golden Ratio and Other Quadratic Irrationals
Barnoff, Aaron
Bright, Curtis
Shallit, Jeffrey
IMPLEMENTATION AND APPLICATION OF AUTOMATA, CIAA 2024, 2024, 15015 : 35 - 50
[37] Using finite state automata (FSA) for formal modelling of affordances in human-machine cooperative manufacturing systems
Kim, N.
Shin, D.
Wysk, R. A.
Rothrock, L.
INTERNATIONAL JOURNAL OF PRODUCTION RESEARCH, 2010, 48 (05) : 1303 - 1320
[38] Function Annotation for Pseudoknot Using Structure Similarity
Chen, Qingfeng
Chen, Yi-Ping Phoebe
IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2011, 8 (06) : 1535 - 1544
[39] An improved protein structure evaluation using a semi-empirically derived structure property
Pal, Manoj Kumar
Lahiri, Tapobrata
Tanwar, Garima
Kumar, Rajnish
BMC STRUCTURAL BIOLOGY, 2018, 18
[40] Searching for Potential gRNA Off-Target Sites for CRISPR/Cas9 using Automata Processing across Different Platforms
Bo, Chunkun
Dang, Vinh
Sadredini, Elaheh
Skadron, Kevin
2018 24TH IEEE INTERNATIONAL SYMPOSIUM ON HIGH PERFORMANCE COMPUTER ARCHITECTURE (HPCA), 2018, : 737 - 748

← 1 2 3 4 5 →