Titlebook: Language and Automata Theory and Applications; 5th International Co Adrian-Horia Dediu,Shunsuke Inenaga,Carlos Martín- Conference proceedin

animated

Recognizing Shuffled Languagesan recognition, and natural language processing. We study the complexity of the membership problem for such models, i.e., how difficult it is to determine if a string belongs to a language or not. In particular, we investigate how interleaving can be introduced into models that capture the context-free languages.

HEDGE

Coordinate

唤起

Mutation Systemsutomaton simulation shows that in this framework, universal computation is possible and the question of whether one string can evolve into another is undecidable. We also analyze the efficiency of the finite state machine simulation assuming random point mutations.

adulterant

drusen

aphasia

A Simple and Efficient Universal Reversible Turing Machineersibilizing any existing universal machine. The interpretive overhead of the URTM is limited to a (program dependent) constant factor slowdown, with no other complexity-wise cost . time and space. The URTM is also able to function as an . for RTMs at no asymptotic cost, simply by reversing the string representing the interpreted machine.

运动的我

Unary Pattern Avoidance in Partial Words Dense with Holesles. We define the concept of hole sparsity, a measure of the frequency of holes in a partial word, and determine the minimum hole sparsity for all unary patterns in the context of trivial and non-trivial avoidability.

外面

Melodrama

The Complexity of Request-Response Gamesmes played on DAGs, and .-complete or .-complete if there is only one player (depending on whether he wants to enforce or spoil the request-response condition)..We also present near-optimal bounds on the memory needed to design winning strategies for each player, in each case.