Reversals-space-parallelism tradeoffs for language recognition
Juraj Hromkovič (1991)
Mathematica Slovaca
Similarity:
Juraj Hromkovič (1991)
Mathematica Slovaca
Similarity:
Viliam Geffert, L'ubomíra Ištoňová (2010)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
We study the relation between the standard two-way automata and more powerful devices, namely, two-way finite automata equipped with some additional “pebbles” that are movable along the input tape, but their use is restricted (nested) in a stack-like fashion. Similarly as in the case of the classical two-way machines, it is not known whether there exists a polynomial trade-off, in the number of states, between the nondeterministic and deterministic two-way automata with nested pebbles....
Viliam Geffert, Norbert Popély (2000)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Maria José Serna (1989)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
Miloslav Nekvinda (1973)
Kybernetika
Similarity:
Ludwig Staiger (2005)
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
Similarity:
The paper presents an elementary approach for the calculation of the entropy of a class of languages. This approach is based on the consideration of roots of a real polynomial and is also suitable for calculating the Bernoulli measure. The class of languages we consider here is a generalisation of the Łukasiewicz language.
Danilo Bruschi, Giovanni Pighizzini (2006)
RAIRO - Theoretical Informatics and Applications
Similarity:
In this paper we analyze some intrusion detection strategies proposed in the literature and we show that they represent the various facets of a well known formal languages problem: computing the distance between a string and a language . In particular, the main differences among the various approaches adopted for building intrusion detection systems can be reduced to the characteristics of the language and to the notion of distance adopted. As a further contribution we will also show...