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, S., Gorín, D.
Formato:	CONF
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:	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	todo:paper_19049872_v8_n_p120_Figueira
record_format	dspace
spelling	todo:paper_19049872_v8_n_p120_Figueira2023-10-03T16:34:26Z On the size of shortest modal descriptions Figueira, S. Gorín, D. 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. CONF info:eu-repo/semantics/openAccess http://creativecommons.org/licenses/by/2.5/ar 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, S. Gorín, D. 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.
format	CONF
author	Figueira, S. Gorín, D.
author_facet	Figueira, S. Gorín, D.
author_sort	Figueira, S.
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
url	http://hdl.handle.net/20.500.12110/paper_19049872_v8_n_p120_Figueira
work_keys_str_mv	AT figueiras onthesizeofshortestmodaldescriptions AT gorind onthesizeofshortestmodaldescriptions
_version_	1807323787319836672

On the size of shortest modal descriptions

Ejemplares similares