Regular languages defined by generalized first-order formulas with a bounded number of bound variables

DOI10.1007/s00224-002-1035-9zbMath1039.68072OpenAlexW2904842705MaRDI QIDQ1405799

Denis Thérien, Howard Straubing

Publication date: 26 August 2003

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00224-002-1035-9

zbMATH Keywords

syntactic monoids

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (8)

Linear circuits, two-variable logic and weakly blocked monoids ⋮ A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS ⋮ WEAKLY ITERATED BLOCK PRODUCTS AND APPLICATIONS TO LOGIC AND COMPLEXITY ⋮ Möbius functions and semigroup representation theory. II: Character formulas and multiplicities. ⋮ Non-solvable Groups Are Not in FO+MOD+MÂJ2[REG] ⋮ THE DOT-DEPTH AND THE POLYNOMIAL HIERARCHIES CORRESPOND ON THE DELTA LEVELS ⋮ Regular Languages Definable by Majority Quantifiers with Two Variables ⋮ One quantifier alternation in first-order logic with modular predicates

This page was built for publication: Regular languages defined by generalized first-order formulas with a bounded number of bound variables