Star-free regular sets of ω-sequences
From MaRDI portal
Publication:4198738
DOI10.1016/S0019-9958(79)90629-6zbMath0411.03031MaRDI QIDQ4198738
Publication date: 1979
Published in: Information and Control (Search for Journal in Brave)
automatadefinabilityfirst-order languageEhrenfeucht gamesmonadic second-order languagestar-free regular word-sets
Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Classical first-order logic (03B10) Decidability of theories and sets of sentences (03B25)
Related Items (39)
CTL\(^*\) and ECTL\(^*\) as fragments of the modal \(\mu\)-calculus ⋮ Towards a language theory for infinite N-free pomsets. ⋮ Infinite-word languages and continuous mappings ⋮ First-order logic and star-free sets ⋮ Functional Specification of Hardware via Temporal Logic ⋮ Brzozowski hierarchy of \(\omega\)-languages ⋮ Pure future local temporal logics are expressively complete for Mazurkiewicz traces ⋮ A game theoretical approach to the algebraic counterpart of the Wagner hierarchy : Part I ⋮ A Game Theoretical Approach to The Algebraic Counterpart of The Wagner Hierarchy : Part II ⋮ The Algebraic Counterpart of the Wagner Hierarchy ⋮ Schützenberger and Eilenberg theorems for words on linear orderings ⋮ A first-order logic characterization of safety and co-safety languages ⋮ Logic vs topology on regular \(\omega \)-languages ⋮ Constrained properties, semilinear systems, and Petri nets ⋮ On the translation of automata to linear temporal logic ⋮ Constructing the maximum prefix-closed subset for a set of \(-\omega \)-words defined by a \(-\omega \)-regular expression ⋮ Quantitative vs. weighted automata ⋮ FINE HIERARCHY OF REGULAR APERIODIC ω-LANGUAGES ⋮ On weighted first-order logics with discounting ⋮ \(\omega\)-languages accepted by finite automata whose structures are cascade products o resets ⋮ Fine hierarchies and m-reducibilities in theoretical computer science ⋮ Varieties of finite monoids and Büchi-McNaughton theorem ⋮ The stuttering principle revisited ⋮ On Expressive Power of Regular Expressions over Infinite Orders ⋮ Logic and rational languages of words indexed by linear orderings ⋮ From Philosophical to Industrial Logics ⋮ Unnamed Item ⋮ Unnamed Item ⋮ From Monadic Logic to PSL ⋮ Temporal logic with recursion ⋮ Logic, semigroups and automata on words ⋮ A Hierarchical Completeness Proof for Propositional Interval Temporal Logic with Finite Time ⋮ Characterization of \(\omega\)-regular languages by monadic second-order formulas ⋮ Star free expressions over the reals ⋮ Expressive completeness of duration calculus. ⋮ Star-free sets of words on ordinals ⋮ Process logic with regular formulas ⋮ On the expressive power of temporal logic for infinite words ⋮ Logic over words on denumerable ordinals
This page was built for publication: Star-free regular sets of ω-sequences
