Automata on ordinals and automaticity of linear orders

作者：Schlicht Philipp^*; Stephan Frank

来源：Annals of Pure and Applied Logic, 2013, 164(5): 523-527.

DOI：10.1016/j.apal.2012.11.007

• Automatic structures
• Linear orders

We investigate structures recognizable by finite state automata with an input tape of length a limit ordinal. At limits, the set of states which appear unboundedly often before the limit are mapped to a limit state. We describe a method for proving non-automaticity and apply this to determine the optimal bounds for the ranks of linear orders recognized by such automata.

• 出版日期2013-5