Wyniki wyszukiwania - BazTech

1

Growing Grammars and Length-reducing Automata

Jurdziński T.

Fundamenta Informaticae

|

2011

|

Vol. 112, nr 2/3

193-217

EN

Growing context-sensitive grammars were introduced in 1986 as a restricted variant of context-sensitive grammars, where all productions are length increasing. Several interesting properties of these grammars have been shown since then, including polynomial time complexity of the membership problem and machine model characterizations. Various characterizations of the model, efficient recognition algorithm and the properties of its deterministic variant (possessing a characterization by string-rewriting systems) justify the practical value. Moreover, as pointed out by McNaughton in 1999, growing context-sensitive grammars complement the Chomsky hierarchy in a very natural way. This article reviews results on this topic and proposes some open problems.

2

The Boolean Closure of Growing Context-Sensitive Languages

Jurdziński T.

Fundamenta Informaticae

|

2008

|

Vol. 89, nr 2-3

289-305

EN

The set of growing context-sensitive languages (GCSL) is a naturally defined subclass of context-sensitive languages whose membership problem is solvable in polynomial time. Moreover, growing context-sensitive languages and their deterministic counterpart called Church-Rosser Languages (CRL) complement the Chomsky hierarchy in a natural way [13]. In this paper, closures of GCSL under the boolean operations are investigated. It is shown that there exists an infinite intersection hierarchy for GCSL and CRL, answering an open problem from [2]. Furthermore, the expressive power of the boolean closures of GCSL, CRL, CFL and LOGCFL are compared.

3

Deterministic Two-Way Restarting Automata and Marcus Contextual Grammars

Jurdziński T., Otto F., Mráz F., Plátek M.

Fundamenta Informaticae

|

2005

|

Vol. 64, nr 1-4

217-228

EN

It is known that for (right-) monotone deterministic one-way restarting automata, the use of auxiliary symbols does not increase the expressive power. Here we show that the same is true for deterministic two-way restarting automata that are right-left-monotone. Moreover, we present a transformation of this kind of restarting automata into contextual grammars with regular selection.

4

Communication complexity for multi-speed cooperating automata

Jurdziński T., Kutyłowski M., Rzechonek P., Zatopiański J.

Prace Naukowe Instytutu Matematyki Politechniki Wrocławskiej. Konferencje

|

2001

|

Vol. 24, nr 3

17-30

EN

We consider bounded memory asynchronous systems. They consist of finite automata working independently and communicating by exchanging messages. We discuss what impact the differences in timing models on computational power of such systems have. It is known that a total lack of synchronization has profound consequences for computational power of systems of automata. Lower bounds found for this model indicate that the only way to perform a nontrivial computation would be to re-synchronize the automata every 0(1) steps. We examine much weaker form of asynchronism. We consider the model in which automata work with constant speeds, but the speed might be different for each automaton, and the automata have no knowledge about the speeds. (We call this model multi-speed systems of finite automata.) In particular, it may happen that some speed cannot be expressed exactly by the means of internal states of automata. Nevertheless, we expect the automata to compute the correct output. The main result of this paper is that, quite unexpectedly, the systems described might be as powerful as synchronous systems, where all automata work with the same speed. More precisely, some languages, which have been candidates for distinguishing multi-speed and synchronous models, can be recognized by multi-speed systems with approximately the same number of messages sent.