Closure properties of predicates recognized by deterministic and non-deterministic asynchronous automata

Details Closure properties of predicates recognized by deterministic and non-deterministic asynchronous automata Closure properties of predicates recognized by deterministic and non-deterministic asynchronous automata

2010-10-14

arxiv.org/abs/1010.3039v1

Mathematics

Logic

22 pages, 3 figures

Scientific paper

Let A be a finite alphabet and let L contained in (A*)^n be an n-variable language over A. We say that L is regular if it is the language accepted by a synchronous n-tape finite state automaton, it is quasi-regular if it is accepted by an asynchronous n-tape automaton, and it is weakly regular if it is accepted by a non-deterministic asynchronous n-tape automaton. We investigate the closure properties of the classes of regular, quasi-regular, and weakly regular languages under first-order logic, and apply these observations to an open decidability problem in automatic group theory.

Affiliated with

Also associated with

No associations

Rating

Closure properties of predicates recognized by deterministic and non-deterministic asynchronous automata 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 Closure properties of predicates recognized by deterministic and non-deterministic asynchronous automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Closure properties of predicates recognized by deterministic and non-deterministic asynchronous automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-203220