×

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
Full Text: DOI