A4 Vertaisarvioitu artikkeli konferenssijulkaisussa
Improved Constructions for Succinct Affine Automata
Tekijät: Yakaryilmaz Abuzer
Toimittaja: Han Yo-Sub, Ko Sang-Ki
Konferenssin vakiintunut nimi: International Conference on Descriptional Complexity of Formal Systems
Kustantaja: Springer Science and Business Media Deutschland GmbH
Kustannuspaikka: Cham
Julkaisuvuosi: 2021
Journal: Lecture Notes in Computer Science
Kokoomateoksen nimi: Descriptional Complexity of Formal Systems: 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings
Tietokannassa oleva lehden nimi: Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Sarjan nimi: Lecture Notes in Computer Science
Vuosikerta: 13037
Aloitussivu: 188
Lopetussivu: 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.
