More Web Proxy on the site http://driver.im/

research-article

Stone duality for languages and complexity

Authors:

Andreas KrebsAuthors Info & Claims

ACM SIGLOG News, Volume 4, Issue 2

Pages 29 - 53

https://doi.org/10.1145/3090064.3090068

Published: 03 May 2017 Publication History

Abstract

Complexity theory and the theory of regular languages both belong to the branch of computer science where the use of resources in computing is the main focus. However, they operate at different levels. While complexity theory seeks to classify computational problems by resource use, such as space and time, regular language theory remains at the very base of this hierarchy and is concerned with classes of computational problems for which membership is (potentially) decidable.

References

[1]

Samson Abramsky. 1991. Domain theory in logical form. Annals of Pure and Applied Logic 51, (1--2) (1991), 1--77.

[2]

Jorge Almeida. 2005. Profinite semigroups and applications. In Structural theory of automata, semigroups, and universal algebra. Springer, 1--45.

[3]

Jorge Almeida and Pascal Weil. 1995. Free profinite semigroups over semidirect products. Izvestiya VUZ Matematika 39, 1--3 (1995), 3--31. English version, Russian Mathem. (Iz. VUZ.) 39 (1995) 1--28.

[4]

Jorge Almeida and Pascal Weil. 1998. Profinite categories and semidirect products. J. Pure Appl. Algebra 123, 1--3 (1998), 1--50.

[5]

David A. Mix Barrington, Kevin Compton, Howard Straubing, and Denis Thérien. 1992. Regular languages in NC¹. J. Comput. System Sci. 44, 3 (1992), 478--499.

Digital Library

[6]

Christoph Behle, Andreas Krebs, and Mark Mercer. 2013. Linear circuits, two-variable logic and weakly blocked monoids. Theor. Comput. Sci. 501 (2013), 20--33.

Digital Library

[7]

Christoph Behle, Andreas Krebs, and Stephanie Reifferscheid. 2011. Typed Monoids - An Eilenberg-Like Theorem for Non Regular Languages. In Algebraic Informatics - 4th International Conference, CAI 2011, Linz, Austria, June 21--24, 2011. Proceedings. Springer, 97--114.

Digital Library

[8]

Christoph Behle and Klaus-Jrn Lange. 2006. FO{¡}-Uniformity. In 21st Annual IEEE Conference on Computational Complexity (CCC 2006). IEEE Computer Society, 183--189.

Digital Library

[9]

Guram Bezhanishvili (Ed.). 2014. Leo Esakia on duality in modal and intuitionistic logic. Outstanding contributions to logic, Vol. 4. Springer. 334 pages.

Digital Library

[10]

Silke Czarnetzki and Andreas Krebs. 2016. Using Duality in Circuit Complexity. In Language and Automata Theory and Applications - 10th International Conference, LATA 2016, Prague, Czech Republic, March 14--18, 2016, Proceedings. 283--294.

[11]

Samuel Eilenberg. 1976. Automata, languages, and machines. Vol. B. Academic Press.

Digital Library

[12]

Merrick Furst, James B. Saxe, and Michael Sipser. 1984. Parity, circuits, and the polynomial hierarchy. Mathematical Systems Theory 17 (1984), 13--27.

[13]

Mai Gehrke, Serge Grigorieff, and Jean-Éric Pin. 2008. Duality and Equational Theory of Regular Languages. In ICALP 2008, Part II, Aceto et al. (Ed.). Springer, Berlin Heidelberg, 246--257.

Digital Library

[14]

Mai Gehrke, Serge Grigorieff, and Jean-Éric Pin. 2010. A Topological Approach to Recognition. In ICALP 2010, Part II. Springer-Verlag, Berlin, Heidelberg, 151--162. http://dl.acm.org/citation.cfm?id=1880999.1881016

Digital Library

[15]

Mai Gehrke and Bjarni Jónsson. 2004. Bounded distributive lattices expansions. Math. Scand. 94, 2 (2004), 13--45.

[16]

Mai Gehrke, Andreas Krebs, and Jean-Éric Pin. 2016. Ultrafilters on Words for a Fragment of Logic. Theor. Comput. Sci. 610, PA (Jan. 2016), 37--58.

Digital Library

[17]

Mai Gehrke, Hideo Nagahashi, and Yde Venema. 2005. A Sahlqvist Theorem for distributive modal logics. Annals of Pure and Applied Logic 131, 1--3 (2005), 65--102.

[18]

Mai Gehrke, Daniela Petrişan, and Luca Reggio. 2016. The Schützenberger Product for Syntactic Spaces. In ICALP 2016. Schloss Dagstuhl, 112:1--112:14.

[19]

Mai Gehrke, Daniela Petrişan, and Luca Reggio. 2017. Quantifiers on languages and codensity monads. (2017). https://arxiv.org/abs/1702.08841 To appear in LICS.

