Operator Precedence Grammars (OPGs) define a deterministic class of context-free languages, which extend input-driven languages and still enjoy many properties: they are closed w.r.t. Boolean operations, concatenation and Kleene star; the emptiness problem is decidable; they are recognized by a suitable model of pushdown automaton; they can be characterized in terms of a monadic second-order logic. Also, they admit efficient parallel parsing. In this paper we introduce a subclass of OPGs, namely Free Grammars (FrGs); we prove some of its basic properties, and that, for each such grammar G, a first-order logic formula ψ can effectively be built so that L(G) is the set of all and only strings satisfying ψ. FrGs were originally introduced for grammatical inference of programming languages. Our result can naturally boost their applicability; to this end, a tool is made freely available for the semiautomatic construction of FrGs.

First-order logic definability of free languages / V. Lonati, D. Mandrioli, F. Panella, M. Pradella (LECTURE NOTES IN COMPUTER SCIENCE). - In: Computer Science : Theory and Applications / [a cura di] L.D. Beklemishev, D.V. Musatov. - [s.l] : Springer Verlag, 2015. - ISBN 9783319202969. - pp. 310-324 (( Intervento presentato al 10. convegno CSR tenutosi a Listvyanka nel 2015 [10.1007/978-3-319-20297-6_20].

First-order logic definability of free languages

V. Lonati;
2015

Abstract

Operator Precedence Grammars (OPGs) define a deterministic class of context-free languages, which extend input-driven languages and still enjoy many properties: they are closed w.r.t. Boolean operations, concatenation and Kleene star; the emptiness problem is decidable; they are recognized by a suitable model of pushdown automaton; they can be characterized in terms of a monadic second-order logic. Also, they admit efficient parallel parsing. In this paper we introduce a subclass of OPGs, namely Free Grammars (FrGs); we prove some of its basic properties, and that, for each such grammar G, a first-order logic formula ψ can effectively be built so that L(G) is the set of all and only strings satisfying ψ. FrGs were originally introduced for grammatical inference of programming languages. Our result can naturally boost their applicability; to this end, a tool is made freely available for the semiautomatic construction of FrGs.
formal languages and automata; operator precedence grammars, first order logic
Settore INF/01 - Informatica
European Association for
National Research University Higher School of Economics
Russian Foundation for Basic Research
Steklov Mathematical Institute of Russian Academy of Sciences
Theoretical Computer Science (EATCS)
Yandex
Book Part (author)
File in questo prodotto:
File Dimensione Formato  
chp%3A10.1007%2F978-3-319-20297-6_20.pdf

non disponibili

Tipologia: Publisher's version/PDF
Dimensione 535.41 kB
Formato Adobe PDF
535.41 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/352807
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 3
  • ???jsp.display-item.citation.isi??? ND
social impact