On Interacting Automata with Limited Nondeterminism

• Autorzy: Buchholz T. , Klein A. , Kutrib M.
• Języki publikacji: EN

Abstrakty

EN

One-way and two-way cellular language acceptors with restricted nondeterminism are investigated. The number of nondeterministic state transitions is regarded as limited resource which depends on the length of the input. We center our attention to real-time, linear-time and unrestricted-time computations. A speed-up result that allows any linear-time computation to be sped-up to real-time is proved. The relationships to deterministic arrays are considered. For an important subclass a characterization in terms of deterministic language families and e-free homomorphisms is given. Finally we prove strong closure properties of languages acceptable with a constant number of nondeterministic transitions.

Słowa kluczowe

EN

cellular automata; formal languages; nondeterminism; parallel computing

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2002
• Tom: Vol. 52, nr 1-3
• Strony: 15--38
• Opis fizyczny: tab., wykr., bibliogr. 31 poz.

Twórcy

autor

Buchholz T.

autor

Klein A.

autor

Kutrib M.

• Institute of Informatics, University of Giessen, Arndstr. 2, D-35392 Giessen, Germany,