Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable

Details Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable

2012-01-24

arxiv.org/abs/1201.5070v1

Computer Science

Logic in Computer Science

19 pages, 2 figures

Scientific paper

A tree automatic structure is a structure whose domain can be encoded by a regular tree language such that each relation is recognisable by a finite automaton processing tuples of trees synchronously. Words can be regarded as specific simple trees and a structure is word automatic if it is encodable using only these trees. The question naturally arises whether a given tree automatic structure is already word automatic. We prove that this problem is decidable for tree automatic scattered linear orderings. Moreover, we show that in case of a positive answer a word automatic presentation is computable from the tree automatic presentation.

Affiliated with

Also associated with

No associations

Rating

Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Word Automaticity of Tree Automatic Scattered Linear Orderings Is Decidable will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-107554