Skip to main content

Resultados relacionados

Resultados totales (Incluyendo duplicados): 3
Encontrada(s) 1 página(s)

RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Complexity-preserving simulations among three variants of accepting networks of evolutionary processors

  • Bottoni ., Paolo
  • Labella ., Anna
  • Manea ., Florin
  • Mitrana, Víctor
  • Petre ., Ion
  • Sempere Luna, José María|||0000-0003-2393-9224
In this paper we consider three variants of accepting networks of evolutionary processors. It is known that two of them are equivalent to Turing machines. We propose here a direct simulation of one device by the other. Each computational step in one model is simulated in a constant number of computational steps in the other one while a translation via Turing machines squares the time complexity. We also discuss the possibility of constructing simulations that preserve not only complexity, but also the shape of the simulated network. © 2011 Springer Science+Business Media B.V., This work was supported by the Academy of Finland, projects 132727, 122426, and 108421. F. Manea acknowledges the support from the Alexander von Humboldt Foundation. J Sempere acknowledges the support from the Spanish Ministerio de Educacion y Ciencia project TIN2007-60769.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

Upper set monoids and length preserving morphisms

  • Cano Gómez, Antonio
  • Pin, Jean-Eric
Length preserving morphisms and inverse of substitutions are two well-studied operations on regular languages. Their connection with varieties generated by power monoids was established independently by Reutenauer and Straubing in 1979. More recently, an ordered version of this theory was proposed by Polák and by the authors. In this paper, we present an improved version of these results and obtain the following consequences. Given a variety of finite ordered monoids V, let P ¿V be the variety of finite ordered monoids generated by the upper set monoids of members of V. Then P ¿(P ¿V)=P ¿V. This contrasts with the known results for the unordered case: the operator PV corresponding to power monoids satisfies P 3V=P 4V, but the varieties V, PV, P 2V and P 3V can be distinct. © 2011 Elsevier B.V., Work supported by the integrated action Picasso 19245ZC and by the AuthoMathA Programme of the European Science Foundation. The first author was supported by the project Tecnicas de Inferencia Gramatical y aplicacion al procesamiento de biosecuencias (TIN2007-60769) supported by the Spanish Ministry of Education and Sciences. The second author was supported by the project ANR 2010 BLAN 0202 02 FREC.
RiuNet. Repositorio Institucional de la Universitat Politécnica de Valéncia
Publication Artículo científico (JournalArticle)

From regular expressions to smaller NFAs

  • García Gómez, Pedro
  • Ruiz Ochando, José
  • Álvarez Vargas, Gloria Inés
  • López Rodríguez, Damián|||0000-0003-3633-3862
Several methods have been developed to construct -free automata that represent a regular expression. Among the most widely known are the position automaton (Glushkov), the partial derivatives automaton (Antimirov) and the follow automaton (Ilie and Yu). All these automata can be obtained with quadratic time complexity, thus, the comparison criterion is usually the size of the resulting automaton. The methods that obtain the smallest automata (although, for general expressions, they are not comparable), are the follow and the partial derivatives methods. In this paper, we propose another method to obtain a -free automaton from a regular expression. The number of states of the automata we obtain is bounded above by the size of both the partial derivatives automaton and of the follow automaton. Our algorithm also runs with the same time complexity of these methods. © 2011 Elsevier B.V. All rights reserved., This work was partially supported by the Spanish Ministerio de Educacion y Ciencia under project TIN2007-60769.