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 条
  • [41] Plant Model-Based Fault Detection during Aircraft Takeoff Using Non-Deterministic Finite-State Automata
    Settele, Ferdinand
    Weber, Alexander
    Knoll, Alexander
    AEROSPACE, 2020, 7 (08)
  • [42] A Highway-Driving System Design Viewpoint Using an Agent-Based Modeling of an Affordance-Based Finite State Automata
    Ransikarbum, Kasin
    Kim, Namhun
    Ha, Sangho
    Wysk, Richard A.
    Rothrock, Ling
    IEEE ACCESS, 2018, 6 : 2193 - 2205
  • [43] Modular decomposition of protein structure using community detection
    Grant, William P.
    Ahnert, Sebastian E.
    JOURNAL OF COMPLEX NETWORKS, 2019, 7 (01) : 101 - 113
  • [44] Protein secondary structure assignment using residual networks
    Antony, Jisna Vellara
    Koya, Roosafeed
    Pournami, Pulinthanathu Narayanan
    Nair, Gopakumar Gopalakrishnan
    Balakrishnan, Jayaraj Pottekkattuvalappil
    JOURNAL OF MOLECULAR MODELING, 2022, 28 (09)
  • [45] Faster 3D saturation-recovery based myocardial T1 mapping using a reduced number of saturation points and denoising
    Nordio, Giovanna
    Bustin, Aurelien
    Odille, Freddy
    Schneider, Torben
    Henningsson, Markus
    Prieto, Claudia
    Botnar, Rene M.
    PLOS ONE, 2020, 15 (04):
  • [46] Prediction of RNA secondary structure with pseudoknots using integer programming
    Poolsap, Unyanee
    Kato, Yuki
    Akutsu, Tatsuya
    BMC BIOINFORMATICS, 2009, 10
  • [47] Automatic structure classification of small proteins using random forest
    Jain, Pooja
    Hirst, Jonathan D.
    BMC BIOINFORMATICS, 2010, 11
  • [48] Pseudoknots Prediction on RNA Secondary Structure Using Term Rewriting
    Chowdhury, Linkon
    Khan, Mohammad Ibrahim
    BIOINFORMATICS AND BIOMEDICAL ENGINEERING (IWBBIO 2015), PT I, 2015, 9043 : 577 - 588
  • [49] Using the RosettaSurface Algorithm to Predict Protein Structure at Mineral Surfaces
    Pacella, Michael S.
    Koo, Da Chen Emily
    Thottungal, Robin A.
    Gray, Jeffrey J.
    RESEARCH METHODS IN BIOMINERALIZATION SCIENCE, 2013, 532 : 343 - 366
  • [50] USING RECURRENT NEURAL NETWORKS TO LEARN THE STRUCTURE OF INTERCONNECTION NETWORKS
    GOUDREAU, MW
    GILES, CL
    NEURAL NETWORKS, 1995, 8 (05) : 793 - 804
12345