Logic characterization of invisibly structured languages : the case of Floyd languages
Contributo in Atti di convegno
Data di Pubblicazione:
2013
Citazione:
Logic characterization of invisibly structured languages : the case of Floyd languages / V. Lonati, D. Mandrioli, M. Pradella - In: SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science : Špindlerův Mlýn, Czech Republic, january 26-31, 2013 : proceedings / [a cura di] P. van Emde Boas, F.C.A. Groen, G.F. Italiano,
J. Nawrocki, H. Sack,. - Berlin : Springer, 2013. - ISBN 9783642358425. - pp. 307-318 (( Intervento presentato al 39. convegno International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM) tenutosi a Špindlerův Mlýn, Czech Republic nel 2013 [10.1007/978-3-642-35843-2_27].
Abstract:
Operator precedence grammars define a classical Boolean and deterministic context-free language family (called Floyd languages or FLs). FLs have been shown to strictly include the well-known Visibly Pushdown Languages, and enjoy the same nice closure properties. In this paper we provide a complete characterization of FLs in terms of a suitable Monadic Second-Order Logic. Tradi- tional approaches to logic characterization of formal languages refer explicitly to the structures over which they are interpreted - e.g, trees or graphs - or to strings that are isomorphic to the structure, as in parenthesis languages. In the case of FLs, instead, the syntactic structure of input strings is “invisible” and must be reconstructed through parsing. This requires that logic formulae encode some typical context-free parsing actions, such as shift-reduce ones.
Tipologia IRIS:
03 - Contributo in volume
Keywords:
deterministic context-free languages; monadic second-order logic; operator precedence languages; pushdown automata
Elenco autori:
V. Lonati, D. Mandrioli, M. Pradella
Link alla scheda completa:
Titolo del libro:
SOFSEM 2013 : theory and practice of computer science : 39th international conference on current trends in theory and practice of computer science : Špindlerův Mlýn, Czech Republic, january 26-31, 2013 : proceedings