Multiset Languages Accepted by Deterministic Multiset Finite Automata with Detection as a Specific Kind of Semilinear Languages

被引：0
作者：
Martinek, Pavel [1 ]
机构：
[1] Tomas Bata Univ Zlin, Dept Math, Nam TG Masaryka 5555, Zlin 76001, Czech Republic
来源：
PROCEEDINGS OF THE INTERNATIONAL CONFERENCE ON NUMERICAL ANALYSIS AND APPLIED MATHEMATICS 2016 (ICNAAM-2016) | 2017年 / 1863卷
关键词：
D O I：
10.1063/1.4992717
中图分类号：
O29 [应用数学];
学科分类号：
070104 ;
摘要：
The class of multiset languages accepted by deterministic multiset finite automata with detection is strictly included in the class of multiset regular languages. Since multiset regular languages coincide with semilinear languages, the strict inclusion means that some restrictive conditions imposed to semilinear languages can narrow them appropriately. The paper provides a condition which is expressed with help of semilinear languages and which is necessary for the multiset languages accepted by deterministic multiset finite automata with detection.
引用
收藏
页数：4
相关论文
共 50 条
[41]   Size of nondeterministic and deterministic automata for certain languages [J].
Ozols, R ;
Freivalds, R ;
Mancinska, L ;
Ozols, M .
FCS '05: PROCEEDINGS OF THE 2005 INTERNATIONAL CONFERENCE ON FOUNDATIONS OF COMPUTER SCIENCE, 2005, :169-175
[42]   Deterministic ordered restarting automata for picture languages [J].
Otto, Friedrich ;
Mraz, Frantisek .
ACTA INFORMATICA, 2015, 52 (7-8) :593-623
[43]   On regular tree languages and deterministic pushdown automata [J].
Jan Janoušek ;
Bořivoj Melichar .
Acta Informatica, 2009, 46 :533-547
[44]   Deterministic ordered restarting automata for picture languages [J].
Friedrich Otto ;
František Mráz .
Acta Informatica, 2015, 52 :593-623
[45]   Deterministic recognizability of picture languages with Wang automata [J].
Lonati, Violetta ;
Pradella, Matteo .
DISCRETE MATHEMATICS AND THEORETICAL COMPUTER SCIENCE, 2010, 12 (04) :73-94
[46]   Efficient Construction of Semilinear Representations of Languages Accepted by Unary NFA [J].
Sawa, Zdenek .
REACHABILITY PROBLEMS, 2010, 6227 :176-182
[47]   FINITE AUTOMATA AND RATIONAL LANGUAGES AN INTRODUCTION [J].
BERSTEL, J .
FORMAL PROPERTIES OF FINITE AUTOMATA AND APPLICATIONS, 1989, 386 :2-14
[48]   Languages recognized by a class of finite automata [J].
Kelarev, A.V. ;
Sokratova, O.V. .
Acta Cybernetica, 2001, 15 (01) :45-52
[49]   Languages recognizable by quantum finite automata [J].
Freivalds, R .
IMPLEMENTATION AND APPLICATION OF AUTOMATA, 2006, 3845 :1-14
[50]   Quantum Automata and Languages of Finite Index [J].
Benso, Andrea ;
D'Alessandro, Flavio ;
Papi, Paolo .
REACHABILITY PROBLEMS, RP 2024, 2024, 15050 :88-103
12345