On the public citation graph

Complexity of Decision Problems for XML Schemas and Chain Regular Expressions

0 signed · 93 inferred · view as graph

Inferred edges come from two machine sources: sweeps of open repository metadata (mostly SSRN and Zenodo), and a bulk OpenAlex citation snapshot. Every row below is labelled with the one it came from. Neither is a complete citation index — absence here is not evidence of absence.

Is this your work? Sign in with ORCID and put your name on the claims that are yours.
Claim with ORCID
Reference health. See whether every reference in this work resolves to a known work and none has been retracted — and get a dated CiteStamped badge you can embed.
See reference health

What this work says

Outgoing claims: the papers this work cites, builds on, or argues with.

inferredcites →https://doi.org/10.1006/inco.1997.2688openalex-snapshot
One-Unambiguous Regular Languages
inferredcites →https://doi.org/10.1006/inco.1997.2695openalex-snapshot
One-Unambiguous Regular Languages
inferredcites →https://doi.org/10.1007/3-540-36285-1_21openalex-snapshot
XPath Containment in the Presence of Disjunction, DTDs, and Variables
inferredcites →https://doi.org/10.1007/3-540-45465-9_15openalex-snapshot
Intersection of Regular Languages and Star Hierarchy
inferredcites →https://doi.org/10.1007/3-540-45793-3_2openalex-snapshot
Automata, Logic, and XML
inferredcites →https://doi.org/10.1007/3-540-49257-7_18openalex-snapshot
Index Structures for Path Expressions
inferredcites →https://doi.org/10.1007/978-3-540-24741-8_28openalex-snapshot
XPath with Conditional Axis Relations
inferredcites →https://doi.org/10.1007/978-3-540-28629-5_70openalex-snapshot
Complexity of Decision Problems for Simple Regular Expressions
inferredcites →https://doi.org/10.1007/978-3-540-30570-5_5openalex-snapshot
Which XML Schemas Admit 1-Pass Preorder Typing?
inferredcites →https://doi.org/10.1007/978-3-642-03816-7_32openalex-snapshot
Regular Expressions with Counting: Weak versus Strong Determinism
inferredcites →https://doi.org/10.1007/978-3-662-04880-1openalex-snapshot
The Complexity Theory Companion
inferredcites →https://doi.org/10.1007/bfb0028754openalex-snapshot
On-the-fly analysis of systems with unbounded, lossy FIFO channels
inferredcites →https://doi.org/10.1016/0020-0190(94)00130-8openalex-snapshot
Haskell overloading is DEXPTIME-complete
inferredcites →https://doi.org/10.1016/0022-0000(86)90036-xopenalex-snapshot
Domino-tiling games
inferredcites →https://doi.org/10.1016/b978-012088469-8.50023-1openalex-snapshot
Schema-based Scheduling of Event Processors and Buffer Minimization for Queries on Structured Data Streams
inferredcites →https://doi.org/10.1016/j.ic.2006.12.003openalex-snapshot
One-unambiguity of regular expressions with numeric occurrence indicators
inferredcites →https://doi.org/10.1016/j.jcss.2006.10.003openalex-snapshot
Automata for XML—A survey
inferredcites →https://doi.org/10.1016/j.tcs.2004.10.035openalex-snapshot
On the complexity of typechecking top-down XML transformations
inferredcites →https://doi.org/10.1016/s0022-0000(02)00030-2openalex-snapshot
Typechecking for XML transformers
inferredcites →https://doi.org/10.1016/s0022-0000(76)80038-4openalex-snapshot
On the equivalence, containment, and covering problems for the regular and context-free languages
inferredcites →https://doi.org/10.1016/s0304-3975(00)00294-2openalex-snapshot
Normal form algorithms for extended context-free grammars
inferredcites →https://doi.org/10.1023/b:form.0000033962.51898.1aopenalex-snapshot
Using Forward Reachability Analysis for Verification of Lossy Channel Systems
inferredcites →https://doi.org/10.1109/ideas.2003.1214930openalex-snapshot
Effective schema-based XML query optimization techniques
inferredcites →https://doi.org/10.1109/sfcs.1977.16openalex-snapshot
Lower bounds for natural proof systems
inferredcites →https://doi.org/10.1137/0219027openalex-snapshot
Deciding Equivalence of Finite Tree Automata
inferredcites →https://doi.org/10.1137/070697367openalex-snapshot
Optimizing Schema Languages for XML: Numerical Constraints and Interleaving
inferredcites →https://doi.org/10.1145/1017074.1017095openalex-snapshot
DTDs versus XML schema
inferredcites →https://doi.org/10.1145/1060745.1060848openalex-snapshot
Expressiveness of XSDs
inferredcites →https://doi.org/10.1145/1065167.1065172openalex-snapshot
XPath satisfiability in the presence of DTDs
inferredcites →https://doi.org/10.1145/1111627.1111631openalex-snapshot
Taxonomy of XML schema languages using formal language theory
inferredcites →https://doi.org/10.1145/1166074.1166076openalex-snapshot
Expressiveness and complexity of XML Schema
inferredcites →https://doi.org/10.1145/304181.304220openalex-snapshot
Storing semistructured data with STORED
inferredcites →https://doi.org/10.1145/335168.335173openalex-snapshot
DTD inference for views of XML data
inferredcites →https://doi.org/10.1145/375551.375554openalex-snapshot
A Web Odyssey
inferredcites →https://doi.org/10.1145/767193.767195openalex-snapshot
XDuce
inferredcites →https://doi.org/10.1145/776985.776999openalex-snapshot
A Web odyssey
inferredcites →https://doi.org/10.1145/800125.804029openalex-snapshot
Word problems requiring exponential time(Preliminary Report)
inferredcites →https://doi.org/10.1145/959060.959076openalex-snapshot
Reasoning on regular path queries
inferredcites →https://doi.org/10.1145/962446.962448openalex-snapshot
Containment and equivalence for a fragment of XPath
inferredcites →https://doi.org/10.1162/109966200750410613openalex-snapshot
Caterpillars: a context specification technique
inferredcites →https://doi.org/10.1201/9781420090512-18openalex-snapshot
A Extensible Markup Language XML
inferredcites →https://doi.org/10.2168/lmcs-2(3:2)2006openalex-snapshot
Logics for Unranked Trees: An Overview
inferredcites →https://doi.org/10.4213/rmopenalex-snapshot
Успехи математических наук
inferredcites →https://doi.org/10.5555/1182635.1164139openalex-snapshot
Inference of concise DTDs from XML data
inferredcites →https://doi.org/10.5860/choice.39-0923openalex-snapshot
Bioinformatics: sequence and genome analysis

