On the parallel complexity of tree automata

DOI10.1007/3-540-45127-7_16MaRDI QIDQ2778879zbMATH OpenFDO

Authors Markus Lohrey

Publication date 21 March 2002

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL http://link.springer.de/link/service/series/0558/bibs/2051/20510201

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45)

Recommendations

• Another variation on the common subexpression problem
• The parallel complexity of finite-state automata problems
• Complexity of uniform membership of context-free tree grammars
• Parallel complexity of iterated morphisms and the arithmetic of small numbers
• Parameterized complexity of basic decision problems for tree automata

Cited in

(13)

• Inverse monoids: decidability and complexity of algebraic questions.
• Parameterized complexity of basic decision problems for tree automata
• The parameterized complexity of chosen problems for finite automata on trees
• scientific article; zbMATH DE number 4133492 (Why is no real title available?)
• On synchronizing tree automata and their work-optimal parallel run, usable for parallel tree pattern matching
• Grammar-Based Tree Compression
• Monadic Second-Order Logic and Transitive Closure Logics over Trees
• Parallel complexity of iterated morphisms and the arithmetic of small numbers
• A unified method for placing problems in polylogarithmic depth
• Branching automata with costs -- a way of reflecting parallelism in costs
• The complexity of tree automata and XPath on grammar-compressed trees
• Automata for XML -- a survey
• Partially commutative inverse monoids.

This page was built for publication: On the parallel complexity of tree automata

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2778879)