One-unambiguity of regular expressions with numeric occurrence indicators

DOI10.1016/J.IC.2006.12.003MaRDI QIDQ2373702zbMATH OpenOpenAlexFDO

Authors Pekka Kilpeläinen, Rauno Tuhkanen

Publication date 16 July 2007

Published in Information and Computation (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ic.2006.12.003

zbMATH Keywords

XML schemaregular expressioninterval expressionnumeric iterationone-unambiguityunique particle attribution

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Data structures (68P05)

Recommendations

• One-unambiguous regular languages
• Deciding determinism of regular languages
• Generalized one-unambiguity
• Inclusion Test Algorithms for One-Unambiguous Regular Expressions
• One-unambiguous regular languages

Cites work

• scientific article; zbMATH DE number 193480 (Why is no real title available?)
• scientific article; zbMATH DE number 194009 (Why is no real title available?)
• scientific article; zbMATH DE number 592267 (Why is no real title available?)
• scientific article; zbMATH DE number 1142294 (Why is no real title available?)
• scientific article; zbMATH DE number 1517989 (Why is no real title available?)
• scientific article; zbMATH DE number 194974 (Why is no real title available?)
• scientific article; zbMATH DE number 947197 (Why is no real title available?)
• scientific article; zbMATH DE number 3251424 (Why is no real title available?)
• A logic you can count on
• Derivatives of Regular Expressions
• Local languages and the Berry-Sethi algorithm
• Mathematical Foundations of Computer Science 2004
• One-unambiguous regular languages
• Online evaluation of regular tree queries
• Regular expressions into finite automata
• THE ABSTRACT THEORY OF AUTOMATA
• The validation of SGML content models
• Web services. Concepts, architectures and applications

Cited in

(11)

• Deciding definability by deterministic regular expressions
• Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
• The complexity of SORE-definability problems
• Fast matching of regular patterns with synchronizing counting
• Definability by weakly deterministic regular expressions with counters is decidable
• Checking determinism of regular expressions with counting
• Succinct determinisation of counting automata via sphere construction
• Regular Expressions with Counting: Weak versus Strong Determinism
• Efficient testing and matching of deterministic regular expressions
• Closure properties and descriptional complexity of deterministic regular expressions
• Inclusion Test Algorithms for One-Unambiguous Regular Expressions

Describes a project that uses

Uses Software

• PERL
• Relax NG

This page was built for publication: One-unambiguity of regular expressions with numeric occurrence indicators

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