Document

**Published in:** LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

A parallel algorithm for enumerating parse trees of a given string according to a fixed context-free grammar is defined. The algorithm computes the number of parse trees of an input string; more generally, it applies to computing the weight of a string in a weighted grammar. The algorithm is first implemented on an arithmetic circuit of depth O((log n)²) with O(n⁶) elements. Then, it is improved using fast matrix multiplication to use only O(n^5.38) elements, while preserving depth O((log n)²).

Margarita Mikhelson and Alexander Okhotin. Parallel Enumeration of Parse Trees. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 67:1-67:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{mikhelson_et_al:LIPIcs.MFCS.2023.67, author = {Mikhelson, Margarita and Okhotin, Alexander}, title = {{Parallel Enumeration of Parse Trees}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {67:1--67:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.67}, URN = {urn:nbn:de:0030-drops-186016}, doi = {10.4230/LIPIcs.MFCS.2023.67}, annote = {Keywords: Context-free grammars, weighted grammars, parsing, parallel algorithms, matrix multiplication} }

Document

**Published in:** LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

A probabilistic variant of input-driven pushdown automata (IDPDA), also known as visibly pushdown automata, is introduced. It is proved that these automata can be determinized: an n-state probabilistic IDPDA that accepts each string with probability at least λ+δ or at most λ-δ is transformed to a deterministic IDPDA with at most (1 + 1/δ)^(n² - n) states recognizing the same language. An asymptotically close lower bound is provided: for infinitely many n, there is a probabilistic IDPDA with 4n + 1 states and δ = 1/(270n), such that every equivalent deterministic IDPDA needs at least 7^(n²/14) states. A few special cases of automata with reduced determinization complexity are identified.

Alex Rose and Alexander Okhotin. Probabilistic Input-Driven Pushdown Automata. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 78:1-78:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{rose_et_al:LIPIcs.MFCS.2023.78, author = {Rose, Alex and Okhotin, Alexander}, title = {{Probabilistic Input-Driven Pushdown Automata}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {78:1--78:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.78}, URN = {urn:nbn:de:0030-drops-186120}, doi = {10.4230/LIPIcs.MFCS.2023.78}, annote = {Keywords: Finite automata, probabilistic automata, input-driven automata, visibly pushdown automata, state complexity} }

Document

**Published in:** LIPIcs, Volume 187, 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)

Graph-walking automata (GWA) traverse graphs by moving between the nodes following the edges, using a finite-state control to decide where to go next. It is known that every GWA can be transformed to a GWA that halts on every input, to a GWA returning to the initial node in order to accept, as well as to a reversible GWA. This paper establishes lower bounds on the state blow-up of these transformations: it is shown that making an n-state GWA traversing k-ary graphs return to the initial node requires at least 2(n-1)(k-3) states in the worst case; the same lower bound holds for the transformation to halting automata. Automata satisfying both properties at once must have at least 4(n-1)(k-3) states. A reversible automaton must have at least 4(n-1)(k-3)-1 states. These bounds are asymptotically tight to the upper bounds proved using the methods from the literature.

Olga Martynova and Alexander Okhotin. Lower Bounds for Graph-Walking Automata. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 187, pp. 52:1-52:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{martynova_et_al:LIPIcs.STACS.2021.52, author = {Martynova, Olga and Okhotin, Alexander}, title = {{Lower Bounds for Graph-Walking Automata}}, booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)}, pages = {52:1--52:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-180-1}, ISSN = {1868-8969}, year = {2021}, volume = {187}, editor = {Bl\"{a}ser, Markus and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2021.52}, URN = {urn:nbn:de:0030-drops-136974}, doi = {10.4230/LIPIcs.STACS.2021.52}, annote = {Keywords: Finite automata, graph-walking automata, halting, reversibility} }

Document

**Published in:** LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)

