Bounded Parikh Automata

被引：3
作者：
Cadilhac, Michael [1 ]
Finkel, Alain [2 ,3 ]
McKenzie, Pierre [1 ]
机构：
[1] Univ Montreal, DIRO, Montreal, PQ, Canada
[2] LSV ENS, Cachan, France
[3] CNRS, Paris, France
来源：
ELECTRONIC PROCEEDINGS IN THEORETICAL COMPUTER SCIENCE | 2011年 / 63期
关键词：
D O I：
10.4204/EPTCS.63.13
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
The Parikh finite word automaton model (PA) was introduced and studied by Klaedtke and Ruess [18]. Here, by means of related models, it is shown that the bounded languages recognized by PA are the same as those recognized by deterministic PA. Moreover, this class of languages is the class of bounded languages whose set of iterations is semilinear.
引用
收藏
页码：93 / 102
页数：10
相关论文
共 50 条
[31]   Observability and reconstructibility of bounded cellular automata [J].
Plenet, Theo ;
El Yacoubi, Samira ;
Raievsky, Clement ;
Lefevre, Laurent .
INTERNATIONAL JOURNAL OF SYSTEMS SCIENCE, 2022, 53 (14) :2901-2917
[32]   Bounded monotone recursion and multihead automata [J].
S. S. Marchenkov .
Programming and Computer Software, 2013, 39 :301-308
[33]   Parikh Matrices and Parikh Rewriting Systems [J].
Teh, Wen Chean .
FUNDAMENTA INFORMATICAE, 2016, 146 (03) :305-320
[34]   Converting nondeterministic automata and context-free grammars into Parikh equivalent one-way and two-way deterministic automata [J].
Lavado, Giovanna J. ;
Pighizzini, Giovanni ;
Seki, Shinnosuke .
INFORMATION AND COMPUTATION, 2013, 228 :1-15
[35]   CLASSES OF LANGUAGES + LINEAR-BOUNDED AUTOMATA [J].
KURODA, SY .
INFORMATION AND CONTROL, 1964, 7 (02) :207-&
[36]   ONLINE N-BOUNDED MULTICOUNTER AUTOMATA [J].
INOUE, K ;
TAKANAMI, I .
INFORMATION SCIENCES, 1979, 17 (03) :239-251
[37]   Alternating Timed Automata over Bounded Time [J].
Jenkins, Mark ;
Ouaknine, Joel ;
Rabinovich, Alexander ;
Worrell, James .
25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010), 2010, :60-69
[38]   SPACE-BOUNDED PROBABILISTIC GAME AUTOMATA [J].
CONDON, A .
JOURNAL OF THE ACM, 1991, 38 (02) :472-494
[39]   Amenability of bounded automata groups on infinite alphabets [J].
Reinke, Bernhard .
BULLETIN OF THE LONDON MATHEMATICAL SOCIETY, 2024, 56 (07) :2460-2471
[40]   Improved Bounded Model Checking of Timed Automata [J].
Smith, Robert L. ;
Bersani, Marcello M. ;
Rossi, Matteo ;
San Pietro, Pierluigi .
2021 IEEE/ACM 9TH INTERNATIONAL CONFERENCE ON FORMAL METHODS IN SOFTWARE ENGINEERING (FORMALISE 2021), 2021, :97-110
12345