Regular expressions for data words

DOI10.1016/J.JCSS.2015.03.005MaRDI QIDQ2353403zbMATH OpenOpenAlexFDO

Authors Tony Tan, Domajoj Vrgoč, Leonid Libkin

Publication date 13 July 2015

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2015.03.005

zbMATH Keywords

regular expressionsdata wordsregister automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• Regular expressions for data words
• Regular expressions with binding over data words for querying graph databases
• Regular expressions for querying data graphs
• On notions of regularity for data languages
• On Notions of Regularity for Data Languages

Cites work

• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• A lower bound technique for the size of nondeterministic finite automata
• Automata and Logics for Words and Trees over an Infinite Alphabet
• Automata for XML -- a survey
• Automata vs. Logics on Data Words
• Finding Regular Simple Paths in Graph Databases
• Finite state machines for strings over infinite alphabets
• Finite-memory automata
• Intractability of decision problems for finite-memory automata
• LTL with the freeze quantifier and register automata
• Logics for Unranked Trees: An Overview
• On the use of guards for logics with data
• Regular expressions for data words
• Regular expressions with binding over data words for querying graph databases
• Rewriting of regular expressions and regular path queries
• Tree Automata over Infinite Alphabets
• Two-variable logic on data words
• Variable automata over infinite alphabets
• XPath evaluation in linear time

Cited in

(16)

• Nondeterministic and co-nondeterministic implies deterministic, for data languages
• On computability of data word functions defined by transducers
• Problems on finite automata and the exponential time hypothesis
• Reactive synthesis from visibly register pushdown automata
• Nominal automata with name binding
• Regular expressions for querying data graphs
• scientific article; zbMATH DE number 7561600 (Why is no real title available?)
• Synthesis of data word transducers
• Active learning for deterministic bottom-up nominal tree automata
• Complexity results on register context-free grammars and related formalisms
• scientific article; zbMATH DE number 7407799 (Why is no real title available?)
• Regular expressions for data words
• Regular Transformations of Data Words Through Origin Information
• Optimal run problem for weighted register automata
• Layered memory automata: recognizers for quasi-regular languages with unbounded memory
• Automata and grammars for data words

This page was built for publication: Regular expressions for data words

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