Regular languages defined with generalized quantifiers

DOI10.1006/INCO.1995.1067MaRDI QIDQ1892890zbMATH OpenOpenAlexFDO

Authors Howard Straubing, Denis Thérien, Wolfgang Thomas

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

complexity theoryfirst-order logicrecognizable languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• scientific article; zbMATH DE number 4076666
• scientific article; zbMATH DE number 1688392
• Regular languages defined by generalized first-order formulas with a bounded number of bound variables
• scientific article; zbMATH DE number 2051828
• Regular Languages Definable by Majority Quantifiers with Two Variables
• Generalizations of 1-deterministic regular languages
• Separating regular languages with two quantifier alternations
• scientific article; zbMATH DE number 4009839
• scientific article; zbMATH DE number 3917732
• scientific article; zbMATH DE number 1244205

Cited in

(33)

• Linear circuits, two-variable logic and weakly blocked monoids
• Developments in Language Theory
• One quantifier alternation in first-order logic with modular predicates
• Hierarchies and reducibilities on regular languages related to modulo counting
• Cascade Products and Temporal Logics on Finite Trees
• Definability of Languages by Generalized First-Order Formulas over $(\mathbb{N},+)$
• Separating regular languages with two quantifier alternations
• Regular languages defined by generalized first-order formulas with a bounded number of bound variables
• Quantifiers on languages and codensity monads
• Counting modulo quantifiers on finite structures
• Definability of Languages by Generalized First-Order Formulas over (N,+)
• Trace languages definable with modular quantifiers
• Regular grammars with truth values in lattice-ordered monoid and their languages
• Varieties
• Regular sets of infinite message sequence charts
• A Cook's tour of duality in logic: from quantifiers, through Vietoris, to measures
• On Second-Order Monadic Groupoidal Quantifiers
• scientific article; zbMATH DE number 4201629 (Why is no real title available?)
• scientific article; zbMATH DE number 2087422 (Why is no real title available?)
• Weakly iterated block products and applications to logic and complexity
• Characterizing classes of regular languages using prefix codes of bounded synchronization delay
• Expressive completeness for LTL with modulo counting and group quantifiers
• Regular Languages Definable by Majority Quantifiers with Two Variables
• Characterizing CTL-like logics on finite trees.
• scientific article; zbMATH DE number 2051828 (Why is no real title available?)
• Circuit complexity of regular languages
• Codensity, profiniteness and algebras of semiring-valued measures
• Modulo counting on words and trees
• scientific article; zbMATH DE number 4076666 (Why is no real title available?)
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• PROFINITE IDENTITIES FOR FINITE SEMIGROUPS WHOSE SUBGROUPS BELONG TO A GIVEN PSEUDOVARIETY
• Modular quantifiers
• Languages defined with modular counting quantifiers

This page was built for publication: Regular languages defined with generalized quantifiers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1892890)