![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Howard Straubing
Person information
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 2020
- [j32]Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing:
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. Log. Methods Comput. Sci. 16(3) (2020) - 2018
- [j31]Howard Straubing:
First-order logic and aperiodic languages: a revisionist history. ACM SIGLOG News 5(3): 4-20 (2018) - 2017
- [j30]Andreas Krebs, Howard Straubing:
An Effective Characterization of the Alternation Hierarchy in Two-Variable Logic. ACM Trans. Comput. Log. 18(4): 30:1-30:22 (2017) - 2016
- [j29]Arkadev Chattopadhyay, Frederic Green, Howard Straubing:
Circuit Complexity of Powering in Fields of Odd Characteristic. Chic. J. Theor. Comput. Sci. 2016 (2016) - 2015
- [j28]Howard Straubing:
A new proof of the locality of R. Int. J. Algebra Comput. 25(1-2): 293-300 (2015) - 2013
- [j27]Howard Straubing:
New applications of the wreath product of forest algebras. RAIRO Theor. Informatics Appl. 47(3): 261-291 (2013) - 2012
- [j26]Mikolaj Bojanczyk, Luc Segoufin, Howard Straubing:
Piecewise testable tree languages. Log. Methods Comput. Sci. 8(3) (2012) - [j25]Mikolaj Bojanczyk, Howard Straubing, Igor Walukiewicz:
Wreath Products of Forest Algebras, with Applications to Tree Logics. Log. Methods Comput. Sci. 8(3) (2012) - 2010
- [j24]Howard Straubing, Pascal Tesson, Denis Thérien:
Weakly Iterated Block Products and Applications to Logic and Complexity. Int. J. Algebra Comput. 20(2): 319-341 (2010) - 2007
- [j23]Amitabha Roy, Howard Straubing:
Definability of Languages by Generalized First-Order Formulas over N+. SIAM J. Comput. 37(2): 502-521 (2007) - 2006
- [j22]Howard Straubing, Denis Thérien:
A Note on MODp - MODm Circuits. Theory Comput. Syst. 39(5): 699-706 (2006) - [j21]Laura Chaubard, Jean-Eric Pin, Howard Straubing:
Actions, wreath products of C-varieties and concatenation product. Theor. Comput. Sci. 356(1-2): 73-89 (2006) - 2005
- [j20]Jean-Eric Pin, Howard Straubing:
Some results on C-varieties. RAIRO Theor. Informatics Appl. 39(1): 239-262 (2005) - 2003
- [j19]Howard Straubing, Denis Thérien:
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. Theory Comput. Syst. 36(1): 29-69 (2003) - 2001
- [j18]Howard Straubing:
Languages Defined with Modular Counting Quantifiers. Inf. Comput. 166(2): 112-132 (2001) - 1999
- [j17]David A. Mix Barrington, Howard Straubing:
Lower bounds for modular counting by circuits with modular gates. Comput. Complex. 8(3): 258-272 (1999) - 1997
- [j16]Pierre Péladeau, Howard Straubing, Denis Thérien:
Finite Semigroup Varieties Defined by Programs. Theor. Comput. Sci. 180(1-2): 325-339 (1997) - 1995
- [j15]Howard Straubing, Denis Thérien, Wolfgang Thomas:
Regular Languages Defined with Generalized Quanifiers. Inf. Comput. 118(2): 289-301 (1995) - [j14]David A. Mix Barrington, Howard Straubing:
Superlinear Lower Bounds for Bounded-Width Branching Programs. J. Comput. Syst. Sci. 50(3): 374-381 (1995) - 1994
- [j13]David A. Mix Barrington, Howard Straubing:
Complex Polynomials and Circuit Lower Bounds for Modular Counting. Comput. Complex. 4: 325-338 (1994) - 1992
- [j12]Kevin J. Compton, Howard Straubing:
Characterizations of regular languages in low level complexity classes. Bull. EATCS 48: 134-142 (1992) - [j11]Jean-Eric Pin, Howard Straubing, Denis Thérien:
Some Results on the Generalized Star-Height Problem. Inf. Comput. 101(2): 219-250 (1992) - [j10]David A. Mix Barrington, Kevin J. Compton, Howard Straubing, Denis Thérien:
Regular Languages in NC¹. J. Comput. Syst. Sci. 44(3): 478-499 (1992) - [j9]Howard Straubing, Pascal Weil:
On a Conjecture Concerning Dot-Depth Two Languages. Theor. Comput. Sci. 104(2): 161-183 (1992) - 1991
- [j8]Howard Straubing:
Constant-Depth periodic Circuits. Int. J. Algebra Comput. 1(1): 49-88 (1991) - 1990
- [j7]David A. Mix Barrington, Howard Straubing, Denis Thérien:
Non-Uniform Automata Over Groups. Inf. Comput. 89(2): 109-132 (1990) - [j6]David A. Mix Barrington, Neil Immerman, Howard Straubing:
On Uniformity within NC¹. J. Comput. Syst. Sci. 41(3): 274-306 (1990) - 1988
- [j5]Howard Straubing:
Semigroups and Languages of Dot-Depth Two. Theor. Comput. Sci. 58: 361-378 (1988) - 1987
- [j4]Howard Straubing:
Applications of the theory of automata in enumeration. Discret. Math. 64(2-3): 269-279 (1987) - 1983
- [j3]Howard Straubing:
A combinatorial proof of the Cayley-Hamilton theorem. Discret. Math. 43(2-3): 273-279 (1983) - 1981
- [j2]Howard Straubing:
Relationals Morphisms and Operations on Recognizable Sets. RAIRO Theor. Informatics Appl. 15(2): 149-159 (1981) - [j1]Howard Straubing:
A Generalization of the Schützenberger Product of Finite Monoids. Theor. Comput. Sci. 13: 137-150 (1981)
Conference and Workshop Papers
- 2018
- [c28]Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing:
An Algebraic Decision Procedure for Two-Variable Logic with a Between Relation. CSL 2018: 28:1-28:17 - [c27]Michael Hahn, Andreas Krebs, Howard Straubing:
Wreath Products of Distributive Forest Algebras. LICS 2018: 512-520 - 2016
- [c26]Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing:
Two-variable Logic with a Between Relation. LICS 2016: 106-115 - 2015
- [c25]Andreas Krebs, Howard Straubing:
EF+EX Forest Algebras. CAI 2015: 128-139 - 2012
- [c24]Andreas Krebs, Howard Straubing:
An effective characterization of the alternation hierarchy in two-variable logic. FSTTCS 2012: 86-98 - 2011
- [c23]Howard Straubing:
Algebraic Characterization of the Alternation Hierarchy in FO2[<] on Finite Words. CSL 2011: 525-537 - 2009
- [c22]Mikolaj Bojanczyk, Howard Straubing, Igor Walukiewicz:
Wreath Products of Forest Algebras, with Applications to Tree Logics. LICS 2009: 255-263 - 2008
- [c21]Howard Straubing, Denis Thérien:
Modular quantifiers. Logic and Automata 2008: 613-628 - [c20]Mikolaj Bojanczyk, Luc Segoufin, Howard Straubing:
Piecewise Testable Tree Languages. LICS 2008: 442-451 - 2006
- [c19]Laura Chaubard, Jean-Eric Pin, Howard Straubing:
First Order Formulas with Modular Predicates. LICS 2006: 211-220 - [c18]Amitabha Roy, Howard Straubing:
Definability of Languages by Generalized First-Order Formulas over (N, +). STACS 2006: 489-499 - 2005
- [c17]Howard Straubing:
Inexpressibility Results for Regular Languages in Nonregular Settings. Developments in Language Theory 2005: 69-77 - 2002
- [c16]Howard Straubing, Denis Thérien:
Weakly Iterated Block Products of Finite Monoids. LATIN 2002: 91-104 - [c15]Howard Straubing:
On Logical Descriptions of Regular Languages. LATIN 2002: 528-538 - 2001
- [c14]Howard Straubing, Denis Thérien:
Regular Languages Defined by Generalized First-Order Formulas with a Bounded Number of Bound Variables. STACS 2001: 551-562 - 1998
- [c13]Howard Straubing:
Languages Defined With Modular Counting Quantifiers (Extended Abstract). STACS 1998: 332-343 - 1996
- [c12]Howard Straubing:
Finite Models, Automata, and Circuit Complexity. Descriptive Complexity and Finite Models 1996: 63-96 - 1995
- [c11]Richard Beigel, Howard Straubing:
The Power of Local Self-Reductions. SCT 1995: 277-285 - [c10]David A. Mix Barrington, Howard Straubing:
Lower Bounds for Modular Counting by Circuits with Modular Gates. LATIN 1995: 60-71 - 1992
- [c9]Howard Straubing:
Circuit Complexity and the Expressive Power of Generalized First-Order Formulas. ICALP 1992: 16-27 - [c8]David A. Mix Barrington, Howard Straubing:
Complex Polynomials and Circuit Lower Bounds for Modular Counting. LATIN 1992: 24-31 - 1991
- [c7]David A. Mix Barrington, Howard Straubing:
Superlinear Lower Bounds for Bounded-Width Branching Programs. SCT 1991: 305-313 - 1989
- [c6]Jean-Eric Pin, Howard Straubing, Denis Thérien:
New Results on the Generalized Star-Height Problem. STACS 1989: 458-467 - 1988
- [c5]David A. Mix Barrington, Neil Immerman, Howard Straubing:
On uniformity within NC1. SCT 1988: 47-59 - [c4]Howard Straubing, Denis Thérien, Wolfgang Thomas:
regular Languages Defined with Generalized Quantifiers. ICALP 1988: 561-575 - [c3]Howard Straubing:
The wreath product and its applications. Formal Properties of Finite Automata and Applications 1988: 15-24 - [c2]Howard Straubing, Denis Thérien:
Finite automata and computational complexity. Formal Properties of Finite Automata and Applications 1988: 199-233 - 1986
- [c1]Howard Straubing:
Semigroups and Languages of Dot-Depth 2. ICALP 1986: 416-423
Parts in Books or Collections
- 2021
- [p3]Howard Straubing, Pascal Weil:
Varieties. Handbook of Automata Theory (I.) 2021: 569-614 - 2012
- [p2]Howard Straubing, Pascal Weil:
An Introduction to Finite Automata and their Connection to Logic. Modern Applications of Automata Theory 2012: 3-44 - 2001
- [p1]Kevin J. Compton, Howard Straubing:
Characterizations of Regular Languages in Low Level Complexity Classes. Current Trends in Theoretical Computer Science 2001: 235-246
Informal and Other Publications
- 2022
- [i11]Andreas Krebs, Howard Straubing:
Regular languages defined by first-order formulas without quantifier alternation. CoRR abs/2208.10480 (2022) - 2019
- [i10]Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing:
Two-variable logics with some betweenness relations: Expressiveness, satisfiability and membership. CoRR abs/1902.05905 (2019) - [i9]Michael Hahn, Andreas Krebs, Howard Straubing:
Wreath Products of Distributive Forest Algebras. CoRR abs/1911.03493 (2019) - 2018
- [i8]Howard Straubing:
Forest Categories. CoRR abs/1801.04337 (2018) - [i7]Célia Borlido, Mai Gehrke, Andreas Krebs, Howard Straubing:
Difference hierarchies and duality with an application to formal languages. CoRR abs/1812.01921 (2018) - 2016
- [i6]Andreas Krebs, Kamal Lodaya, Paritosh K. Pandya, Howard Straubing:
Two-variable Logic with a Between Predicate. CoRR abs/1603.05625 (2016) - 2015
- [i5]Howard Straubing, Pascal Weil:
Varieties. CoRR abs/1502.03951 (2015) - 2014
- [i4]Andreas Krebs, Howard Straubing:
EF+EX Forest Algebras. CoRR abs/1408.0809 (2014) - 2012
- [i3]Andreas Krebs, Howard Straubing:
An effective characterization of the alternation hierarchy in two-variable logic. CoRR abs/1205.4802 (2012) - 2010
- [i2]Howard Straubing, Pascal Weil:
An introduction to finite automata and their connection to logic. CoRR abs/1011.6491 (2010) - 1995
- [i1]Richard Beigel, Howard Straubing:
The Power of Local Self-Reductions. Electron. Colloquium Comput. Complex. TR95 (1995)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-04-24 23:15 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint