@inproceedings{5dfaa4e16c9c4355aa6040af56f6fac1,
title = "Improved Constructions for Succinct Affine Automata",
abstract = "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.",
keywords = "Affine automata, Bounded error, Linear systems, One-sided error, Probabilistic automata, Quantum automata, State complexity, Succinctness, Zero error",
author = "Abuzer Yakaryilmaz",
note = "Publisher Copyright: {\textcopyright} 2021, IFIP International Federation for Information Processing.",
year = "2021",
doi = "10.1007/978-3-030-93489-7\_16",
language = "English",
isbn = "9783030934880",
volume = "13037 LNCS",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Science and Business Media Deutschland GmbH",
pages = "188--199",
booktitle = "Descriptional Complexity of Formal Systems - 23rd IFIP WG 1.02 International Conference, DCFS 2021, Proceedings",
}