Deterministic synchronization of bounded-delay automata

被引：8
|
作者：
Frougny, C
Sakarovitch, J [1 ]
机构：
[1] IBP, CNRS, Lab Informat Theor & Programmat, Paris, France
[2] Univ Paris 08, Paris, France
来源：
THEORETICAL COMPUTER SCIENCE | 1998年 / 191卷 / 1-2期
关键词：
D O I：
10.1016/S0304-3975(96)00305-2
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
It is shown that a subsequential automaton (i.e. an automaton deterministic with respect to the input) with bounded delay is equivalent to an on-line automaton, that is an automaton which is letter-to-letter after an initial period where it reads the input and output nothing, and subsequential. The results on the synchronisation of automaton with bounded delay established so far did not keep the property of being subsequential.
引用
收藏
页码：61 / 77
页数：17
相关论文
共 50 条
  • [41] Deterministic generalized automata
    Giammarresi, D
    Montalbano, R
    THEORETICAL COMPUTER SCIENCE, 1999, 215 (1-2) : 191 - 208
  • [42] From LTL and Limit-Deterministic Buchi Automata to Deterministic Parity Automata
    Esparza, Javier
    Kretinsky, Jan
    Raskin, Jean-Francois
    Sickert, Salomon
    TOOLS AND ALGORITHMS FOR THE CONSTRUCTION AND ANALYSIS OF SYSTEMS, TACAS 2017, PT I, 2017, 10205 : 426 - 442
  • [43] BOUNDED PARIKH AUTOMATA
    Cadilhac, Michael
    Finkel, Alain
    Mckenzie, Pierre
    INTERNATIONAL JOURNAL OF FOUNDATIONS OF COMPUTER SCIENCE, 2012, 23 (08) : 1691 - 1709
  • [44] Bounded Parikh Automata
    Cadilhac, Michael
    Finkel, Alain
    McKenzie, Pierre
    ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE, 2011, (63): : 93 - 102
  • [45] Characterizing classes of regular languages using prefix codes of bounded synchronization delay
    Diekert, Volker
    Walter, Tobias
    INTERNATIONAL JOURNAL OF ALGEBRA AND COMPUTATION, 2017, 27 (06) : 561 - 589
  • [46] Bounded immune response in immunotherapy described by the deterministic delay Kirschner-Panetta model
    Tsygvintsev, Alexei
    Banerjee, Sandip
    APPLIED MATHEMATICS LETTERS, 2014, 35 : 90 - 94
  • [47] On bounded languages and reversal-bounded automata
    Ibarra, Oscar H.
    Ravikumar, Bala
    INFORMATION AND COMPUTATION, 2016, 246 : 30 - 42
  • [48] Pushdown automata with bounded nondeterminism and bounded ambiguity
    Herzog, C
    THEORETICAL COMPUTER SCIENCE, 1997, 181 (01) : 141 - 157
  • [49] Synchronization of pushdown automata
    Caucal, Didier
    DEVELOPMENTS IN LANGUAGE THEORY, PROCEEDINGS, 2006, 4036 : 120 - 132
  • [50] SYNCHRONIZATION OF FINITE AUTOMATA
    DESCHAMPS, JP
    PHILIPS RESEARCH REPORTS, 1972, 27 (02): : 126 - +
12345