Deterministic Caterpillar Expressions

DOI10.1007/978-3-540-76336-9_11zbMath1139.68374OpenAlexW1598379535MaRDI QIDQ3503898

Jinfeng Zan, Kai Salomaa, Sheng Yu

Publication date: 10 June 2008

Published in: Implementation and Application of Automata (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-76336-9_11

zbMATH Keywords

determinismregular expressionsdecidabilitytree walking automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Related Items (1)

Operational state complexity of nested word automata

Cites Work

• Tree-walking automata cannot be determinized
• Typechecking for XML transformers
• On the power of tree-walking automata.
• Translation of binary regular expressions into nondeterministic \(\varepsilon\)-free automata with \(O(n\log n)\) transitions
• SGML and XML document grammars and exceptions
• Tree-walking automata do not recognize all regular languages
• Computingϵ-Free NFA from Regular Expressions inO(nlog²(n)) Time
• Characterizing regular languages with polynomial densities
• Regular Expressions and NFAs Without ε-Transitions
• Ambiguity in Graphs and Expressions
• One-unambiguous regular languages
• Translating regular expressions into small \(\epsilon\)-free nondeterministic finite automata
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deterministic Caterpillar Expressions