Improved Constructions for Succinct Affine Automata




Yakaryilmaz Abuzer

Han Yo-Sub, Ko Sang-Ki

International Conference on Descriptional Complexity of Formal Systems

PublisherSpringer Science and Business Media Deutschland GmbH

Cham

2021

Lecture Notes in Computer Science

Descriptional Complexity of Formal Systems: 23rd IFIP WG 1.02 International Conference, DCFS 2021, Virtual Event, September 5, 2021, Proceedings

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Lecture Notes in Computer Science

13037

188

199

978-3-030-93488-0

978-3-030-93489-7

0302-9743

DOIhttps://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.



Last updated on 2024-26-11 at 11:41