Two-variable logic on data words

DOI10.1145/1970398.1970403zbMATH Open1352.03041OpenAlexW2073614038WikidataQ130866193 ScholiaQ130866193MaRDI QIDQ2946646FDOQ2946646

Authors: Mikołaj Bojańczyk, Claire David, Anca Muscholl, Thomas Schwentick, Luc Segoufin 

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

Recommendations

• On the satisfiability of two-variable logic over data words
• Two-variable logic on 2-dimensional structures
• Two-variable logic with two order relations (extended abstract)
• Two-variable logic with two order relations
• Feasible automata for two-variable logic with successor on data words

zbMATH Keywords

first-order logicequivalence relationdata wordsPetri-net reachabilitytwo-variables logic

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Logic in computer science (03B70) Models and methods for concurrent and distributed computing (process algebras, bisimulation, transition nets, etc.) (68Q85)

Cited In (70)

• Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic
• Logics for unordered trees with data constraints
• On Pebble Automata for Data Languages with Decidable Emptiness Problem
• An automata-theoretic approach to model-checking systems and specifications over infinite data domains
• Weak and nested class memory automata
• Generalized data automata and fixpoint logic
• Separation logics and modalities: a survey
• Reactive synthesis from visibly register pushdown automata
• Algorithmic Analysis of Array-Accessing Programs
• Reasoning about data repetitions with counter systems
• On regular paths with counting and data tests
• Finite \(n\)-tape automata over possibly infinite alphabets: Extending a theorem of Eilenberg et al.
• Nondeterministic and co-nondeterministic implies deterministic, for data languages
• Toward model theory with data values
• Reachability in pushdown register automata
• Algorithmic nominal game semantics
• Adding one or more equivalence relations to the interval temporal logic \(\mathsf{AB}\overline{\mathsf{B}}\)
• Querying best paths in graph databases
• An automaton over data words that captures EMSO logic
• Variable tree automata over infinite ranked alphabets
• Automata and Logics for Concurrent Systems: Five Models in Five Pages
• Logics of repeating values on data trees and branching counter systems
• Beyond knowing that: a new generation of epistemic logics
• Active learning for deterministic bottom-up nominal tree automata
• Metric propositional neighborhood logic with an equivalence relation
• Future-Looking Logics on Data Words and Trees
• Reasoning about data repetitions with counter systems
• Weighted register automata and weighted logic on data words
• Weighted register automata and weighted logic on data words
• The complexity of flat freeze LTL
• Streamable regular transductions
• Layered memory automata: recognizers for quasi-regular languages with unbounded memory
• A succinct canonical register automaton model
• Leafy automata for higher-order concurrency
• Expressiveness of hybrid temporal logic on data words
• On temporal logics with data variable quantifications: decidability and complexity
• Extending two-variable logic on data trees with order on data values and its automata
• Complexity results on register context-free grammars and related formalisms
• The ``equal last letter predicate for words on infinite alphabets and classes of multitape automata
• Regular expressions for data words
• Two-variable logic on 2-dimensional structures
• Finite automata over infinite alphabets: two models with transitions for local change
• Title not available (Why is that?)
• Finite automata over infinite alphabets: two models with transitions for local change
• Pebble-intervals automata and \(\text{FO}^2\) with two orders
• \(\mathbb {N}\)-memory automata over the alphabet \(\mathbb {N}\)
• Fragments of fixpoint logic on data words
• Walking on data words
• Automata and Logics for Words and Trees over an Infinite Alphabet
• Solving Infinite Games in the Baire Space
• Safety alternating automata on data words
• Communicating finite-state machines and two-variable logic
• On the satisfiability of two-variable logic over data words
• Feasible automata for two-variable logic with successor on data words
• On freeze LTL with ordered attributes
• A class of automata for the verification of infinite, resource-allocating behaviours
• On pebble automata for data languages with decidable emptiness problem
• Round- and context-bounded control of dynamic pushdown systems
• On the satisfiability of local first-order logics with data
• Realizability problem for constraint LTL
• A Note on C² Interpreted over Finite Data-Words
• Set augmented finite automata over infinite alphabets
• Learning Transparent Data Automata
• Abstraction refinement and antichains for trace inclusion of infinite state systems
• Optimal run problem for weighted register automata
• Coverability in 2-VASS with one unary counter is in NP
• First order Büchi automata and their application to verification of LTL specifications
• Reasoning on data words over numeric domains
• On the existential fragments of local first-order logics with data
• Automata and grammars for data words

This page was built for publication: Two-variable logic on data words

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