What points at this work

Incoming claims: where this work appears in other papers’ reference lists and arguments.

inferred← citeshttps://doi.org/10.1007/978-3-030-00847-5_43openalex-snapshot
Learning Restricted Regular Expressions with Interleaving from XML Data
inferred← citeshttps://doi.org/10.1007/978-3-030-32505-3_14openalex-snapshot
Context-Free Grammars for Deterministic Regular Expressions with Interleaving
inferred← citeshttps://doi.org/10.1007/978-3-030-33223-5_22openalex-snapshot
Learning k-Occurrence Regular Expressions from Positive and Negative Samples
inferred← citeshttps://doi.org/10.1007/978-3-030-47436-2_58openalex-snapshot
Inferring Restricted Regular Expressions with Interleaving from Positive and Negative Samples
inferred← citeshttps://doi.org/10.1007/978-3-031-06678-8_29openalex-snapshot
Learning from Positive and Negative Examples: Dichotomies and Parameterized Algorithms
inferred← citeshttps://doi.org/10.1007/978-3-319-08867-9_14openalex-snapshot
Symbolic Visibly Pushdown Automata
inferred← citeshttps://doi.org/10.1007/978-3-319-45817-5_29openalex-snapshot
Practical Study of Subclasses of Regular Expressions in DTD and XML Schema
inferred← citeshttps://doi.org/10.1007/978-3-319-93037-4_31openalex-snapshot
Inference of a Concise Regular Expression Considering Interleaving from XML Documents
inferred← citeshttps://doi.org/10.1007/978-3-319-96893-3_4openalex-snapshot
Inferring Regular Expressions with Interleaving from XML Data
inferred← citeshttps://doi.org/10.1007/978-3-540-88282-4_18openalex-snapshot
Efficient Inclusion Checking for Deterministic Tree Automata and DTDs
inferred← citeshttps://doi.org/10.1007/978-3-642-21254-3_10openalex-snapshot
Recognizing Shuffled Languages
inferred← citeshttps://doi.org/10.1007/978-3-642-28472-4_2openalex-snapshot
Foundations of XML Based on Logic and Automata: A Snapshot
inferred← citeshttps://doi.org/10.1007/s00224-012-9428-xopenalex-snapshot
Generating, Sampling and Counting Subclasses of Regular Tree Languages
inferred← citeshttps://doi.org/10.1007/s00224-014-9559-3openalex-snapshot
Fast Learning of Restricted Regular Expressions and DTDs
inferred← citeshttps://doi.org/10.1007/s00224-014-9593-1openalex-snapshot
Schemas for Unordered XML on a DIME
inferred← citeshttps://doi.org/10.1007/s00224-015-9623-7openalex-snapshot
Deciding Twig-definability of Node Selecting Tree Automata
inferred← citeshttps://doi.org/10.1007/s00224-016-9682-4openalex-snapshot
Games for Active XML Revisited
inferred← citeshttps://doi.org/10.1007/s00236-016-0282-1openalex-snapshot
Conjunctive query containment over trees using schema information
inferred← citeshttps://doi.org/10.1016/j.ic.2017.06.004openalex-snapshot
Complexity of universality and related problems for partially ordered NFAs
inferred← citeshttps://doi.org/10.1016/j.jcss.2011.02.003openalex-snapshot
Distributed XML design
inferred← citeshttps://doi.org/10.1016/j.jcss.2013.01.009openalex-snapshot
Simplifying XML Schema: Single-type approximations of regular tree languages
inferred← citeshttps://doi.org/10.1016/j.jcss.2019.04.001openalex-snapshot
Deterministic regular expressions with back-references
inferred← citeshttps://doi.org/10.1016/j.scico.2020.102436openalex-snapshot
Inclusion algorithms for one-unambiguous regular expressions and their applications
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.04.022openalex-snapshot
Shuffled languages—Representation and recognition
inferred← citeshttps://doi.org/10.1016/j.tcs.2013.04.023openalex-snapshot
Efficient asymmetric inclusion of regular expressions with interleaving and counting for XML type-checking
inferred← citeshttps://doi.org/10.1145/1559795.1559833openalex-snapshot
Distributed XML design
inferred← citeshttps://doi.org/10.1145/1807085.1807117openalex-snapshot
Schema design for XML repositories
inferred← citeshttps://doi.org/10.1145/1807085.1807118openalex-snapshot
Simplifying XML schema
inferred← citeshttps://doi.org/10.1145/1938551.1938559openalex-snapshot
Generating, sampling and counting subclasses of regular tree languages
inferred← citeshttps://doi.org/10.1145/1989284.1989316openalex-snapshot
The complexity of text-preserving XML transformations
inferred← citeshttps://doi.org/10.1145/2071368.2071372openalex-snapshot
Succinctness of the Complement and Intersection of Regular Expressions
inferred← citeshttps://doi.org/10.1145/2213556.2213573openalex-snapshot
The complexity of evaluating path expressions in SPARQL
inferred← citeshttps://doi.org/10.1145/2213598.2213609openalex-snapshot
Foundations of regular expressions in XML schema languages and SPARQL
inferred← citeshttps://doi.org/10.1145/2274576.2274584openalex-snapshot
Deciding twig-definability of node selecting tree automata
inferred← citeshttps://doi.org/10.1145/2448496.2448504openalex-snapshot
Fast learning of restricted regular expressions and DTDs
inferred← citeshttps://doi.org/10.1145/2483574.2483576openalex-snapshot
Learning queries for relational, semi-structured, and graph databases
inferred← citeshttps://doi.org/10.1145/2494529openalex-snapshot
The complexity of regular expressions and property paths in SPARQL
inferred← citeshttps://doi.org/10.1145/2745754.2745766openalex-snapshot
The (Almost) Complete Guide to Tree Pattern Containment
inferred← citeshttps://doi.org/10.1145/2806416.2806434openalex-snapshot
Efficient Incremental Evaluation of Succinct Regular Expressions
inferred← citeshttps://doi.org/10.1145/2898995openalex-snapshot
Bounded Repairability for Regular Tree Languages
inferred← citeshttps://doi.org/10.1145/3294052.3319684openalex-snapshot
Split-Correctness in Information Extraction
inferred← citeshttps://doi.org/10.1145/3331076.3331100openalex-snapshot
An effective algorithm for learning single occurrence regular expressions with interleaving
inferred← citeshttps://doi.org/10.1145/3632891openalex-snapshot
Validation of Modern JSON Schema: Formalization and Complexity
inferred← citeshttps://doi.org/10.1145/3799416openalex-snapshot
Witness Generation for Classical JSON Schema
inferred← citeshttps://doi.org/10.23638/lmcs-17(2:14)2021openalex-snapshot
Partially Ordered Automata and Piecewise Testability
inferred← citeshttps://doi.org/10.4242/balisagevol5.stuhrenberg01openalex-snapshot
Refining the Taxonomy of XML Schema Languages. A new Approach for Categorizing XML Schema Languages in Terms of Processing Complexity.
inferred← citeshttps://doi.org/10.48550/arxiv.1303.4277openalex-snapshot
Simple Schemas for Unordered XML
inferred← citeshttps://doi.org/10.48550/arxiv.1707.00827openalex-snapshot
Document Spanners for Extracting Incomplete Information: Expressiveness and Complexity
Editorial review for independent work. ICSAC — the Institute for Complexity Science and Advanced Computing — runs a structured editorial panel for researchers publishing outside journals, and publishes on CiteStamp rails. Submission is free and goes through ORCID: icsacinstitute.org/submit.