Generating, sampling and counting subclasses of regular tree languages

DOI10.1007/s00224-012-9428-xzbMath1270.68145OpenAlexW1964169047MaRDI QIDQ359886

Timos Antonopoulos, Floris Geerts, Frank Neven, Wim Martens

Publication date: 23 August 2013

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1942/11703

zbMATH Keywords

complexitycountingXML schema languages

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Theory of programming languages (68N15) Information storage and retrieval of data (68P20)

Related Items

Optimal probabilistic generation of XML documents

Uses Software

• REGAL
• ToXgene

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simplifying XML schema: single-type approximations of regular tree languages
• Succinctness of pattern-based schema languages for XML
• On the minimization of XML schemas and tree automata for unranked trees
• Enumeration and random generation of accessible automata
• The complexity of computing the number of strings of given length in context-free languages
• A calculus for the random generation of labelled combinatorial structures
• A quasi-polynomial-time algorithm for sampling words from a context-free language
• Enumeration and generation with a string automata representation
• Deciding Equivalence of Finite Tree Automata
• The Tractability Frontier for NFA Minimization
• Complexity of Decision Problems for XML Schemas and Chain Regular Expressions
• Random Generation of Deterministic Tree (Walking) Automata
• One-unambiguous regular languages
• Normal form algorithms for extended context-free grammars