On the piecewise complexity of words

DOI10.1007/S00236-025-00480-4MaRDI QIDQ7018160zbMATH OpenFDO

Authors Philippe Schnoebelen, Isa Vialard

Publication date 5 March 2025

Published in Acta Informatica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/S00236-025-00480-4

Mathematics Subject Classification ID

Combinatorics on words (68R15) Algorithms on strings (68W32)

Cites work

• A generic polynomial time approach to separation by first-order logic without quantifier alternation
• A SURVEY ON SMALL FRAGMENTS OF FIRST-ORDER LOGIC OVER FINITE WORDS
• Classifying regular events in symbolic logic
• Cognitive and sub-regular complexity
• Deciding piecewise testable separability for regular tree languages
• scientific article; zbMATH DE number 3811868 (Why is no real title available?)
• scientific article; zbMATH DE number 4028925 (Why is no real title available?)
• scientific article; zbMATH DE number 3495598 (Why is no real title available?)
• scientific article; zbMATH DE number 2051146 (Why is no real title available?)
• scientific article; zbMATH DE number 2206109 (Why is no real title available?)
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• Kernel methods for learning languages
• On shuffle products, acyclic automata and piecewise-testable languages
• On the complexity of k-piecewise testability and the depth of automata
• On the index of Simon's congruence for piecewise testability
• Piecewise testable languages via combinatorics on words
• Piecewise testable tree languages
• Scattered Factor-Universality of Words
• Separability by piecewise testable languages and downward closures beyond subwords
• Simon's theorem for scattered words
• Testing Simon's congruence
• The height of piecewise-testable languages with applications in logical complexity

This page was built for publication: On the piecewise complexity of words

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