Alternative automata characterization of piecewise testable languages

DOI10.1007/978-3-642-38771-5_26MaRDI QIDQ5300848zbMATH OpenOpenAlexFDO

Authors Ondřej Klíma, Libor Polák

Publication date 28 June 2013

Published in Developments in Language Theory (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-38771-5_26

zbMATH Keywords

piecewise testable languagesacyclic automatalocally confluent automata

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Recommendations

• On the complexity of \(k\)-piecewise testability and the depth of automata
• Biautomata for \(k\)-piecewise testable languages
• Piecewise testable languages and nondeterministic automata
• Piecewise testable languages via combinatorics on words
• scientific article; zbMATH DE number 1839456

Cited in

(18)

• Testing Simon's congruence
• On shuffle products, acyclic automata and piecewise-testable languages
• Tribute: The influence of Imre Simon's work in the theory of automata, languages and semigroups
• On languages piecewise testable in the strict sense
• Biautomata for \(k\)-piecewise testable languages
• Obituary: Libor Polák (1950--2020)
• On the index of Simon's congruence for piecewise testability
• On Boolean combinations forming piecewise testable languages
• Complexity of universality and related problems for partially ordered NFAs
• On the Simon's congruence neighborhood of languages
• Characterizations of some classes of regular events
• scientific article; zbMATH DE number 7350780 (Why is no real title available?)
• scientific article; zbMATH DE number 7056230 (Why is no real title available?)
• Piecewise testable languages via combinatorics on words
• Separability by piecewise testable languages is \textsc{PTime}-complete
• Learning from positive and negative examples: dichotomies and parameterized algorithms
• On the complexity of \(k\)-piecewise testability and the depth of automata
• Piecewise testable languages and nondeterministic automata

This page was built for publication: Alternative automata characterization of piecewise testable languages

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