Abstract:
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.
Registro:
| Documento: |
Conferencia
|
| Título: | On the size of shortest modal descriptions |
| Autor: | Figueira, S.; Gorín, D. |
| Ciudad: | Moscow |
| Filiación: | Departamento de Computacifion, FCEyN, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria (C1428EGA), Buenos Aires, Argentina
|
| Palabras clave: | 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 |
| Año: | 2010
|
| Volumen: | 8
|
| Página de inicio: | 120
|
| Página de fin: | 139
|
| Título revista: | 8th International Conference on Advances in Modal Logic, AiML-2010
|
| Título revista abreviado: | Adv. Modal Logic
|
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira |
Referencias:
- Adler, M., Immerman, N., An n! lower bound on formula size (2003) ACM Trans. Comput. Logic, 4, pp. 296-314
- Areces, C., Figueira, S., Gorín, D., The question of expressiveness in the generation of referring expressions (2010) Technical Report, University of Buenos Aires, , http://arxiv.org/abs/1006.4621v1
- Areces, C., Koller, A., Striegnitz, K., Referring expressions as formulas of description logic (2008) Proc. of the 5th INLG, pp. 42-49. , Salt Fork, OH, USA
- Blackburn, P., De Rijke, M., Venema, Y., (2001) Modal Logic, , Cambridge University Press
- Blackburn, P., Van Benthem, J., Wolter, F., (2006) Handbook of Modal Logic Volume 3 (Studies in Logic and Practical Reasoning), , Elsevier Science Inc., New York, NY, USA
- Dale, R., Cooking up referring expressions (1989) Proc. of the 27th ACL, pp. 68-75
- Dale, R., Haddock, N., Generating referring expressions involving relations (1991) Proc. of the 5th EACL, pp. 161-166
- Dale, R., Reiter, E., Computational interpretations of the Gricean maxims in the generation of referring expressions (1995) Cognitive Science, 19
- Dawar, A., Grohe, M., Kreutzer, S., Schweikardt, N., Model theory makes formulas large (2007) Proceedings of the 34th International Colloquium on Automata, Languages and Programming
- Hennessy, M., Milner, R., Algebraic laws for indeterminism and concurrency (1985) Journal of the ACM, 32, pp. 137-162
- Hopcroft, J., An nlog(n) algorithm for minimizing states in a finite automaton (1971) Theory of Machines and Computations, , Z. Kohave, editor. Academic Press
- Kanellakis, P., Smolka, S., CCS expressions finite state processes and three problems of equivalence (1990) Inf. Comput., 86, pp. 43-68
- Li, M., Vitányi, P., (1997) An Introduction to Kolmogorov Complexity and Its Applications, , Springer, 2nd edition
- Markey, N., Temporal logic with past is exponentially more succinct (2003) Bulletin of the EATCS 79, pp. 122-128
- Paige, R., Tarjan, R., Three partition refinement algorithms (1987) SIAM J. Comput., 16, pp. 973-989
- Stone, M., On identifying sets (2000) Proc. of the 1st INLG, pp. 116-123
- Van Deemter, K., Generating referring expressions: Boolean extensions of the incremental algorithm (2002) Computational Linguistics, 28, pp. 37-52
- Wilke, T., CTL + is exponentially more succinct than CTL (1999) FSTTCS, pp. 110-121A4 - Laboratoire J.-V.Poncelet; Russian Academy of Sciences, Steklov Mathematical Institute; MUHMO; Reseau Form. Rech. Franco-Russe Sci. Technol. Inf. Commun.; Fondation l'Enterprise - EADS
Citas:
---------- APA ----------
Figueira, S. & Gorín, D.
(2010)
. On the size of shortest modal descriptions. 8th International Conference on Advances in Modal Logic, AiML-2010, 8, 120-139.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira [ ]
---------- CHICAGO ----------
Figueira, S., Gorín, D.
"On the size of shortest modal descriptions"
. 8th International Conference on Advances in Modal Logic, AiML-2010 8
(2010) : 120-139.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira [ ]
---------- MLA ----------
Figueira, S., Gorín, D.
"On the size of shortest modal descriptions"
. 8th International Conference on Advances in Modal Logic, AiML-2010, vol. 8, 2010, pp. 120-139.
Recuperado de https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira [ ]
---------- VANCOUVER ----------
Figueira, S., Gorín, D. On the size of shortest modal descriptions. Adv. Modal Logic. 2010;8:120-139.
Available from: https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_19049872_v8_n_p120_Figueira [ ]
