Two-variable logic on data words
From MaRDI portal
Publication:2946646
DOI10.1145/1970398.1970403zbMath1352.03041OpenAlexW2073614038MaRDI QIDQ2946646
Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin, Mikołaj Bojańczyk
Publication date: 17 September 2015
Published in: ACM Transactions on Computational Logic (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/1970398.1970403
Logic in computer science (03B70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85) Decidability of theories and sets of sentences (03B25)
Related Items
Reactive synthesis from visibly register pushdown automata ⋮ Solving Infinite Games in the Baire Space ⋮ Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\) ⋮ Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change ⋮ Weighted Register Automata and Weighted Logic on Data Words ⋮ Future-Looking Logics on Data Words and Trees ⋮ On Pebble Automata for Data Languages with Decidable Emptiness Problem ⋮ Metric propositional neighborhood logic with an equivalence relation ⋮ On temporal logics with data variable quantifications: decidability and complexity ⋮ Reachability in pushdown register automata ⋮ Layered memory automata: recognizers for quasi-regular languages with unbounded memory ⋮ Communicating Finite-State Machines and Two-Variable Logic ⋮ Complexity results on register context-free grammars and related formalisms ⋮ Automata and Logics for Concurrent Systems: Five Models in Five Pages ⋮ Separation logics and modalities: a survey ⋮ Set augmented finite automata over infinite alphabets ⋮ Coverability in 2-VASS with one unary counter is in NP ⋮ Active learning for deterministic bottom-up nominal tree automata ⋮ Logics for unordered trees with data constraints ⋮ Realizability problem for constraint LTL ⋮ Finite Automata Over Infinite Alphabets: Two Models with Transitions for Local Change ⋮ Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic ⋮ On pebble automata for data languages with decidable emptiness problem ⋮ Unnamed Item ⋮ Logics of Repeating Values on Data Trees and Branching Counter Systems ⋮ A succinct canonical register automaton model ⋮ Beyond Knowing That: A New Generation of Epistemic Logics ⋮ Algorithmic Nominal Game Semantics ⋮ Leafy automata for higher-order concurrency ⋮ Nondeterministic and co-nondeterministic implies deterministic, for data languages ⋮ Walking on data words ⋮ On regular paths with counting and data tests ⋮ A Note on C² Interpreted over Finite Data-Words ⋮ Variable Tree Automata over Infinite Ranked Alphabets ⋮ Extending two-variable logic on data trees with order on data values and its automata ⋮ Learning Transparent Data Automata ⋮ $$\mathbb {N}$$ -Memory Automata over the Alphabet $$\mathbb {N}$$ ⋮ The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata ⋮ Unnamed Item ⋮ Weighted register automata and weighted logic on data words ⋮ Playing with Repetitions in Data Words Using Energy Games ⋮ Weak and Nested Class Memory Automata ⋮ Streamable regular transductions ⋮ Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al. ⋮ On Freeze LTL with Ordered Attributes ⋮ Optimal run problem for weighted register automata ⋮ Abstraction refinement and antichains for trace inclusion of infinite state systems ⋮ A Class of Automata for the Verification of Infinite, Resource-Allocating Behaviours ⋮ An Automaton over Data Words That Captures EMSO Logic ⋮ Expressiveness of Hybrid Temporal Logic on Data Words ⋮ Algorithmic Analysis of Array-Accessing Programs ⋮ Unnamed Item ⋮ The Complexity of Flat Freeze LTL ⋮ An automata-theoretic approach to model-checking systems and specifications over infinite data domains ⋮ Regular expressions for data words