A Note on C² Interpreted over Finite Data-Words

DOI10.4230/LIPICS.TIME.2020.17MaRDI QIDQ6060103zbMATH OpenOpenAlexFDO

Authors Bartosz Bednarczyk, Piotr Witkowski

Publication date 2 November 2023

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2020/12985/pdf/LIPIcs-TIME-2020-17.pdf/

zbMATH Keywords

countingdata-wordsdecidabilitytwo-variable logicundecidabilityVASS

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Temporal logic (03B44) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Two-variable logic with counting and a linear order
• Two-variable logic on data words
• Two-variable logic with counting and a linear order
• Two-variable first order logic with counting quantifiers: complexity results
• The two-variable fragment with counting and equivalence

Cites work

• A logical characterization of data languages.
• A note on the emptiness problem for alternating finite-memory automata
• A robust class of data languages and an application to learning
• Algorithmic analysis of array-accessing programs
• An algebraic approach to data languages and timed languages
• An automaton over data words that captures EMSO logic
• An extension of data automata that captures XPath
• Demystifying Reachability in Vector Addition Systems
• First-order logic with two variables and unary temporal logic
• scientific article; zbMATH DE number 3310089 (Why is no real title available?)
• LTL with the freeze quantifier and register automata
• Metric propositional neighborhood logic with an equivalence relation
• On logics with two variables
• On temporal logics with data variable quantifications: decidability and complexity
• Presburger concept cardinality constraints in very expressive description logics. Allegro sexagenarioso ma non ritardando
• Reasoning about data repetitions with counter systems
• Shuffle Expressions and Words with Nested Data
• The reachability problem for Petri nets is not elementary
• The two-variable fragment with counting and equivalence
• The two-variable fragment with counting revisited
• Two-variable first-order logic with counting in forests
• Two-variable logic on data words
• Two-variable logic with counting and a linear order
• Weak and nested class memory automata

Cited in

(2)

• On the existential fragments of local first-order logics with data
• On the satisfiability of local first-order logics with data

This page was built for publication: A Note on C² Interpreted over Finite Data-Words

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