On groups generated by bi-reversible automata: The two-state case over a changing alphabet

作者：

Highlights：

• Extending the notion of bi-reversibility to automata over a changing alphabet.

• Absence of 2-state bi-reversible automata over a bounded changing alphabet which generate the non-abelian free group F2.

• Natural and applicable realization of F2 by a 2-state bi-reversible automaton over an arbitrary unbounded changing alphabet.

• Classification of groups generated by a 2-state bi-reversible automaton over the sequence of binary alphabets.

摘要

•Extending the notion of bi-reversibility to automata over a changing alphabet.•Absence of 2-state bi-reversible automata over a bounded changing alphabet which generate the non-abelian free group F2.•Natural and applicable realization of F2 by a 2-state bi-reversible automaton over an arbitrary unbounded changing alphabet.•Classification of groups generated by a 2-state bi-reversible automaton over the sequence of binary alphabets.

论文关键词：Changing alphabet,Transducer,Mealy automaton,Automaton over a changing alphabet,Group generated by automaton,Automorphism group,Free group

论文评审过程：Received 20 July 2016, Revised 28 December 2016, Accepted 11 January 2017, Available online 20 January 2017, Version of Record 27 February 2017.

论文官网地址：https://doi.org/10.1016/j.jcss.2017.01.004