Name
Abstract | ||
|---|---|---|
It is proved that if definability of regular languages in the Sigma(n) fragment of the first-order logic on finite words is decidable, then it is decidable also for the Delta(n+1) fragment. In particular, the decidability for Delta(5) is obtained. More generally, for every concatenation hierarchy of regular languages, it is proved that decidability of one of its half levels implies decidability of the intersection of the following half level with its complement. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1007/978-3-319-21500-6_4 | DEVELOPMENTS IN LANGUAGE THEORY (DLT 2015) |
Field | DocType | Volume |
Discrete mathematics,Combinatorics,Binary relation,Decidability,Concatenation,Sigma,Regular language,Membership problem,Transitive closure,Hierarchy,Mathematics | Conference | 9168 |
ISSN | Citations | PageRank |
0302-9743 | 9 | 0.82 |
References | Authors | |
7 | 4 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| J. Almeida | 1 | 61 | 15.24 |
| Jana Bartonová | 2 | 9 | 0.82 |
| Ondrej Klíma | 3 | 39 | 9.16 |
| Michal Kunc | 4 | 138 | 12.83 |