Nondeterministic and co-nondeterministic implies deterministic, for data languages

DOI10.1007/978-3-030-71995-1_19OpenAlexW3137262423MaRDI QIDQ2233422FDOQ2233422

Authors Bartek Klin, Sławomir Lasota, Szymon Toruńczyk 

Publication date 18 October 2021

Full work available at URL https://doi.org/10.1007/978-3-030-71995-1_19

zbMATH Keywords

nominal setsdata languagesregister automatadeterminizabilitysets with atomsdeterministic separabilityorbit-finite sets

Mathematics Subject Classification ID

Theory of software (68Nxx) Theory of computing (68Qxx)

Cites work

• An algebraic characterization of deterministic regular languages over infinite alphabets.
• An extension of data automata that captures XPath
• Automata and Logics for Words and Trees over an Infinite Alphabet
• Automata theory in nominal sets
• Data monoids
• Decidability Border for Petri Nets with Data: WQO Dichotomy Conjecture
• Finite state machines for strings over infinite alphabets
• Finite-memory automata
• Finite-memory automata with non-deterministic reassignment
• Forms of determinism for automata
• Generalized data automata and fixpoint logic
• Intractability of decision problems for finite-memory automata
• LTL with the freeze quantifier and register automata
• Logics with rigidly guarded data tests
• Minimization of symbolic automata
• Modelling infinite structures with atoms
• Nominal sets. Names and symmetry in computer science
• Regular expressions for data words
• Regular expressions for languages over infinite alphabets
• The containment problem for unambiguous register automata and unambiguous timed automata
• Two-variable logic on data words
• Typechecking for XML transformers

Cited in

(1)

• scientific article; zbMATH DE number 7566065 (Why is no real title available?)

This page was built for publication: Nondeterministic and co-nondeterministic implies deterministic, for data languages

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