dc.creator | Paun, Gheorghe | es |
dc.creator | Pérez Jiménez, Mario de Jesús | es |
dc.date.accessioned | 2018-10-30T10:45:03Z | |
dc.date.available | 2018-10-30T10:45:03Z | |
dc.date.issued | 2012 | |
dc.identifier.citation | Paun, G. y Pérez Jiménez, M.d.J. (2012). P automata revisited. Theoretical Computer Science, 454 (octubre 2012), 222-230. | |
dc.identifier.issn | 0304-3975 | es |
dc.identifier.uri | https://hdl.handle.net/11441/79705 | |
dc.description.abstract | We continue here the investigation of P automata, in their non-extended case, a class of
devices which characterize non-universal family of languages. First, a recent conjecture is
confirmed: any recursively enumerable language is obtained from a language recognized
by a P automaton, to which an initial (arbitrarily large) string is added. Then, we discuss
possibilities of extending P automata, following suggestions from string finite automata.
For instance, automata with a memory (corresponding to push-down automata) are
considered and their power is briefly investigated, as well as some closure properties of
the family of languages recognized by P automata. In the context, a brief survey of results
about P and dP automata (a distributed version of P automata) is provided, and several
further research topics are formulated. | es |
dc.description.sponsorship | Junta de Andalucía P08-TIC-04200 | es |
dc.format | application/pdf | es |
dc.language.iso | eng | es |
dc.publisher | Elsevier | es |
dc.relation.ispartof | Theoretical Computer Science, 454 (octubre 2012), 222-230. | |
dc.rights | Attribution-NonCommercial-NoDerivatives 4.0 Internacional | * |
dc.rights.uri | http://creativecommons.org/licenses/by-nc-nd/4.0/ | * |
dc.subject | Membrane Computing | es |
dc.subject | P Automata | es |
dc.subject | Turing computability | es |
dc.subject | Closure properties | es |
dc.title | P automata revisited | es |
dc.type | info:eu-repo/semantics/article | es |
dcterms.identifier | https://ror.org/03yxnpp24 | |
dc.type.version | info:eu-repo/semantics/submittedVersion | es |
dc.rights.accessRights | info:eu-repo/semantics/openAccess | es |
dc.contributor.affiliation | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial | es |
dc.relation.projectID | P08-TIC-04200 | es |
dc.relation.publisherversion | https://www.sciencedirect.com/science/article/pii/S0304397512000837?via%3Dihub | es |
dc.identifier.doi | 10.1016/j.tcs.2012.01.036 | es |
dc.contributor.group | Universidad de Sevilla. TIC193: Computación Natural | es |
idus.format.extent | 9 | es |
dc.journaltitle | Theoretical Computer Science | es |
dc.publication.volumen | 454 | es |
dc.publication.issue | octubre 2012 | es |
dc.publication.initialPage | 222 | es |
dc.publication.endPage | 230 | es |
dc.identifier.sisius | 20270192 | es |
dc.contributor.funder | Junta de Andalucía | |