Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
http://dx.doi.org/10.18419/opus-2557
Autor(en): | Kuske, Dietrich Lohrey, Markus |
Titel: | First order and counting theories of omega-automatic structures |
Erscheinungsdatum: | 2005 |
Dokumentart: | Arbeitspapier |
Serie/Report Nr.: | Technischer Bericht / Universität Stuttgart, Fakultät Informatik, Elektrotechnik und Informationstechnik;2005,7 |
URI: | http://nbn-resolving.de/urn:nbn:de:bsz:93-opus-24282 http://elib.uni-stuttgart.de/handle/11682/2574 http://dx.doi.org/10.18419/opus-2557 |
Zusammenfassung: | The logic L(Q_u) extends first-order logic by a generalized form of counting quantifiers ("the number of elements satisfying ... belongs to the set C"). This logic is investigated for structures with an injective omega-automatic presentation. If first-order logic is extended by an infinity-quantifier, the resulting theory of any such structure is known to be decidable (Blumensath, Grädel 2004). It is shown that, as in the case of automatic structures (Khoussainov, Rubin, Stephan 2004) also modulo-counting quantifiers as well as infinite cardinality quantifiers ("there are c many elements satisfying ...") lead to decidable theories. For a structure of bounded degree with injective omega-automatic presentation, the fragment of L(Q_u) that contains only effective quantifiers is shown to be decidable and an elementary algorithm for this decision is presented. Both assumptions (omega-automaticity and bounded degree) are necessary for this result to hold. |
Enthalten in den Sammlungen: | 05 Fakultät Informatik, Elektrotechnik und Informationstechnik |
Dateien zu dieser Ressource:
Datei | Beschreibung | Größe | Format | |
---|---|---|---|---|
TR_2005_07.pdf | 258,88 kB | Adobe PDF | Öffnen/Anzeigen |
Alle Ressourcen in diesem Repositorium sind urheberrechtlich geschützt.