Partially-ordered two-way automata: A new characterization of DA

DOI10.1007/3-540-46011-X_20MaRDI QIDQ4737911zbMATH OpenFDO

Authors Thomas Schwentick, Denis Thérien, Heribert Vollmer

Publication date 11 August 2004

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/2295/22950239.htm

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Algebraic theory of languages and automata (68Q70)

Recommendations

• Partially ordered two-way Büchi automata
• Partially ordered two-way Büchi automata
• scientific article; zbMATH DE number 3911713
• Two-way finite automata: old and recent results
• Two-way finite automata: old and recent results
• On the determinacy problem for two-way pushdown automata
• A note on partially ordered tree automata
• Two-way visibly pushdown automata and transducers
• scientific article; zbMATH DE number 1059319

Cited in

(26)

• The word problem for omega-terms over the Trotter-Weil hierarchy
• On shuffle products, acyclic automata and piecewise-testable languages
• Complexity of universality and related problems for partially ordered NFAs
• On Simon's congruence closure of a string
• State complexity of permutation and related decision problems on alphabetical pattern constraints
• First-order rewritability of ontology-mediated queries in linear temporal logic
• The half-levels of the \(\mathrm {FO}_2\) alternation hierarchy
• Partially ordered two-way Büchi automata
• On FO 2 Quantifier Alternation over Words
• Partially ordered two-way Büchi automata
• Partially ordered automata and piecewise testability
• Testing Simon's congruence
• The Word Problem for Omega-Terms over the Trotter-Weil Hierarchy
• Circuit complexity of regular languages
• Circuit complexity of regular languages
• State Complexity of Permutation and the Language Inclusion Problem up to Parikh Equivalence on Alphabetical Pattern Constraints and Partially Ordered NFAs
• On Simon's congruence closure of a string
• Conelikes and ranker comparisons
• Simon's congruence pattern matching
• Unary and two-variable interval logics
• Asymptotic reasoning with two variables
• Subset mapping problems in solvable automata
• Uniformisation of regular relations in first-order logic with two variables
• Co-lexicographically ordering automata and regular languages. I
• Synchronization of Parikh automata
• Weakly acyclic automata and exponential time hypotheses: universality and related problems

This page was built for publication: Partially-ordered two-way automata: A new characterization of DA

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