[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Ultrafilters on words for a fragment of logic

Published: 11 January 2016 Publication History

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 .

References

[1]
J. Almeida, Residually finite congruences and quasi-regular subsets in uniform algebras, Port. Math., 46 (1989) 313-328.
[2]
J. Almeida, Finite Semigroups and Universal Algebra, World Scientific Publishing Co. Inc., River Edge, NJ, 1994.
[3]
D.A.M. Barrington, H. Straubing, D. Thérien, Non-uniform automata over groups, Inform. and Comput., 89 (1990) 109-132.
[4]
M. Gehrke, S. Grigorieff, J.-E. Pin, Duality and equational theory of regular languages, in: Lect. Notes Comp. Sci., vol. 5126, Springer, Berlin, 2008, pp. 246-257.
[5]
M. Gehrke, S. Grigorieff, J.-E. Pin, A topological approach to recognition, in: Lect. Notes Comp. Sci., vol. 6199, Springer, Berlin, 2010, pp. 151-162.
[6]
M. Gehrke, A. Krebs, J.-É. Pin, From ultrafilters on words to the expressive power of a fragment of logic, in: Lect. Notes Comp. Sci., vol. 8614, Springer, Berlin, 2014, pp. 138-149.
[7]
P. McKenzie, M. Thomas, H. Vollmer, Extensional uniformity for Boolean circuits, SIAM J. Comput., 39 (2010) 3186-3206.
[8]
J.-É. Pin, Profinite methods in automata theory, in: 26th International Symposium on Theoretical Aspects of Computer Science, Internationales Begegnungs- und Forschungszentrum für Informatik (IBFI), Schloss Dagstuhl, Germany, 2009, pp. 31-50.
[9]
J.-É. Pin, Equational descriptions of languages, Internat. J. Found. Comput. Sci., 23 (2012) 1227-1240.
[10]
H. Straubing, Constant-depth periodic circuits, Internat. J. Algebra Comput., 1 (1991) 49-87.
[11]
H. Straubing, Finite Automata, Formal Logic, and Circuit Complexity, Birkhäuser Boston Inc., Boston, MA, 1994.
[12]
H. Straubing, On logical descriptions of regular languages, in: Lect. Notes Comp. Sci., vol. 2286, Springer, 2002, pp. 528-538.

Cited By

View all
  • (2017)Monadic Second-Order Logic with Arbitrary Monadic PredicatesACM Transactions on Computational Logic10.1145/309112418:3(1-17)Online publication date: 18-Aug-2017
  • (2017)Stone duality for languages and complexityACM SIGLOG News10.1145/3090064.30900684:2(29-53)Online publication date: 3-May-2017
  • (2016)Duality in Computer ScienceProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2934575(12-26)Online publication date: 5-Jul-2016

Recommendations

Reviews

Wolfgang Schreiner

The modern theory of formal languages has progressed far beyond concepts such as regular expressions that the typical computer scientist is familiar with. One approach to language theory is based on the mathematical framework of profinite topologies; profinite words can be considered as limits of sequences of finite words, which converge according to a metric that denotes the size of the automaton needed to distinguish between two words. The present paper investigates the logical description of profinite languages by a first-order logic with numerical predicates that constrain the length of a word and the symbols in it; for example, the sentence "exists x . a ( x )" with unary predicate " a " is true for every word in which the symbol " a " occurs at some position. In particular, the authors investigate in which cases languages can be also characterized in a simpler form, namely by "ultrafilter equations" where an ultrafilter denotes a profinite language and a language satisfies an equation if it is denoted by both ultrafilters in the equation or by none. They show that every regular language that can be described by the first-order logic can be also described by a simple class of ultrafilter equations; this also gives rise to a new proof of decidability of the problem of whether a language is both regular and a Boolean algebra. While the paper contains interesting results, its target readers are experts in the field. For a general motivation or examples, the reader should consult more accessible introductions to the profinite approach to language theory first. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Theoretical Computer Science
Theoretical Computer Science  Volume 610, Issue PA
January 2016
139 pages

Publisher

Elsevier Science Publishers Ltd.

United Kingdom

Publication History

Published: 11 January 2016

Author Tags

  1. Formal languages
  2. Profinite equations
  3. Regular languages
  4. Stone duality
  5. Ultrafilters

Qualifiers

  • Research-article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 11 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2017)Monadic Second-Order Logic with Arbitrary Monadic PredicatesACM Transactions on Computational Logic10.1145/309112418:3(1-17)Online publication date: 18-Aug-2017
  • (2017)Stone duality for languages and complexityACM SIGLOG News10.1145/3090064.30900684:2(29-53)Online publication date: 3-May-2017
  • (2016)Duality in Computer ScienceProceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science10.1145/2933575.2934575(12-26)Online publication date: 5-Jul-2016

View Options

View options

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media