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.
Back to the Petri Nets Bibliography