gzipped postscript
or
postscript
A technical report Parikh Automata and MSO Logics with Cardinalities contains complete technical developments and proofs. It also contains an extension of the decidability results to Parikh Tree Automata.
This work is based on the technical report ``WS1S with Cardinality Constraints'' which already contains the main insights but the more recent technical developments of these facts are smoother. It contains encodings of applications such as the Byzantine Generals Problem and shows up a relationship of these results to Petri Net reachability.
gzipped postscript
or
postscript
@inproceedings{KlaedtkeRuess:ICALP03,
TITLE = {Monadic Second-Order Logics with Cardinalities},
AUTHOR = {Felix Klaedtke and Harald Rue{\ss}},
EDITOR = {Jos C. M. Baeten and Jan Karel Lenstra and
Joachim Parrow and Gerhard J. Woeginger},
BOOKTITLE = {30th International Colloquium on Automata, Languages and Programming, ICALP 2003},
PUBLISHER = {Springer Verlag},
SERIES = {Lecture Notes in Computer Science},
VOLUME = {2719},
YEAR = {2003},
ISBN = {3-540-40493-7},
NOTES = {Eindhoven, The Netherlands, June 30 - July 4}
}
@TechReport{Klaedtke_Ruess.2002,
author = {F. Klaedtke and H. Rue{\ss}},
title = {Parikh Automata and Monadic Second-Order Logics with Linear Cardinality Constraints},
type = {Technical Report},
institution = {Albert-Ludwigs-Universit{\"a}t Freiburg},
month = {July},
year = {2002},
number = {177},
note = {(revised version)},
}
@techreport{Klaedtke_Ruess.2001,
AUTHOR = {F. Klaedtke and H. Rue{\ss}},
TITLE = {{WS1S} with Cardinality Constraints},
type = {Technical Report},
INSTITUTION = {SRI International},
NUMBER = {SRI-CSL-05-01},
YEAR = {2001},
}