Piecewise testable tree languages

Mikołaj Bojańczyk; Luc Segoufin; Howard Straubing

doi:10.2168/LMCS-8(3:26)2012

Mikołaj Bojańczyk ; Luc Segoufin ; Howard Straubing - Piecewise testable tree languages

lmcs:1216 - Logical Methods in Computer Science, September 29, 2012, Volume 8, Issue 3 - https://doi.org/10.2168/LMCS-8(3:26)2012

Piecewise testable tree languagesArticle

Authors: Mikołaj Bojańczyk ; Luc Segoufin ; Howard Straubing

This paper presents a decidable characterization of tree languages that can be defined by a boolean combination of Sigma_1 sentences. This is a tree extension of the Simon theorem, which says that a string language can be defined by a boolean combination of Sigma_1 sentences if and only if its syntactic monoid is J-trivial.

https://doi.org/10.2168/LMCS-8(3:26)2012

Source: arXiv.org:1208.5129

Volume: Volume 8, Issue 3

Published on: September 29, 2012

Imported on: November 15, 2011

Keywords: Computer Science - Formal Languages and Automata Theory, F.4.3,F.4.1

Licence: arXiv.org - Non-exclusive license to distribute

Funding:

Source : OpenAIRE Graph

SHF: AF: Small: Algebraic Methods for the Study of Logics on Trees; Funder: National Science Foundation; Code: 0915065

Classifications

Mathematics Subject Classification 2020¹

Sources:

[1] zbMATH Open.

Publications

Has review

Review available on zbMATH Open, by Magnus Steinby (Turku) (English)

1 zbMATH Open

Bibliographic References

11 Documents citing this article

Philippe Schnoebelen;Isa Vialard, 2025, On the piecewise complexity of words, Acta Informatica, 62, 1, 10.1007/s00236-025-00480-4.

Philippe Schnoebelen;Julien Veron, arXiv (Cornell University), On Arch Factorization and Subword Universality for Words and Compressed Words, pp. 274-287, 2023, 10.1007/978-3-031-33180-0_21, https://arxiv.org/abs/2304.11932.

Thomas Colcombet;Arthur Jaquard, A Complexity Approach to Tree Algebras: the Bounded Case, 2021, 10.4230/lipics.icalp.2021.127, https://hal.archives-ouvertes.fr/hal-03468240.

Julian Bradfield;Igor Walukiewicz, Springer eBooks, The mu-calculus and Model Checking, pp. 871-919, 2018, 10.1007/978-3-319-10575-8_26.

Michael Hahn;Andreas Krebs;Howard Straubing, arXiv (Cornell University), Wreath Products of Distributive Forest Algebras, pp. 512-520, 2018, Oxford United Kingdom, 10.1145/3209108.3209158, http://arxiv.org/abs/1911.03493.

Tomáš Masopust, 2017, Separability by piecewise testable languages is PTime-complete, Theoretical Computer Science, 711, pp. 109-114, 10.1016/j.tcs.2017.11.004, https://doi.org/10.1016/j.tcs.2017.11.004.

Tomáš Masopust;Markus Krötzsch, Lecture notes in computer science, Deciding Universality of ptNFAs is PSpace-Complete, pp. 413-427, 2017, 10.1007/978-3-319-73117-9_29.

Andreas Krebs;Howard Straubing, Lecture notes in computer science, EF+EX Forest Algebras, pp. 128-139, 2015, 10.1007/978-3-319-23021-4_12.

Mikołaj Bojańczyk, 2014, Automata column, ACM SIGLOG News, 1, 1, pp. 4, 10.1145/2657460.2657462, https://doi.org/10.1145/2657460.2657462.

Galina Jirásková;Tomáš Masopust, Lecture notes in computer science, On the State Complexity of the Reverse of ${\mathcal R}$ - and ${\mathcal J}$ -Trivial Regular Languages, pp. 136-147, 2013, 10.1007/978-3-642-39310-5_14.

Howard Straubing, 2013, New applications of the wreath product of forest algebras, French digital mathematics library (Numdam), 47, 3, pp. 261-291, 10.1051/ita/2013039, http://www.numdam.org/articles/10.1051/ita/2013039/.

Sources : OpenCitations, OpenAlex & Crossref

Share and export

Consultation statistics

This page has been seen 2981 times.

This article's PDF has been downloaded 404 times.