Games, equations and the dot-depth hierarchy

DOI10.1016/0898-1221(89)90179-XzbMATH Open0682.03015MaRDI QIDQ1823928FDOQ1823928

Authors: F. Blanchet-Sadri 

Publication date: 1989

Published in: Computers & Mathematics with Applications (Search for Journal in Brave)

Recommendations

• Games, equations and dot-depth two monoids
• On dot-depth two
• scientific article; zbMATH DE number 4049066
• THE DOT-DEPTH OF A GENERATING CLASS OF APERIODIC MONOIDS IS COMPUTABLE
• An application of the Ehrenfeucht-Fraisse game in formal language theory

zbMATH Keywords

monoid varietiesEhrenfeucht-Fraisse gamefine structure of the Straubing hierarchy of star-free languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Equational classes, universal algebra in model theory (03C05) Semigroups in automata theory, linguistics, etc. (20M35)

Cites Work

• Title not available (Why is that?)
• Characterizations of locally testable events
• Title not available (Why is that?)
• Title not available (Why is that?)
• An application of games to the completeness problem for formalized theories
• Title not available (Why is that?)
• On finite monoids having only trivial subgroups
• Classifying regular events in symbolic logic
• Title not available (Why is that?)
• First-order logic and star-free sets
• Finite semigroup varieties of the form V*D
• Dot-depth of star-free events
• Title not available (Why is that?)
• $ℵ_0$-categoricity of linear orderings
• Title not available (Why is that?)
• Application of model theoretic games to discrete linear orders and finite automata
• Categories as algebra: An essential ingredient in the theory of monoids
• Title not available (Why is that?)
• Title not available (Why is that?)
• Algebraic decision procedures for local testability
• The dot-depth hierarchy of star-free languages is infinite
• Title not available (Why is that?)
• An application of the Ehrenfeucht-Fraisse game in formal language theory

Cited In (20)

• On dot-depth two
• Equations on the semidirect product of a finite semilattice by a $\mathcal {J}$-trivial monoid of height $k$
• THE DOT-DEPTH OF A GENERATING CLASS OF APERIODIC MONOIDS IS COMPUTABLE
• Games, equations and dot-depth two monoids
• Hierarchies of piecewise testable languages
• On Boolean combinations forming piecewise testable languages
• The \(\omega\)-inequality problem for concatenation hierarchies of star-free languages
• Title not available (Why is that?)
• Inclusion relations between some congruences related to the dot-depth hierarchy
• On the word problem for syntactic monoids of piecewise testable languages.
• Equations and monoid varieties of dot-depth one and two
• On a complete set of generators for dot-depth two
• Hierarchies of Piecewise Testable Languages
• Polynomial closure and unambiguous product
• The variable hierarchy for the games \(\mu \)-calculus
• Tropical representations and identities of the stylic monoid
• REFLEXIVE RELATIONS, EXTENSIVE TRANSFORMATIONS AND PIECEWISE TESTABLE LANGUAGES OF A GIVEN HEIGHT
• On semidirect and two-sided semidirect products of finite $\mathcal {J}$trivial monoids
• Normal forms under Simon's congruence
• Equations and dot-depth one

This page was built for publication: Games, equations and the dot-depth hierarchy

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