Generating, sampling and counting subclasses of regular tree languages
From MaRDI portal
Publication:359886
DOI10.1007/s00224-012-9428-xzbMath1270.68145MaRDI QIDQ359886
Wim Martens, Timos Antonopoulos, Frank Neven, Floris Geerts
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
68Q45: Formal languages and automata
68N15: Theory of programming languages
68P20: Information storage and retrieval of data
Uses Software
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