The partial string avoidability problem, also known as partial word avoidability, is stated as follows: given a finite set of strings with possible ``holes'' (undefined symbols), determine whether there exists any two-sided infinite string containing no substrings from this set, assuming that a hole matches every symbol.
The problem is known to be NP-hard and in PSPACE, and this paper establishes its PSPACE-completeness.
Next, string avoidability over the binary alphabet is interpreted as a version of conjunctive normal form (CNF) satisfiability problem (SAT), with each clause having infinitely many shifted variants.
Non-satisfiability of these formulas can be proved using variants of classical propositional proof systems, augmented with derivation rules for shifting constraints (such as clauses, inequalities, polynomials, etc).
Two results on their proof complexity are established.
First, there is a particular formula that has a short refutation in Resolution with shift, but requires classical proofs of exponential size (Resolution, Cutting Plane, Polynomial Calculus, etc.).
At the same time, exponential lower bounds for shifted versions of classical proof systems are established.

Dmitry Itsykson, Alexander Okhotin, and Vsevolod Oparin. Computational and Proof Complexity of Partial String Avoidability. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 51:1-51:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{itsykson_et_al:LIPIcs.MFCS.2016.51, author = {Itsykson, Dmitry and Okhotin, Alexander and Oparin, Vsevolod}, title = {{Computational and Proof Complexity of Partial String Avoidability}}, booktitle = {41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)}, pages = {51:1--51:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-016-3}, ISSN = {1868-8969}, year = {2016}, volume = {58}, editor = {Faliszewski, Piotr and Muscholl, Anca and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.51}, URN = {urn:nbn:de:0030-drops-64637}, doi = {10.4230/LIPIcs.MFCS.2016.51}, annote = {Keywords: partial strings, partial words, avoidability, proof complexity, PSPACE-completeness} }

Document

**Published in:** Dagstuhl Seminar Proceedings, Volume 10501, Advances and Applications of Automata on Words and Trees (2011)

In contrast to context-free grammars, the extension of these
grammars by explicit conjunction, the so-called conjunctive
grammars can generate (quite complicated) non-regular languages
over a single-letter alphabet (DLT 2007). Given these
expressibility results, we study the parsability of Boolean grammars,
an extension of context-free grammars by conjunction and negation,
over a unary alphabet and show that they can be parsed in time O(|G| log^2(n) M(n))
where M(n) is the time to multiply two n-bit integers. This multiplication
algorithm is transformed into a convolution algorithm which in turn is
converted to an online convolution algorithm which is used for the parsing.

Alexander Okhotin and Christian Reitwießner. Parsing Unary Boolean Grammars Using Online Convolution. In Advances and Applications of Automata on Words and Trees. Dagstuhl Seminar Proceedings, Volume 10501, pp. 1-11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{okhotin_et_al:DagSemProc.10501.3, author = {Okhotin, Alexander and Reitwie{\ss}ner, Christian}, title = {{Parsing Unary Boolean Grammars Using Online Convolution}}, booktitle = {Advances and Applications of Automata on Words and Trees}, pages = {1--11}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2011}, volume = {10501}, editor = {Christian Glasser and Jean-Eric Pin and Nicole Schweikardt and Victor Selivanov and Wolfgang Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10501.3}, URN = {urn:nbn:de:0030-drops-31465}, doi = {10.4230/DagSemProc.10501.3}, annote = {Keywords: } }

Document

**Published in:** LIPIcs, Volume 5, 27th International Symposium on Theoretical Aspects of Computer Science (2010)

Systems of equations with sets of integers as unknowns are considered.
It is shown that the class of sets representable by unique solutions of equations using the operations of union and addition $S+T=\makeset{m+n}{m \in S, \: n \in T}$ and with ultimately periodic constants is exactly the class of hyper-arithmetical sets.
Equations using addition only can represent every hyper-arithmetical set under a simple encoding. All hyper-arithmetical sets can also be represented by equations over sets of natural numbers equipped with union, addition and subtraction $S \dotminus T=\makeset{m-n}{m \in S, \: n \in T, \: m \geqslant n}$. Testing whether a given system has a solution is $\Sigma^1_1$-complete for each model. These results, in particular, settle the expressive power of the most general types of language equations, as well as equations over subsets of free groups.

