Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435476 | Theoretical Computer Science | 2016 | 22 Pages |
Abstract
We give a method for specifying ultrafilter equations and identify their projections on the set of profinite words. Let BB 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 BB and then projecting these to obtain profinite equations characterising B∩RegB∩Reg. This suffices to establish the decidability of the membership problem for B∩RegB∩Reg.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mai Gehrke, Andreas Krebs, Jean-Éric Pin,