Name
Abstract | ||
|---|---|---|
In this paper we consider the class of all regular languages definable by the extended majority quantifier and the order predicate but using only two variables. The main part of the paper is the presentation of a geometric method which is used to show that a given regular language cannot be defined by such formulas. Applying this method we can give a necessary condition in terms of an equation as well as an upper and a lower bound for the corresponding class of monoids. As a consequence we obtain that FO + MAJ2[ 2[ |
Year | DOI | Venue |
|---|---|---|
2009 | 10.1007/978-3-642-02737-6_7 | Developments in Language Theory |
Keywords | Field | DocType |
order predicate,extended majority quantifier,regular languages definable,necessary condition,corresponding class,geometric method,majority quantifiers,main part,regular language,lower bound | Generalized star height problem,Discrete mathematics,Combinatorics,Geometric method,Upper and lower bounds,Monoid,Regular language,Pumping lemma for regular languages,Predicate (grammar),Mathematics | Conference |
Volume | ISSN | Citations |
5583 | 0302-9743 | 3 |
PageRank | References | Authors |
0.44 | 6 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christoph Behle | 1 | 23 | 4.14 |
| Andreas Krebs | 2 | 27 | 5.83 |
| Stephanie Reifferscheid | 3 | 17 | 2.27 |