Wyniki wyszukiwania - BazTech

1

On McNaughton Families of Languages That Are Specified by Some Variants of Monadic String-Rewriting Systems

Leupold P., Otto F.

Fundamenta Informaticae

|

2011

|

Vol. 112, nr 2/3

219-238

EN

We study the McNaughton families of languages that are specified by four different variants of monadic string-rewriting systems: strictly monadic systems, monadic systems, inverse context-free systems, and generalized monadic systems. In the general case these four variants yield the same McNaughton family of languages, which coincides with the class of context-free languages. In the case of confluent systems, however, we obtain two McNaughton families by showing that special rules, that is, rules with empty right-hand side, are not needed. This implies that in this situation strictly monadic systems are as expressive as monadic systems, and inverse context-free systems are as expressive as generalized monadic systems. The McNaughton family defined by the former systems is contained in the McNaughton family that is defined by the latter systems, and this inclusion is proper if and only if the former family is not closed under inverse alphabeticmorphisms. Finally, we show that the latter family is a proper subclass of the class of deterministic context-free languages.

2

5'→3' Watson-Crick AutomataWith Several Runs

Leupold P., Nagy B.

Fundamenta Informaticae

|

2010

|

Vol. 104, nr 1/2

71-91

EN

5'→3' WK-automata are Watson-Crick automata whose two heads start on opposite ends of the input word and always run in opposite directions. One full reading in both directions is called a run. We prove that the expressive power of these automata increases with every additional run that they can make, both for deterministic and non-deterministic machines. This defines two incomparable infinite hierarchies of language classes between the regular and the context-sensitive languages. These hierarchies are complemented with classes defined by several restricted variants of 5'→3' WK-automata like stateless automata. Finally we show that several standard problems are undecidable for languages accepted by 5'→3' WK-automata in only one run, for example the emptiness and the finiteness problems.

3

Observation of String-Rewriting Systems

Cavaliere M., Leupold P.

Fundamenta Informaticae

|

2006

|

Vol. 74, nr 4

447-462

EN

Models of computation in theoretical computer science very frequently consist of a device performing some type of process, like a Turing machine and its computation or a grammar and its derivation. After the process halts, only some final output is regarded as the result. In adding an observer to such a device, one can obtain a protocol of the entire process and then use this as the result of the computation. In several recent articles this approach has proved to often exceed greatly the power of the observed system. Here we apply this architecture to string-rewriting systems. They receive a string as input, and a combination of observer and decider then determines whether this string is accepted. This decision is based only on the rewriting process performed. First we determine the power of painter, context-free, and inverse context-free rewriting systems in terms of McNaughton languages. Then these are investigated as components of rewriting/observer systems, and we obtain characterizations of the classes of context-sensitive and recursively enumerable languages. Finally we investigate some limitations, i.e. characterize some systems, where observation does not increase power.