The Experts below are selected from a list of 306 Experts worldwide ranked by ideXlab platform
Alexander Okhotin - One of the best experts on this subject based on the ideXlab platform.
-
DCFS - On the number of Nonterminal Symbols in unambiguous conjunctive grammars
Descriptional Complexity of Formal Systems, 2012Co-Authors: Artur Jeż, Alexander OkhotinAbstract:It is demonstrated that the family of languages generated by unambiguous conjunctive grammars with 1 Nonterminal Symbol is strictly included in the languages generated by 2-Nonterminal grammars, which is in turn a proper subset of the family generated using 3 or more Nonterminal Symbols. This hierarchy is established by considering grammars over a one-letter alphabet, for which it is shown that 1-Nonterminal grammars generate only regular languages, 2-Nonterminal grammars generate some non-regular languages, but all of them have upper density zero, while 3-Nonterminal grammars may generate some non-regular languages of non-zero density. It is also shown that the equivalence problem for 2-Nonterminal grammars is undecidable.
-
On the expressive power of univariate equations over sets of natural numbers
Information and Computation, 2012Co-Authors: Alexander Okhotin, Panos RondogiannisAbstract:Equations of the form [email protected](X) are considered, where the unknown X is a set of natural numbers. The expression @f(X) may contain the operations of set addition, defined as S+T={m+n|[email protected]?S,[email protected]?T}, union, intersection, as well as ultimately periodic constants. An equation with a non-periodic solution of exponential growth rate is constructed. At the same time it is demonstrated that no sets with super-exponential growth rate can be represented. It is also shown that restricted classes of these equations cannot represent sets with super-linearly growing complements nor sets that are additive bases of order 2. The results have direct implications on the power of unary conjunctive grammars with one Nonterminal Symbol.
-
One-Nonterminal Conjunctive Grammars over a Unary Alphabet
Theory of Computing Systems, 2011Co-Authors: Artur Jeż, Alexander OkhotinAbstract:Conjunctive grammars over an alphabet Σ ={ a } are studied, with the focus on the special case with a unique Nonterminal Symbol. Such a grammar is equivalent to an equation X = ϕ ( X ) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple Nonterminals can be encoded into a grammar with a single Nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-Nonterminal conjunctive grammars over { a } is proved to be EXPTIME-complete; the same problem for the context-free grammars is decidable in NLOGSPACE, but becomes NP-complete if the grammar is compressed as well. The equivalence problem for these grammars is shown to be co-r.e.-complete, both finiteness and co-finiteness are r.e.-complete, while equivalence to a fixed unary language with a regular positional notation is decidable.
-
CSR - One-Nonterminal Conjunctive Grammars over a Unary Alphabet
Computer Science - Theory and Applications, 2009Co-Authors: Artur Jeż, Alexander OkhotinAbstract:Conjunctive grammars over an alphabet Σ = {a } are studied, with the focus on the special case with a unique Nonterminal Symbol. Such a grammar is equivalent to an equation X = φ (X ) over sets of natural numbers, using union, intersection and addition. It is shown that every grammar with multiple Nonterminals can be encoded into a grammar with a single Nonterminal, with a slight modification of the language. Based on this construction, the compressed membership problem for one-Nonterminal conjunctive grammars over {a } is proved to be EXPTIME-complete, while the equivalence, finiteness and emptiness problems for these grammars are shown to be undecidable.
-
On the closure properties of linear conjunctive languages
Theoretical Computer Science, 2003Co-Authors: Alexander OkhotinAbstract:Linear conjunctive grammars are conjunctive grammars in which the body of each conjunct contains no more than a single Nonterminal Symbol. They can at the same time be thought of as a special case of conjunctive grammars and as a generalization of linear context-free grammars that provides an explicit intersection operation.Although the set of languages generated by these grammars is known to include many important noncontext-free languages, linear conjunctive languages are still all square-time, and several practical algorithms have been devised to handle them, which makes this class of grammars quite suitable for use in applications.In this paper we investigate the closure properties of the language family generated by linear conjunctive grammars; the main result is its closure under complement, which implies that it is closed under all set-theoretic operations. We also consider several cases in which the concatenation of two linear conjunctive languages is certain to be linear conjunctive. In addition, it is demonstrated that linear conjunctive languages are closed under quotient with finite languages, not closed under quotient with regular languages, and not closed under ?-free homomorphism.
Masaaki Nagata - One of the best experts on this subject based on the ideXlab platform.
-
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence Statistical Parsing with Probabilistic Symbol-Refined Tree Substitution Grammars ∗
2014Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We present probabilistic Symbol-Refined Tree Substitution Grammars (SR-TSG) for statistical parsing of natural language sentences. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. Our probabilistic model is consistent based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, thus all grammar rules can be learned from training data in a fully automatic fashion. Our SR-TSG parser achieves the state-of-the-art performance on the Wall Street Journal (WSJ) English Penn Treebank data.
-
IJCAI - Statistical parsing with probabilistic Symbol-refined tree substitution grammars
2013Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We present probabilistic Symbol-Refined Tree Substitution Grammars (SR-TSG) for statistical parsing of natural language sentences. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. Our probabilistic model is consistent based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, thus all grammar rules can be learned from training data in a fully automatic fashion. Our SR-TSG parser achieves the state-of-the-art performance on the Wall Street Journal (WSJ) English Penn Tree-bank data.
-
Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing
2013Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We propose Symbol-Refined Tree Substitution Grammars (SR-TSGs) for syntactic parsing. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. We aim to provide a unified model where TSG rules and Symbol refinement are learned from training data in a fully automatic and consistent fashion. We present a novel probabilistic SR-TSG model based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, and develop an efficient training method based on Markov Chain Monte Carlo (MCMC) sampling. Our SR-TSG parser achieves an F1 score of 92.4% in the Wall Street Journal (WSJ) English Penn Treebank parsing task, which is a 7.7 point improvement over a conventional Bayesian TSG parser, and better than state-of-the-art discriminative reranking parsers.
-
ACL (1) - Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing
2012Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We propose Symbol-Refined Tree Substitution Grammars (SR-TSGs) for syntactic parsing. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. We aim to provide a unified model where TSG rules and Symbol refinement are learned from training data in a fully automatic and consistent fashion. We present a novel probabilistic SR-TSG model based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, and develop an efficient training method based on Markov Chain Monte Carlo (MCMC) sampling. Our SR-TSG parser achieves an F1 score of 92.4% in the Wall Street Journal (WSJ) English Penn Treebank parsing task, which is a 7.7 point improvement over a conventional Bayesian TSG parser, and better than state-of-the-art discriminative reranking parsers.
Hiroyuki Shindo - One of the best experts on this subject based on the ideXlab platform.
-
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence Statistical Parsing with Probabilistic Symbol-Refined Tree Substitution Grammars ∗
2014Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We present probabilistic Symbol-Refined Tree Substitution Grammars (SR-TSG) for statistical parsing of natural language sentences. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. Our probabilistic model is consistent based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, thus all grammar rules can be learned from training data in a fully automatic fashion. Our SR-TSG parser achieves the state-of-the-art performance on the Wall Street Journal (WSJ) English Penn Treebank data.
-
IJCAI - Statistical parsing with probabilistic Symbol-refined tree substitution grammars
2013Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We present probabilistic Symbol-Refined Tree Substitution Grammars (SR-TSG) for statistical parsing of natural language sentences. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. Our probabilistic model is consistent based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, thus all grammar rules can be learned from training data in a fully automatic fashion. Our SR-TSG parser achieves the state-of-the-art performance on the Wall Street Journal (WSJ) English Penn Tree-bank data.
-
Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing
2013Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We propose Symbol-Refined Tree Substitution Grammars (SR-TSGs) for syntactic parsing. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. We aim to provide a unified model where TSG rules and Symbol refinement are learned from training data in a fully automatic and consistent fashion. We present a novel probabilistic SR-TSG model based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, and develop an efficient training method based on Markov Chain Monte Carlo (MCMC) sampling. Our SR-TSG parser achieves an F1 score of 92.4% in the Wall Street Journal (WSJ) English Penn Treebank parsing task, which is a 7.7 point improvement over a conventional Bayesian TSG parser, and better than state-of-the-art discriminative reranking parsers.
-
ACL (1) - Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing
2012Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We propose Symbol-Refined Tree Substitution Grammars (SR-TSGs) for syntactic parsing. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. We aim to provide a unified model where TSG rules and Symbol refinement are learned from training data in a fully automatic and consistent fashion. We present a novel probabilistic SR-TSG model based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, and develop an efficient training method based on Markov Chain Monte Carlo (MCMC) sampling. Our SR-TSG parser achieves an F1 score of 92.4% in the Wall Street Journal (WSJ) English Penn Treebank parsing task, which is a 7.7 point improvement over a conventional Bayesian TSG parser, and better than state-of-the-art discriminative reranking parsers.
Alexander Knyazev - One of the best experts on this subject based on the ideXlab platform.
-
on recognition of words from languages generated by linear grammars with one Nonterminal Symbol
Lecture Notes in Computer Science, 1998Co-Authors: Alexander KnyazevAbstract:In this paper we consider the classification of languages generated by linear grammars with one Nonterminal Symbol depending on the minimal depth of decision trees for language word recognition.
-
Rough Sets and Current Trends in Computing - On Recognition of Words from Languages Generated by Linear Grammars with One Nonterminal Symbol
Rough Sets and Current Trends in Computing, 1998Co-Authors: Alexander KnyazevAbstract:In this paper we consider the classification of languages generated by linear grammars with one Nonterminal Symbol depending on the minimal depth of decision trees for language word recognition.
Akinori Fujino - One of the best experts on this subject based on the ideXlab platform.
-
Proceedings of the Twenty-Third International Joint Conference on Artificial Intelligence Statistical Parsing with Probabilistic Symbol-Refined Tree Substitution Grammars ∗
2014Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We present probabilistic Symbol-Refined Tree Substitution Grammars (SR-TSG) for statistical parsing of natural language sentences. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. Our probabilistic model is consistent based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, thus all grammar rules can be learned from training data in a fully automatic fashion. Our SR-TSG parser achieves the state-of-the-art performance on the Wall Street Journal (WSJ) English Penn Treebank data.
-
IJCAI - Statistical parsing with probabilistic Symbol-refined tree substitution grammars
2013Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We present probabilistic Symbol-Refined Tree Substitution Grammars (SR-TSG) for statistical parsing of natural language sentences. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. Our probabilistic model is consistent based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, thus all grammar rules can be learned from training data in a fully automatic fashion. Our SR-TSG parser achieves the state-of-the-art performance on the Wall Street Journal (WSJ) English Penn Tree-bank data.
-
Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing
2013Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We propose Symbol-Refined Tree Substitution Grammars (SR-TSGs) for syntactic parsing. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. We aim to provide a unified model where TSG rules and Symbol refinement are learned from training data in a fully automatic and consistent fashion. We present a novel probabilistic SR-TSG model based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, and develop an efficient training method based on Markov Chain Monte Carlo (MCMC) sampling. Our SR-TSG parser achieves an F1 score of 92.4% in the Wall Street Journal (WSJ) English Penn Treebank parsing task, which is a 7.7 point improvement over a conventional Bayesian TSG parser, and better than state-of-the-art discriminative reranking parsers.
-
ACL (1) - Bayesian Symbol-Refined Tree Substitution Grammars for Syntactic Parsing
2012Co-Authors: Hiroyuki Shindo, Yusuke Miyao, Akinori Fujino, Masaaki NagataAbstract:We propose Symbol-Refined Tree Substitution Grammars (SR-TSGs) for syntactic parsing. An SR-TSG is an extension of the conventional TSG model where each Nonterminal Symbol can be refined (subcategorized) to fit the training data. We aim to provide a unified model where TSG rules and Symbol refinement are learned from training data in a fully automatic and consistent fashion. We present a novel probabilistic SR-TSG model based on the hierarchical Pitman-Yor Process to encode backoff smoothing from a fine-grained SR-TSG to simpler CFG rules, and develop an efficient training method based on Markov Chain Monte Carlo (MCMC) sampling. Our SR-TSG parser achieves an F1 score of 92.4% in the Wall Street Journal (WSJ) English Penn Treebank parsing task, which is a 7.7 point improvement over a conventional Bayesian TSG parser, and better than state-of-the-art discriminative reranking parsers.
