For the most recent entries see the Petri Nets Newsletter.

A descriptive complexity approach to the linear hierarchy.

Hacha´chi, Yassine

In: Theoretical Computer Science, Volume 304, Issues 1-3 , 28 July 2003, pages 421-429. Elsevier, July 2003.

Abstract: This paper gives some new logical characterizations of the class of rudimentary languages in the scope of descriptive complexity. These characterizations are based on a logic introduced by Parigot and Pelz to characterize Petri Net languages, and generalized quantifiers of comparison of cardinality.

Keywords: Rudimentary languages; Linear hierarchy; Descriptive complexity; Monadic second-order logic; Generalized quantifiers.


Do you need a refined search? Try our search engine which allows complex field-based queries.

Back to the Petri Nets Bibliography