Title :
Some results on majority quantifiers over words
Author :
Lange, Klaus-Jörn
Author_Institution :
Wiolhelm-Schickard-Inst. fur Informatik, Eberhard-Karls-Univ., Tubingen, Germany
Abstract :
The class of languages definable by majority quantifiers using the order predicate is investigated. It is shown that the additional use of first order or counting quantifiers does not increase this class. Further on, addition is in this connection a definable numerical predicate, while the converse does not hold. The emptiness problem for this class turns out to be undecidable.
Keywords :
decidability; formal languages; counting quantifiers; emptiness problem; first order quantifiers; language classes; majority quantifiers; numerical predicate; order predicate; undecidability; Books; Computational complexity; Logic;
Conference_Titel :
Computational Complexity, 2004. Proceedings. 19th IEEE Annual Conference on
Print_ISBN :
0-7695-2120-7
DOI :
10.1109/CCC.2004.1313817
