Name
Abstract | ||
|---|---|---|
We give a method for specifying ultrafilter equations and identify their projections on the set of profinite words. Let B be the set of languages captured by first-order sentences using unary predicates for each letter, arbitrary uniform unary numerical predicates and a predicate for the length of a word. We illustrate our methods by giving ultrafilter equations characterising B and then projecting these to obtain profinite equations characterising B∩Reg. This suffices to establish the decidability of the membership problem for B∩Reg. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1016/j.tcs.2015.08.007 | Theoretical Computer Science |
Keywords | Field | DocType |
Ultrafilters,Formal languages,Profinite equations,Regular languages,Stone duality | Discrete mathematics,Combinatorics,Formal language,Algebra,Unary operation,Ultrafilter,Decidability,Predicate (grammar),Regular language,Membership problem,Stone duality,Mathematics | Journal |
Volume | Issue | ISSN |
610 | PA | 0304-3975 |
Citations | PageRank | References |
3 | 0.38 | 7 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Mai Gehrke | 1 | 349 | 49.19 |
| Andreas Krebs | 2 | 21 | 8.20 |
| Jean-Éric Pin | 3 | 112 | 10.57 |