Dang, Zhe; Ibarra, Oscar H.; Lin, Qin Sampling a two-way finite automaton. (English) Zbl 1327.68153 Adamatzky, Andrew (ed.), Automata, universality, computation. Tribute to Maurice Margenstern. Cham: Springer (ISBN 978-3-319-09038-2/hbk; 978-3-319-09039-9/ebook). Emergence, Complexity and Computation 12, 103-115 (2015). Summary: We study position sampling in a 2-way nondeterministic finite automaton (2NFA) to measure the information dependency and information flow between state variables, based on the information-theoretic sampling technique proposed in [Q. Li and the first author, Theor. Comput. Sci. 577, 125–140 (2015; Zbl 1309.68062)]. We prove that for a 2NFA, the language generated by position sampling is regular. We also show that for a 2NFA, we can effectively find a vector of sampling positions that maximizes dependency and information flow in a run of the 2NFA. Finally, we give some language properties of sampled runs of 2NFAs augmented with restricted unbounded storage.For the entire collection see [Zbl 1305.68018]. MSC: 68Q45 Formal languages and automata Citations:Zbl 1309.68062 PDFBibTeX XMLCite \textit{Z. Dang} et al., Emerg. Complex. Comput. 12, 103--115 (2015; Zbl 1327.68153) Full Text: DOI