Search

Your search keyword '"Shallit, Jeffrey"' showing total 11 results
Start Over Author "Shallit, Jeffrey" Topic formal language

Refine your results

more »

more »

11 results on '"Shallit, Jeffrey"'

1. Factorization in Formal Languages

Author

Bell, Paul C., Reidenbach, Daniel, Shallit, Jeffrey, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, and Potapov, Igor, editor

Published
2015
Full Text
View/download PDF

2. Closures in Formal Languages and Kuratowski’s Theorem

Author

Brzozowski, Janusz, Grant, Elyot, Shallit, Jeffrey, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Nierstrasz, Oscar, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Sudan, Madhu, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Vardi, Moshe Y., Series editor, Weikum, Gerhard, Series editor, Diekert, Volker, editor, and Nowotka, Dirk, editor

Published
2009
Full Text
View/download PDF

3. Finite Automata, Palindromes, Powers, and Patterns

Author

Anderson, Terry, Rampersad, Narad, Santean, Nicolae, Shallit, Jeffrey, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Doug, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Martín-Vide, Carlos, editor, Otto, Friedrich, editor, and Fernau, Henning, editor

Published
2008
Full Text
View/download PDF

4. State Complexity and the Monoid of Transformations of a Finite Set

Author

Krawetz, Bryan, Lawrence, John, Shallit, Jeffrey, Hutchison, David, editor, Kanade, Takeo, editor, Kittler, Josef, editor, Kleinberg, Jon M., editor, Mattern, Friedemann, editor, Mitchell, John C., editor, Naor, Moni, editor, Nierstrasz, Oscar, editor, Pandu Rangan, C., editor, Steffen, Bernhard, editor, Sudan, Madhu, editor, Terzopoulos, Demetri, editor, Tygar, Dough, editor, Vardi, Moshe Y., editor, Weikum, Gerhard, editor, Domaratzki, Michael, editor, Okhotin, Alexander, editor, Salomaa, Kai, editor, and Yu, Sheng, editor

Published
2005
Full Text
View/download PDF

5. Minimal Covers of Formal Languages

Author

Domaratzki, Michael, Shallit, Jeffrey, Yu, Sheng, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Kuich, Werner, editor, Rozenberg, Grzegorz, editor, and Salomaa, Arto, editor

Published
2002
Full Text
View/download PDF

6. Variations on a Theorem of Fine & Wilf

Author

Mignosi, Filippo, Shallit, Jeffrey, Wang, Ming-wei, Goos, Gerhard, editor, Hartmanis, Juris, editor, van Leeuwen, Jan, editor, Sgall, Jiří, editor, Pultr, Aleš, editor, and Kolman, Petr, editor

Published
2001
Full Text
View/download PDF

7. Additive Number Theory via Approximation by Regular Languages.

Author

Bell, Jason, Lidbetter, Thomas F., and Shallit, Jeffrey

Subjects
NUMBER theory, APPROXIMATION theory, FORMAL languages, PHILOSOPHY of language, NATURAL numbers
Abstract

We prove some new theorems in additive number theory, using novel techniques from automata theory and formal languages. As an example of our method, we prove that every natural number > 2 5 is the sum of at most three natural numbers whose base- 2 representation has an equal number of 0 's and 1 's. [ABSTRACT FROM AUTHOR]

Published
2020
Full Text
View/download PDF

8. Composition and orbits of language operations: finiteness and upper bounds.

Author

Charlier, Émilie, Domaratzki, Mike, Harju, Tero, and Shallit, Jeffrey

Subjects
MATHEMATICAL bounds, FORMAL languages, COMPOSITION (Language arts), SUFFIXES & prefixes (Grammar), MATHEMATICAL proofs, NUMBER theory, MONOIDS, EQUIVALENCE classes (Set theory)
Abstract

We consider a set of eight natural operations on formal languages (Kleene closure, positive closure, complement, prefix, suffix, factor, subword, and reversal), and compositions of them. Ifxandyare compositions, we sayxis equivalent toyif they have the same effect on all languagesL. We prove that the number of equivalence classes of these eight operations is finite. This implies that the orbit of any languageLunder the elements of the monoid is finite and bounded, independent ofL. This generalizes previous results about complement, Kleene closure, and positive closure. We also estimate the number of distinct languages generated by various subsets of these operations. [ABSTRACT FROM AUTHOR]

Published
2013
Full Text
View/download PDF

9. Filtrations of Formal Languages by Arithmetic Progressions.

Author

Mousavi, Hamoon and Shallit, Jeffrey

Subjects
*FORMAL languages, *ARITHMETIC series, *MATHEMATICAL bounds, *COMPUTATIONAL complexity, *DATA mining, *MATHEMATICAL sequences, *MACHINE theory
Abstract

A filtration of a formal language L by a sequence s maps L to the set of words formed by taking the letters of words of L indexed only by s. We consider the languages resulting from filtering by all arithmetic progressions. If L is regular, it is easy to see that only finitely many distinct languages result; we give bounds on the number of distinct languages in terms of the state complexity of L. By contrast, there exist CFL's that give infinitely many distinct languages as a result. We use our technique to show that two related operations, including diag (which extracts the diagonal of words of square length arranged in a square array), preserve regularity but do not preserve context-freeness. [ABSTRACT FROM AUTHOR]

Published
2013
Full Text
View/download PDF

10. CLOSURES IN FORMAL LANGUAGES AND KURATOWSKI'S THEOREM.

Author

BRZOZOWSKI, JANUSZ, GRANT, ELYOT, SHALLIT, JEFFREY, Diekert, Volker, and Nowotka, Dirk

Subjects
FORMAL languages, CLOSURE operators, TOPOLOGICAL spaces, KLEENE algebra, PARTITIONS (Mathematics), QUADRATIC programming, DECISION making
Abstract

A famous theorem of Kuratowski states that, in a topological space, at most 14 distinct sets can be produced by repeatedly applying the operations of closure and complement to a given set. We re-examine this theorem in the setting of formal languages, where by "closure" we mean either Kleene closure or positive closure. We classify languages according to the structure of the algebras they generate under iterations of complement and closure. There are precisely 9 such algebras in the case of positive closure, and 12 in the case of Kleene closure. We study how the properties of being open and closed are preserved under concatenation. We investigate analogues, in formal languages, of the separation axioms in topological spaces; one of our main results is that there is a clopen partition separating two words if and only if the words do not commute. We can decide in quadratic time if the language specified by a DFA is closed, but if the language is specified by an NFA, the problem is PSPACE-complete. [ABSTRACT FROM AUTHOR]

Published
2011
Full Text
View/download PDF

11. Prefix-Free Subsets of Regular Languages and Descriptional Complexity

Author

Jirásek, Jozef Štefan, Šebej, Juraj, Hutchison, David, Series editor, Kanade, Takeo, Series editor, Kittler, Josef, Series editor, Kleinberg, Jon M., Series editor, Mattern, Friedemann, Series editor, Mitchell, John C., Series editor, Naor, Moni, Series editor, Pandu Rangan, C., Series editor, Steffen, Bernhard, Series editor, Terzopoulos, Demetri, Series editor, Tygar, Doug, Series editor, Weikum, Gerhard, Series editor, Shallit, Jeffrey, editor, and Okhotin, Alexander, editor

Published
2015
Full Text
View/download PDF

Catalog

Books, media, physical & digital resources
See catalog results