Accepting splicing systems with permitting and forbidding words

Abstract: In this paper we propose a generalization of the accepting splicingsystems introduced in Mitrana et al. (Theor Comput Sci 411:2414?2422,2010). More precisely, the input word is accepted as soon as a permittingword is obtained provided that no forbidding word has been obtained sofar, otherwise it is rejected. Note that in the new variant of acceptingsplicing system the input word is rejected if either no permitting word isever generated (like in Mitrana et al. in Theor Comput Sci 411:2414?2422,2010) or a forbidding word has been generated and no permitting wordhad been generated before. We investigate the computational power ofthe new variants of accepting splicing systems and the interrelationshipsamong them. We show that the new condition strictly increases thecomputational power of accepting splicing systems. Although there areregular languages that cannot be accepted by any of the splicing systemsconsidered here, the new variants can accept non-regular and even non-context-free languages, a situation that is not very common in the case of(extended) finite splicing systems without additional restrictions. We alsoshow that the smallest class of languages out of the four classes definedby accepting splicing systems is strictly included in the class of context-free languages. Solutions to a few decidability problems are immediatelyderived from the proof of this result.

Splicing Systems: Accepting Versus Generating.

In this paper we propose a condition for rejecting the input word by an accepting splicing system which is defined by a finite set of forbidding words. We investigate the computational power of the new variants of accepting splicing systems. We show that the new condition strictly increases the computational power of accepting splicing systems. Rather surprisingly, accepting splicing systems considered here can accept non-regular languages, a situation that has never occurred in the case of (extended) finite splicing systems without additional restrictions.

Rule Representation in Distributed Environments with Accepting Networks of Splicing Processors.

This paper presents the model named Accepting Networks of Evolutionary Processors as NP-problem solver inspired in the biological DNA operations. A processor has a rules set, splicing rules in this model,an object multiset and a filters set. Rules can be applied in parallel since there exists a large number of copies of objects in the multiset. Processors can form a graph in order to solve a given problem. This paper shows the network configuration in order to solve the SAT problem using linear resources and time. A rule representation arquitecture in distributed environments can be easily implemented using these networks of processors, such as decision support systems, as shown in the paper.

Photonic liquid crystal fiber intermodal interferometer

In this work, we present a novel interferometer based on liquid crystal and photonic crystal fiber technology. The objective of this project is the development of a tunable (switchable) modal (Mach-Zehnder) interferometer for optical communications or sensing. This interferometer has been manufactured splicing a short portion (between 15 and 30 mm) of photonic crystal fiber with two single mode fiber pigtails. The study shows a high sensitivity of the interferometer to the polarization of the launching light.

Modelo de computación conexionista inspirado en las redes de procesadores evolutivos y su aprendizaje

