Logical definability on infinite traces

DOI10.1016/0304-3975(95)00130-1zbMath0871.68111OpenAlexW2034083679MaRDI QIDQ672860

Anca Muscholl, Werner Ebinger

Publication date: 28 February 1997

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0304-3975(95)00130-1

zbMATH Keywords

monadic second-order logicrecognizability for real trace languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (18)

An extension of the wreath product principle for finite Mazurkiewicz traces ⋮ Regular sets of infinite message sequence charts ⋮ Generalized rational relations and their logical definability ⋮ On the complementation of asynchronous cellular Büchi automata ⋮ Pure future local temporal logics are expressively complete for Mazurkiewicz traces ⋮ Solving word equations modulo partial commutations ⋮ Muller message-passing automata and logics ⋮ AN EXPRESSIVE EXTENSION OF TLC ⋮ A Büchi-like theorem for weighted tree automata over multioperator monoids ⋮ Local temporal logic is expressively complete for cograph dependence alphabets ⋮ From local to global temporal logics over Mazurkiewicz traces. ⋮ A Kleene theorem and model checking algorithms for existentially bounded communicating automata ⋮ Unnamed Item ⋮ Local testability from words to traces, a suitable definition ⋮ RECOGNIZABLE AND LOGICALLY DEFINABLE LANGUAGES OF INFINITE COMPUTATIONS IN CONCURRENT AUTOMATA ⋮ A theory of regular MSC languages ⋮ Models for quantitative distributed systems and multi-valued logics ⋮ LTL is expressively complete for Mazurkiewicz traces

Cites Work

• On the concatenation of infinite traces
• A syntactic congruence for rational \(\omega\)-languages
• First-order logic and star-free sets
• Theory of traces
• Combinatorics on traces
• Star-free trace languages
• An extension of Kleene's and Ochmański's theorems to infinite traces
• Deterministic asynchronous automata for infinite traces
• Combinatorial problems of commutation and rearrangements
• Une condition suffisante de reconnaissabilité dans un monoïde partiellement commutatif
• Notes on finite asynchronous automata
• Asynchronous cellular automata for infinite traces
• On finite monoids having only trivial subgroups
• Inhomogeneous sorting
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Logical definability on infinite traces