Artur Jez and Alexander Okhotin. On Equations over Sets of Integers. In 27th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 5, pp. 477-488, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2010.2478, author = {Jez, Artur and Okhotin, Alexander}, title = {{On Equations over Sets of Integers}}, booktitle = {27th International Symposium on Theoretical Aspects of Computer Science}, pages = {477--488}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-16-3}, ISSN = {1868-8969}, year = {2010}, volume = {5}, editor = {Marion, Jean-Yves and Schwentick, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2010.2478}, URN = {urn:nbn:de:0030-drops-24780}, doi = {10.4230/LIPIcs.STACS.2010.2478}, annote = {Keywords: Language equations, computability, arithmetical hierarchy, hyper-arithmetical hierarchy} }

Document

**Published in:** LIPIcs, Volume 3, 26th International Symposium on Theoretical Aspects of Computer Science (2009)

Systems of equations of the form $X=YZ$ and $X=C$ are considered, in which the unknowns are sets of natural numbers, ``$+$'' denotes pairwise sum of sets $S+T=\ensuremath{ \{ m+n \: | \: m \in S, \; n \in T \} }$, and $C$ is an ultimately periodic constant. It is shown that such systems are computationally universal, in the sense that for every recursive (r.e., co-r.e.) set $S \subseteq \mathbb{N}$ there exists a system with a unique (least, greatest) solution containing a component $T$ with $S=\ensuremath{ \{ n \: | \: 16n+13 \in T \} }$. This implies undecidability of basic properties of these equations. All results also apply to language equations over a one-letter alphabet with concatenation and regular constants.

Artur Jez and Alexander Okhotin. Equations over Sets of Natural Numbers with Addition Only. In 26th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 3, pp. 577-588, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2009)

Copy BibTex To Clipboard

@InProceedings{jez_et_al:LIPIcs.STACS.2009.1806, author = {Jez, Artur and Okhotin, Alexander}, title = {{Equations over Sets of Natural Numbers with Addition Only}}, booktitle = {26th International Symposium on Theoretical Aspects of Computer Science}, pages = {577--588}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-09-5}, ISSN = {1868-8969}, year = {2009}, volume = {3}, editor = {Albers, Susanne and Marion, Jean-Yves}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2009.1806}, URN = {urn:nbn:de:0030-drops-18061}, doi = {10.4230/LIPIcs.STACS.2009.1806}, annote = {Keywords: } }

Document

**Published in:** LIPIcs, Volume 1, 25th International Symposium on Theoretical Aspects of Computer Science (2008)

Systems of equations over sets of natural numbers (or,
equivalently, language equations over a one-letter alphabet) of the
form $X_i=varphi_i(X_1, ldots, X_n)$ ($1 leqslant i leqslant
n$) are considered. Expressions $varphi_i$ may contain the
operations of union, intersection and pairwise sum $A plus B = {x
+ y mid x in A, y in B$. A system with an EXPTIME-complete
least solution is constructed, and it is established that least
solutions of all such systems are in EXPTIME. The general
membership problem for these equations is proved to be
EXPTIME-complete.

Alexander Okhotin and Artur Jez. Complexity of solutions of equations over sets of natural numbers. In 25th International Symposium on Theoretical Aspects of Computer Science. Leibniz International Proceedings in Informatics (LIPIcs), Volume 1, pp. 373-384, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2008)

Copy BibTex To Clipboard

@InProceedings{okhotin_et_al:LIPIcs.STACS.2008.1319, author = {Okhotin, Alexander and Jez, Artur}, title = {{Complexity of solutions of equations over sets of natural numbers}}, booktitle = {25th International Symposium on Theoretical Aspects of Computer Science}, pages = {373--384}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-06-4}, ISSN = {1868-8969}, year = {2008}, volume = {1}, editor = {Albers, Susanne and Weil, Pascal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2008.1319}, URN = {urn:nbn:de:0030-drops-13194}, doi = {10.4230/LIPIcs.STACS.2008.1319}, annote = {Keywords: } }

X

Feedback for Dagstuhl Publishing

Feedback submitted

Please try again later or send an E-mail