It is shown that small fragments of the first-order theory of the subword order, the (partial) lexicographic path ordering on words, the homomorphism preorder, and the infix order are undecidable. This is in contrast to the decidability of the monadic second-order theory of the prefix order [M.O. Rabin, Trans. Amer. Math. Soc., 1969] and of the theory of the total lexicographic path ordering [P. Narendran and M. Rusinowitch, Lect. Notes Artificial Intelligence, 2000] and, in case of the subword...
It is shown that small fragments of the first-order theory of the
subword order, the (partial) lexicographic path ordering on words,
the homomorphism preorder, and the infix order are undecidable. This
is in contrast to the decidability of the monadic second-order
theory of the prefix order [M.O. Rabin, , 1969] and of the theory of the
total lexicographic path ordering [P. Narendran and M. Rusinowitch, , 2000] and, in case of the
subword and the lexicographic path order, improves upon a result...
Since recognizable tree languages are closed under the rational operations, every regular tree expression denotes a recognizable tree language. We provide an alternative proof to this fact that results in smaller tree automata. To this aim, we transfer Antimirov's partial derivatives from regular word expressions to regular tree expressions. For an analysis of the size of the resulting automaton as well as for algorithmic improvements, we also transfer the methods of Champarnaud and Ziadi from words...
Since recognizable tree languages are closed under the rational
operations, every regular tree expression denotes a recognizable
tree language. We provide an alternative proof to this fact that
results in smaller tree automata. To this aim, we transfer
Antimirov's partial derivatives from regular word expressions to
regular tree expressions. For an analysis of the size of the
resulting automaton as well as for algorithmic improvements, we also
transfer the methods of Champarnaud and Ziadi...
Under the assumption that the Polynomial-Time Hierarchy does not collapse
we show for a regular language :
the unbalanced polynomial-time leaf language class determined by
equals iff is existentially but not
quantifierfree definable in FO[<, min, max, +1, −1].
Furthermore, no such
class lies properly between NP and co-1-NP or NP⊕co-NP.
The proofs rely on a result of Pin and Weil
characterizing
the automata of existentially first-order definable languages.
Download Results (CSV)