A4 Refereed article in a conference publication
Improved Constructions for Succinct Affine Automata
Authors: Yakaryilmaz Abuzer
Editors: Han Yo-Sub, Ko Sang-Ki
Conference name: International Conference on Descriptional Complexity of Formal Systems
Publisher: Springer Science and Business Media Deutschland GmbH
Publishing place: Cham
Publication year: 2021
Journal: Lecture Notes in Computer Science
Book title : Descriptional Complexity of Formal Systems: 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings
Journal name in source: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Series title: Lecture Notes in Computer Science
Volume: 13037
First page : 188
Last page: 199
ISBN: 978-3-030-93488-0
eISBN: 978-3-030-93489-7
ISSN: 0302-9743
DOI: https://doi.org/10.1007/978-3-030-93489-7_16
Affine finite automata (AfAs) can be more succinct than probabilistic and quantum finite automata when recognizing some regular languages with bounded error. In this paper, we improve previously known succinct AFA constructions in three ways. First, we replace some of the fixed error bounds with arbitrarily small error bounds. Second, we present new constructions by using fewer states than the previous constructions. Third, we show that any language recognized by a nondeterministic finite automaton (NFA) is also recognized by bounded-error AfAs having one more state, and so, AfAs inherit all succinct results by NFAs. As a special case, we also show that any language recognized by an NFA is recognized by AfAs with zero error if the number of accepting path(s) for each member is the same number.