La informática teórica es una disciplina básica ya que la mayoría de los avances en informática se sustentan en un sólido resultado de esa materia. En los últimos a~nos debido tanto al incremento de la potencia de los ordenadores, como a la cercanía del límite físico en la miniaturización de los componentes electrónicos, resurge el interés por modelos formales de computación alternativos a la arquitectura clásica de von Neumann. Muchos de estos modelos se inspiran en la forma en la que la naturaleza resuelve eficientemente problemas muy complejos. La mayoría son computacionalmente completos e intrínsecamente paralelos. Por este motivo se les está llegando a considerar como nuevos paradigmas de computación (computación natural). Se dispone, por tanto, de un abanico de arquitecturas abstractas tan potentes como los computadores convencionales y, a veces, más eficientes: alguna de ellas mejora el rendimiento, al menos temporal, de problemas NPcompletos proporcionando costes no exponenciales. La representación formal de las redes de procesadores evolutivos requiere de construcciones, tanto independientes, como dependientes del contexto, dicho de otro modo, en general una representación formal completa de un NEP implica restricciones, tanto sintácticas, como semánticas, es decir, que muchas representaciones aparentemente (sintácticamente) correctas de casos particulares de estos dispositivos no tendrían sentido porque podrían no cumplir otras restricciones semánticas. La aplicación de evolución gramatical semántica a los NEPs pasa por la elección de un subconjunto de ellos entre los que buscar los que solucionen un problema concreto. En este trabajo se ha realizado un estudio sobre un modelo inspirado en la biología celular denominado redes de procesadores evolutivos [55, 53], esto es, redes cuyos nodos son procesadores muy simples capaces de realizar únicamente un tipo de mutación puntual (inserción, borrado o sustitución de un símbolo). Estos nodos están asociados con un filtro que está definido por alguna condición de contexto aleatorio o de pertenencia. Las redes están formadas a lo sumo de seis nodos y, teniendo los filtros definidos por una pertenencia a lenguajes regulares, son capaces de generar todos los lenguajes enumerables recursivos independientemente del grafo subyacente. Este resultado no es sorprendente ya que semejantes resultados han sido documentados en la literatura. Si se consideran redes con nodos y filtros definidos por contextos aleatorios {que parecen estar más cerca a las implementaciones biológicas{ entonces se pueden generar lenguajes más complejos como los lenguajes no independientes del contexto. Sin embargo, estos mecanismos tan simples son capaces de resolver problemas complejos en tiempo polinomial. Se ha presentado una solución lineal para un problema NP-completo, el problema de los 3-colores. Como primer aporte significativo se ha propuesto una nueva dinámica de las redes de procesadores evolutivos con un comportamiento no determinista y masivamente paralelo [55], y por tanto todo el trabajo de investigación en el área de la redes de procesadores se puede trasladar a las redes masivamente paralelas. Por ejemplo, las redes masivamente paralelas se pueden modificar de acuerdo a determinadas reglas para mover los filtros hacia las conexiones. Cada conexión se ve como un canal bidireccional de manera que los filtros de entrada y salida coinciden. A pesar de esto, estas redes son computacionalmente completas. Se pueden también implementar otro tipo de reglas para extender este modelo computacional. Se reemplazan las mutaciones puntuales asociadas a cada nodo por la operación de splicing. Este nuevo tipo de procesador se denomina procesador splicing. Este modelo computacional de Red de procesadores con splicing ANSP es semejante en cierto modo a los sistemas distribuidos en tubos de ensayo basados en splicing. Además, se ha definido un nuevo modelo [56] {Redes de procesadores evolutivos con filtros en las conexiones{ , en el cual los procesadores tan solo tienen reglas y los filtros se han trasladado a las conexiones. Dicho modelo es equivalente, bajo determinadas circunstancias, a las redes de procesadores evolutivos clásicas. Sin dichas restricciones el modelo propuesto es un superconjunto de los NEPs clásicos. La principal ventaja de mover los filtros a las conexiones radica en la simplicidad de la modelización. Otras aportaciones de este trabajo ha sido el dise~no de un simulador en Java [54, 52] para las redes de procesadores evolutivos propuestas en esta Tesis. Sobre el término "procesador evolutivo" empleado en esta Tesis, el proceso computacional descrito aquí no es exactamente un proceso evolutivo en el sentido Darwiniano. Pero las operaciones de reescritura que se han considerado pueden interpretarse como mutaciones y los procesos de filtrado se podrían ver como procesos de selección. Además, este trabajo no abarca la posible implementación biológica de estas redes, a pesar de ser de gran importancia. A lo largo de esta tesis se ha tomado como definición de la medida de complejidad para los ANSP, una que denotaremos como tama~no (considerando tama~no como el número de nodos del grafo subyacente). Se ha mostrado que cualquier lenguaje enumerable recursivo L puede ser aceptado por un ANSP en el cual el número de procesadores está linealmente acotado por la cardinalidad del alfabeto de la cinta de una máquina de Turing que reconoce dicho lenguaje L. Siguiendo el concepto de ANSP universales introducido por Manea [65], se ha demostrado que un ANSP con una estructura de grafo fija puede aceptar cualquier lenguaje enumerable recursivo. Un ANSP se puede considerar como un ente capaz de resolver problemas, además de tener otra propiedad relevante desde el punto de vista práctico: Se puede definir un ANSP universal como una subred, donde solo una cantidad limitada de parámetros es dependiente del lenguaje. La anterior característica se puede interpretar como un método para resolver cualquier problema NP en tiempo polinomial empleando un ANSP de tama~no constante, concretamente treinta y uno. Esto significa que la solución de cualquier problema NP es uniforme en el sentido de que la red, exceptuando la subred universal, se puede ver como un programa; adaptándolo a la instancia del problema a resolver, se escogerín los filtros y las reglas que no pertenecen a la subred universal. Un problema interesante desde nuestro punto de vista es el que hace referencia a como elegir el tama~no optimo de esta red.---ABSTRACT---This thesis deals with the recent research works in the area of Natural Computing {bio-inspired models{, more precisely Networks of Evolutionary Processors first developed by Victor Mitrana and they are based on P Systems whose father is Georghe Paun. In these models, they are a set of processors connected in an underlying undirected graph, such processors have an object multiset (strings) and a set of rules, named evolution rules, that transform objects inside processors[55, 53],. These objects can be sent/received using graph connections provided they accomplish constraints defined at input and output filters processors have. This symbolic model, non deterministic one (processors are not synchronized) and massive parallel one[55] (all rules can be applied in one computational step) has some important properties regarding solution of NP-problems in lineal time and of course, lineal resources. There are a great number of variants such as hybrid networks, splicing processors, etc. that provide the model a computational power equivalent to Turing machines. The origin of networks of evolutionary processors (NEP for short) is a basic architecture for parallel and distributed symbolic processing, related to the Connection Machine as well as the Logic Flow paradigm, which consists of several processors, each of them being placed in a node of a virtual complete graph, which are able to handle data associated with the respective node. All the nodes send simultaneously their data and the receiving nodes handle also simultaneously all the arriving messages, according to some strategies. In a series of papers one considers that each node may be viewed as a cell having genetic information encoded in DNA sequences which may evolve by local evolutionary events, that is point mutations. Each node is specialized just for one of these evolutionary operations. Furthermore, the data in each node is organized in the form of multisets of words (each word appears in an arbitrarily large number of copies), and all the copies are processed in parallel such that all the possible events that can take place do actually take place. Obviously, the computational process just described is not exactly an evolutionary process in the Darwinian sense. But the rewriting operations we have considered might be interpreted as mutations and the filtering process might be viewed as a selection process. Recombination is missing but it was asserted that evolutionary and functional relationships between genes can be captured by taking only local mutations into consideration. It is clear that filters associated with each node allow a strong control of the computation. Indeed, every node has an input and output filter; two nodes can exchange data if it passes the output filter of the sender and the input filter of the receiver. Moreover, if some data is sent out by some node and not able to enter any node, then it is lost. In this paper we simplify the ANSP model considered in by moving the filters from the nodes to the edges. Each edge is viewed as a two-way channel such that the input and output filters coincide. Clearly, the possibility of controlling the computation in such networks seems to be diminished. For instance, there is no possibility to loose data during the communication steps. In spite of this and of the fact that splicing is not a powerful operation (remember that splicing systems generates only regular languages) we prove here that these devices are computationally complete. As a consequence, we propose characterizations of two complexity classes, namely NP and PSPACE, in terms of accepting networks of restricted splicing processors with filtered connections. We proposed a uniform linear time solution to SAT based on ANSPFCs with linearly bounded resources. This solution should be understood correctly: we do not solve SAT in linear time and space. Since any word and auxiliary word appears in an arbitrarily large number of copies, one can generate in linear time, by parallelism and communication, an exponential number of words each of them having an exponential number of copies. However, this does not seem to be a major drawback since by PCR (Polymerase Chain Reaction) one can generate an exponential number of identical DNA molecules in a linear number of reactions. It is worth mentioning that the ANSPFC constructed above remains unchanged for any instance with the same number of variables. Therefore, the solution is uniform in the sense that the network, excepting the input and output nodes, may be viewed as a program according to the number of variables, we choose the filters, the splicing words and the rules, then we assign all possible values to the variables, and compute the formula.We proved that ANSP are computationally complete. Do the ANSPFC remain still computationally complete? If this is not the case, what other problems can be eficiently solved by these ANSPFCs? Moreover, the complexity class NP is exactly the class of all languages decided by ANSP in polynomial time. Can NP be characterized in a similar way with ANSPFCs?

Generating segmental foreign accent

For most of us, speaking in a non-native language involves deviating to some extent from native pronunciation norms. However, the detailed basis for foreign accent (FA) remains elusive, in part due to methodological challenges in isolating segmental from suprasegmental factors. The current study examines the role of segmental features in conveying FA through the use of a generative approach in which accent is localised to single consonantal segments. Three techniques are evaluated: the first requires a highly-proficiency bilingual to produce words with isolated accented segments; the second uses cross-splicing of context-dependent consonants from the non-native language into native words; the third employs hidden Markov model synthesis to blend voice models for both languages. Using English and Spanish as the native/non-native languages respectively, listener cohorts from both languages identified words and rated their degree of FA. All techniques were capable of generating accented words, but to differing degrees. Naturally-produced speech led to the strongest FA ratings and synthetic speech the weakest, which we interpret as the outcome of over-smoothing. Nevertheless, the flexibility offered by synthesising localised accent encourages further development of the method.

Selectively filled photonic liquid crystal fibers = Fibras de cristal fotónico selectivamente llenas con cristal líquido

El presente trabajo de Tesis se ha centrado en el diseño, fabricación y caracterización de dispositivos basados en fibras de cristal fotónico infiltrado selectivamente con cristales líquidos, polímeros y una mezcla de ambos. Todos los dispositivos son sintonizables, y su área de aplicación se centra en comunicaciones ópticas y sensores. La manipulación y fusionado de fibras fotónicas, el llenado selectivo de determinadas cavidades y la alineación recíproca de fibras mantenedoras de polarización son tareas muy específicas y delicadas para las que se requieren protocolos muy estrictos. Previo a la fabricación de dispositivos ha sido necesaria por tanto una tarea de sistematización y creación de protocolos de fabricación. Una vez establecidos se ha procedido a la fabricación y caracterización de dispositivos. Los dispositivos fabricados se enumeran a continuación para posteriormente detallar una a una las singularidades de cada uno. • Interferómetros intermodales hechos a partir de una porción de fibra fotónica soldada entre dos fibras estándar, bien monomodo o PANDA (mantenedora de polarización). Estos interferómetros han sido sumergidos o bien llenados selectivamente con cristales líquidos para así sintonizar la señal interferométrica guiada a través de la fibra. • Infiltración de fibras fotónicas con cristales líquidos colestéricos con especial énfasis en la fase azul (blue phase) de estos materiales. Las moléculas de cristal líquido se autoalinean en volumen por lo que la infiltración de fibras fotónicas con estos cristales líquidos es muy interesante, pues es conocida la dificultad de alinear apropiadamente cristales líquidos dentro de cavidades micrométricas de las fibras fotónicas. • Grabación de redes holográficas de forma selectiva en las cavidades de una fibra fotónica. Estas redes holográficas, llamadas POLICRYPS (POlymer-LIquid CRYstal-Polymer Slices), son redes fabricadas a base de franjas de polímero y cristal líquido alineado perpendicularmente a dichas franjas. Las franjas son a su vez perpendiculares al eje de la fibra como lo puede ser una red de Bragg convencional. El cristal líquido, al estar alineado perpendicularmente a dichos franjas y paralelo al eje de la fibra, se puede conmutar aplicando un campo eléctrico externo, modificando así el índice efectivo de la red. Se puede fabricar por lo tanto una red de Bragg sintonizable en fibra, muy útil en comunicaciones ópticas. • Llenado selectivo de fibras fotónicas con polidimetilsiloxano (PDMS), un polímero de tipo silicona. Si se realiza un llenado selectivo asimétrico se puede inducir birrefringencia en la fibra. El índice de refracción del PDMS tiene una fuerte dependencia térmica, por lo que se puede sintonizar la birrefringencia de la fibra. • Estudio teórico de llenado selectivo de fibras fotónicas con PDMS dopado con nanopartículas de plata de 5, 40 y 80 nm. Estas nanopartículas poseen un pico de absorción en torno a los 450 nm debido a resonancias superficiales localizadas de plasmones (LSPR). La resonancia del plasmon tiene una fuerte dependencia con el índice de refracción del material colindante, y al ser éste PDMS, la variación de índice de refracción se ve amplificada, obteniendo una absorción sintonizable. Se ha propuesto la fabricación de polarizadores sintonizables usando esta técnica. Como ya se ha dicho, previamente a la fabricación ha sido necesaria la protocolización de diversos procedimientos de fabricación de alta complejidad, así como protocolizar el proceso de toma de medidas para optimizar los resultados. Los procedimientos que han requerido la formulación de protocolos específicos han sido los siguientes: • Llenado selectivo de cavidades en una fibra fotónica. Dichas fibras tienen generalmente un diámetro externo de 125 μm, y sus cavidades son de entre 5 y 10 μm de diámetro. Se han desarrollado tres técnicas diferentes para el llenado/bloqueado selectivo, pudiéndose combinar varios protocolos para la optimización del proceso. Las técnicas son las siguientes: o Llenado y bloqueado con un prepolímero. Dicho prepolímero, también llamado adhesivo óptico, está inicialmente en estado líquido y posee una cierta viscosidad. Las cavidades de la fibra fotónica que se desea llenar o bloquear poseen un diámetro diferente al resto, por lo que en el proceso de llenado aparecen dos frentes de llenado dependientes de su diámetro. A mayor diámetro, mayor velocidad de llenado. Polimerizando cuando existe dicha diferencia en los frentes se puede cortar por medio, obteniendo así una fibra parcialmente bloqueada. o Colapsamiento de las cavidades de menor diámetro mediante aplicación de calor. El calor producido por un arco voltaico de una soldadora de fibra estándar fusiona el material exterior de la fibra produciendo el colapsamiento de las cavidades de menor diámetro. En esta técnica también es necesaria una diferencia de diámetros en las cavidades de la fibra. o Bloqueo una a una de las cavidades de la fibra fotónica con adhesivo óptico. Este procedimiento es muy laborioso y requiere mucha precisión. Con este sistema se pueden bloquear las cavidades deseadas de una fibra sin importar su diámetro. • Alineación de una fuente de luz linealmente polarizada con una fibra mantenedora de polarización ya sea PANDA o fotónica. Así mismo también se han alineado entre sí fibras mantenedoras de polarización, para que sus ejes rápidos se fusionen paralelos y así el estado de polarización de la luz guiada se mantenga. • Sistematización de toma de medidas para caracterizar los interferómetros modales. Éstos son altamente sensibles a diversas variables por lo que el proceso de medida es complejo. Se deben aislar variables de forma estrictamente controlada. Aunque todos los dispositivos tienen en común el llenado selectivo de cavidades en una fibra fotónica cada dispositivo tiene sus peculiaridades, que van a ser explicadas a continuación. ABSTRACT The present Thesis has been centered in the design, fabrication and characterization of devices based on photonic crystal fibers selectively filled with liquid crystals, polymers and a mixture of both. All devices are tunable and their work field is optical communications and sensing The handling and splicing of photonic crystal fibers, the selective filling of their holes and the aligning of polarization maintaining fibers are very specific and delicate tasks for which very strict protocols are required. Before the fabrication of devices has therefore been necessary task systematization and creation of manufacturing protocols. Once established we have proceeded to the fabrication and characterization of devices. The fabricated devices are listed below and their peculiarities are detailed one by one: • Intermodal interferometers made with a portion of photonic crystal fiber spliced between two optical communication fiber pigtails, either single mode or PANDA (polarization-maintaining) fiber. These interferometers have been submerged or selectively filled with liquid crystals to tune the interferometric guided signal. • Infiltration of photonic fibers with cholesteric liquid crystals with special emphasis on their blue phase (blue phase). The liquid crystal molecules are self-aligning in volume so the infiltration of photonic fibers with these liquid crystals is very interesting. It is notoriously difficult to properly align liquid crystals within micron cavities such as photonic fibers. • Selectively recording of holographic gratings in the holes of photonic crystal fibers. These holographic gratings, called POLICRYPS (POlymer-LIquid CRYstal-Polymes Slices), are based on walls made of polymer and liquid crystal aligned perpendicular to them. These walls are perpendicular to the axis of the fiber as it can be a conventional Bragg grating. The liquid crystal is aligned perpendicular to the walls and parallel to the fiber axis, and can be switched by applying an external electric field and thus change the effective index of the grating. It is thus possible to manufacture a tunable Bragg grating fiber, useful in optical communications. •Asymmetrically selective filling of photonic crystal fibers with a silicone polymer like called polydimethylsiloxane (PDMS) to induce birefringence in the fiber. The refractive index of PDMS has temperature dependence, so that the birefringence of the fiber can be tuned. • Theoretical study of photonic crystal fibers selectively filled with PDMS doped with silver nanoparticles of 5, 40 and 80 nm. These nanoparticles have an absorption peak around 450 nm due to localized surface plasmon resonances (LSPR). Plasmon resonance has a strong dependence on the refractive index of the adjacent material, and as this is PDMS, the refractive index variation is amplified, obtaining a tunable absorption. Fabrication of tunable polarizers using this technique has been proposed. Before starting the fabrication, it has been necessary to optimize several very delicate procedures and different protocols have been designed. The most delicate procedures are as follows: • Selective filling of holes in a photonic crystal fiber. These fibers generally have an outer diameter of 125 μm, and their holes have a diameter around between 5 and 10 μm. It has been developed three different techniques for filling / selective blocking, and they can be combined for process optimization. The techniques are: o Filling and blocked with a prepolymer. This prepolymer also called optical adhesive is initially in liquid state and has a certain viscosity. The holes of the photonic crystal fiber that are desired to be filled or blocked should have a different diameter, so that in the filling process appear two different fronts depending on the hole diameter. The holes with larger diameter are filled faster. Then the adhesive is polymerized when there is such a difference on the front. A partially blocked fiber is obtained cutting between fronts. o Collapsing of holes of smaller diameter by application of heat. The heat produced by an arc of a standard fusion splicer fuses the outer fiber material producing the collapsing of the cavities of smaller diameter. In this technique also you need a difference of diameters in the fiber holes. o Blocking one by one the holes of photonic crystal fiber with optical adhesive. This procedure is very laborious and requires great precision. This system can block unwanted cavities regardless fiber diameter. • Aligning a linearly polarized light source with a polarization-maintaining fiber (either a PANDA fiber as a photonic crystal fiber). It is needed also an aligning between polarization-maintaining fibers, so that their fast axes parallel merge and that is state of polarization of light guided is maintained. • Systematization of taking measurements to characterize the modal interferometers. These are highly sensitive to several variables so the measurement process is very complicated. Variables must be fixed in a very controlled manner. Although all devices have the common characteristic of being selectively filled PCFs with some kind of material, each one has his own peculiarities, which are explained below.