Deciding determinism of caterpillar expressions

DOI10.1016/j.tcs.2009.03.010zbMath1194.68146OpenAlexW2020054624MaRDI QIDQ840761

Kai Salomaa, Jinfeng Zan, Sheng Yu

Publication date: 14 September 2009

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.tcs.2009.03.010

zbMATH Keywords

determinismregular expressionsdecidabilitytree-walking automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Tree-walking automata cannot be determinized
• Deterministic generalized automata
• 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
• THE GENERALIZATION OF GENERALIZED AUTOMATA: EXPRESSION AUTOMATA
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Deciding determinism of caterpillar expressions