Regular languages defined with generalized quantifiers

DOI10.1006/inco.1995.1067zbMath0826.68072OpenAlexW2034586951MaRDI QIDQ1892890

Wolfgang Thomas, Denis Thérien, Howard Straubing

Publication date: 10 July 1995

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/inco.1995.1067

zbMATH Keywords

first-order logiccomplexity theoryrecognizable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items

Regular sets of infinite message sequence charts ⋮ Linear circuits, two-variable logic and weakly blocked monoids ⋮ Unnamed Item ⋮ Characterizing classes of regular languages using prefix codes of bounded synchronization delay ⋮ Hierarchies and reducibilities on regular languages related to modulo counting ⋮ WEAKLY ITERATED BLOCK PRODUCTS AND APPLICATIONS TO LOGIC AND COMPLEXITY ⋮ Circuit complexity of regular languages ⋮ The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey ⋮ Characterizing CTL-like logics on finite trees. ⋮ Expressive Completeness for LTL With Modulo Counting and Group Quantifiers ⋮ Unnamed Item ⋮ Codensity, profiniteness and algebras of semiring-valued measures ⋮ Varieties ⋮ PROFINITE IDENTITIES FOR FINITE SEMIGROUPS WHOSE SUBGROUPS BELONG TO A GIVEN PSEUDOVARIETY ⋮ One quantifier alternation in first-order logic with modular predicates ⋮ Quantifiers on languages and codensity monads ⋮ Counting modulo quantifiers on finite structures ⋮ Languages defined with modular counting quantifiers ⋮ Cascade Products and Temporal Logics on Finite Trees