[20]

Silvio Ghilardi. 1995. An Algebraic Theory of Normal Forms. Annals of Pure and Applied Logic 71, 3 (1995), 189--245.

[21]

Silvio Ghilardi. 2004. Unification, finite duality and projectivity in varieties of Heyting algebras. Annals of Pure and Applied Logic 127, 1--3 (2004), 99--115.

[22]

Robert Goldblatt. 1989. Varieties of complex algebras. Annals of Pure and Applied Logic 44 (1989), 173--242.

[23]

Neil Immerman. 1999. Descriptive Complexity. Springer-Verlag, New York.

[24]

Andreas Krebs, Klaus-Jörn Lange, and Stephanie Reifferscheid. 2007. Characterizing TC⁰ in Terms of Infinite Groups. Theory Comput. Syst. 40, 4 (2007), 303--325.

Digital Library

[25]

Michal Kunc. 2003. Equational description of pseudovarieties of homomorphisms. Theoret. Informatics Appl.37 (2003), 243--254.

[26]

Robert McNaughton and Seymour Papert. 1971. Counter-free Automata. MIT Press.

[27]

Jean-Éric Pin. 2009. Profinite Methods in Automata Theory. In STACS 2009, Albers and Marion (Eds.), Vol. 3. Schloss Dagstuhl, 31--50. http://drops.dagstuhl.de/opus/volltexte/2009/1856

[28]

Jean-Éric Pin and Howard Straubing. 2005. Some results on C-varieties. Theoret. Informatics Appl. 39 (2005), 239--262.

[29]

Nicholas Pippenger. 1997. Regular Languages and Stone Duality. Theory Comput. Syst. 30, 2 (1997), 121--134.

[30]

Jan Reiterman. 1982. The Birkhoff theorem for finite algebras. Algebra Universalis 14, 1 (1982), 1--10.

[31]

John Rhodes and Benjamin Steinberg. 2009. The q-theory of finite semigroups. Springer Verlag. 666 pages.

Digital Library

[32]

Marcel-Paul Schützenberger. 1965. On finite monoids having only trivial subgroups. Inform. Control 8 (1965), 190--194.

[33]

Marshall H. Stone. 1936. The theory of representations for Boolean algebras. TAMS 40 (1936), 37--111.

[34]

Howard Straubing. 1994. Finite Automata, Formal Logic, and Circuit Complexity. Birkhauser.

Digital Library

[35]

Pascal Tesson and Denis Thérien. 2007. Logic meets algebra: the case of regular languages. Log. Methods Comput. Sci. 3, 1 (2007), 1:4, 37.

[36]

Yde Venema. 2006. Algebras and coalgebras. In Handbook of Modal Logic, Blackburn et al (Ed.). Elsevier, 331--426.

[37]

Pascal Weil. 2002. Profinite methods in semigroup theory. Int. J. Alg. Comput. 12 (2002), 137--178.

[38]

Ryan Williams. 2014. Nonuniform ACC Circuit Lower Bounds. J. ACM 61, 1, Article 2 (Jan. 2014), 32 pages.

Digital Library

Cited By

Gehrke MPetrişan DReggio LAceto LIngólfsdóttir A(2017)Quantifiers on languages and codensity monadsProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330075(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330075

Stone duality for languages and complexity
1. Theory of computation
  1. Formal languages and automata theory
    1. Formalisms
  2. Models of computation

Recommendations

Nondeterministic state complexity of star-free languages

We investigate the nondeterministic state complexity of several operations on finite automata accepting star-free and unary star-free languages. It turns out that in most cases exactly the same tight bounds as for general regular languages are reached. ...
Descriptional complexity of bounded context-free languages

We investigate finite-turn pushdown automata (PDAs) from the point of view of descriptional complexity. It is known that such automata accept exactly the class of ultralinear context-free languages. Furthermore, the increase in size when converting ...
The complexity of finite languages

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGLOG News

ACM SIGLOG News Volume 4, Issue 2

April 2017

125 pages

EISSN:2372-3491

DOI:10.1145/3090064

Editor:
Andrzej Murawski
University of Warwick

Issue’s Table of Contents

Copyright © 2017 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 May 2017

Published in SIGLOG Volume 4, Issue 2

Check for updates

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

1
Total Citations
View Citations
139
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)1

Reflects downloads up to 11 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Gehrke MPetrişan DReggio LAceto LIngólfsdóttir A(2017)Quantifiers on languages and codensity monadsProceedings of the 32nd Annual ACM/IEEE Symposium on Logic in Computer Science10.5555/3329995.3330075(1-12)Online publication date: 20-Jun-2017
https://dl.acm.org/doi/10.5555/3329995.3330075

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents