On the size of shortest modal descriptions

We address the problems of separation and description in some fragments of modal logics. The former consists in finding a formula that is true in some given subset of the domain and false in another. The latter is a special case when one separates a singleton from the rest. We are interested in the...

Descripción completa

Guardado en:

Detalles Bibliográficos
Autores principales:	Figueira, Santiago Daniel, Gorín, Daniel Alejandro
Publicado:	2010
Materias:	Ehrenfeucht-Fraïssé Lower bound Modal logic Referring expression Shortest formula size Succinctness Formula size Lower bounds Computational linguistics Separation Formal logic
Acceso en línea:	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira http://hdl.handle.net/20.500.12110/paper_19049872_v8_n_p120_Figueira
Aporte de:	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires

id	paper:paper_19049872_v8_n_p120_Figueira
record_format	dspace
spelling	paper:paper_19049872_v8_n_p120_Figueira2023-06-08T16:30:21Z On the size of shortest modal descriptions Figueira, Santiago Daniel Gorín, Daniel Alejandro Ehrenfeucht-Fraïssé Lower bound Modal logic Referring expression Shortest formula size Succinctness Formula size Lower bounds Modal logic Referring expression Succinctness Computational linguistics Separation Formal logic We address the problems of separation and description in some fragments of modal logics. The former consists in finding a formula that is true in some given subset of the domain and false in another. The latter is a special case when one separates a singleton from the rest. We are interested in the shortest size of both separations and descriptions. This is motivated by applications in computational linguistics. Lower bounds are given by considering the minimum size of Spoiler's strategies in the classical Ehrenfeucht-Fraïssé game. This allows us to show that the size of such formulas is not polynomially bounded (with respect to the size of the finite input model). Upper bounds for these problems are also studied. Finally we give a fine hierarchy of succinctness for separation over the studied logics. Fil:Figueira, S. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. Fil:Gorín, D. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2010 https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira http://hdl.handle.net/20.500.12110/paper_19049872_v8_n_p120_Figueira
institution	Universidad de Buenos Aires
institution_str	I-28
repository_str	R-134
collection	Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
topic	Ehrenfeucht-Fraïssé Lower bound Modal logic Referring expression Shortest formula size Succinctness Formula size Lower bounds Modal logic Referring expression Succinctness Computational linguistics Separation Formal logic
spellingShingle	Ehrenfeucht-Fraïssé Lower bound Modal logic Referring expression Shortest formula size Succinctness Formula size Lower bounds Modal logic Referring expression Succinctness Computational linguistics Separation Formal logic Figueira, Santiago Daniel Gorín, Daniel Alejandro On the size of shortest modal descriptions
topic_facet	Ehrenfeucht-Fraïssé Lower bound Modal logic Referring expression Shortest formula size Succinctness Formula size Lower bounds Modal logic Referring expression Succinctness Computational linguistics Separation Formal logic
description	We address the problems of separation and description in some fragments of modal logics. The former consists in finding a formula that is true in some given subset of the domain and false in another. The latter is a special case when one separates a singleton from the rest. We are interested in the shortest size of both separations and descriptions. This is motivated by applications in computational linguistics. Lower bounds are given by considering the minimum size of Spoiler's strategies in the classical Ehrenfeucht-Fraïssé game. This allows us to show that the size of such formulas is not polynomially bounded (with respect to the size of the finite input model). Upper bounds for these problems are also studied. Finally we give a fine hierarchy of succinctness for separation over the studied logics.
author	Figueira, Santiago Daniel Gorín, Daniel Alejandro
author_facet	Figueira, Santiago Daniel Gorín, Daniel Alejandro
author_sort	Figueira, Santiago Daniel
title	On the size of shortest modal descriptions
title_short	On the size of shortest modal descriptions
title_full	On the size of shortest modal descriptions
title_fullStr	On the size of shortest modal descriptions
title_full_unstemmed	On the size of shortest modal descriptions
title_sort	on the size of shortest modal descriptions
publishDate	2010
url	https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira http://hdl.handle.net/20.500.12110/paper_19049872_v8_n_p120_Figueira
work_keys_str_mv	AT figueirasantiagodaniel onthesizeofshortestmodaldescriptions AT gorindanielalejandro onthesizeofshortestmodaldescriptions
_version_	1768544154130841600

On the size of shortest modal descriptions

Ejemplares similares