Two-variable logic on data words

DOI10.1145/1970398.1970403MaRDI QIDQ2946646zbMATH OpenOpenAlexWikidataFDO

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

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)

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

Cited in

(70)

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

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)