Capturing relational NEXPTIME with a fragment of existential third order logic

Buscar material

Busque entre los 156185 recursos disponibles en el repositorio

Suba sus trabajos a SEDICI, para mejorar notoriamente su visibilidad e impacto

dc.date.accessioned	2015-12-14T12:41:27Z
dc.date.available	2015-12-14T12:41:27Z
dc.date.issued	2015-11
dc.identifier.uri	http://sedici.unlp.edu.ar/handle/10915/50177
dc.description.abstract	We prove that the existential fragment Σ₁^2,ω of the third order logic TO^ω captures the relational complexity class non deterministic exponential time. As a Corollary we have that relational machines that work in NEXPTIME_r can simulate third order relational machines that work in NEXPTIME_3,r.	es
dc.format.extent	87-92	es
dc.language	en	es
dc.subject	relational complexity	en
dc.subject	third order logic	en
dc.subject	expressibility of logics	en
dc.subject	relational machines	en
dc.subject	fixed point quantifiers	en
dc.title	Capturing relational NEXPTIME with a fragment of existential third order logic	en
dc.type	Articulo	es
sedici.identifier.uri	http://journal.info.unlp.edu.ar/wp-content/uploads/JCST41-Paper-7.pdf	es
sedici.identifier.issn	1666-6038	es
sedici.creator.person	Turull Torres, José María	es
sedici.subject.materias	Ciencias Informáticas	es
sedici.description.fulltext	true	es
mods.originInfo.place	Facultad de Informática	es
sedici.subtype	Articulo	es
sedici.rights.license	Creative Commons Attribution 3.0 Unported (CC BY 3.0)
sedici.rights.uri	http://creativecommons.org/licenses/by/3.0/
sedici.description.peerReview	peer-review	es
sedici.relation.journalTitle	Journal of Computer Science & Technology	es
sedici.relation.journalVolumeAndIssue	vol. 15, no. 2	es

Enlace externo

Excepto donde se diga explícitamente, este item se publica bajo la siguiente licencia Creative Commons Attribution 3.0 Unported (CC BY 3.0)