×

Found 396 Documents (Results 1–100)

The big-O problem for labelled Markov chains and weighted automata. (English) Zbl 07559497

Konnov, Igor (ed.) et al., 31st international conference on concurrency theory. CONCUR 2020, September 1–4, 2020, Vienna, Austria, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 171, Article 41, 19 p. (2020).
MSC:  68Q85
PDFBibTeX XMLCite
Full Text: DOI

Decidability of cutpoint isolation for probabilistic finite automata on letter-bounded inputs. (English) Zbl 07559478

Konnov, Igor (ed.) et al., 31st international conference on concurrency theory. CONCUR 2020, September 1–4, 2020, Vienna, Austria, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 171, Article 22, 16 p. (2020).
MSC:  68Q85
PDFBibTeX XMLCite
Full Text: DOI arXiv

Kernels of sub-classes of context-free languages. (English) Zbl 1440.68159

Chatzigeorgiou, Alexander (ed.) et al., SOFSEM 2020: theory and practice of computer science. 46th international conference on current trends in theory and practice of informatics, SOFSEM 2020, Limassol, Cyprus, January 20–24, 2020. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12011, 136-147 (2020).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

A polynomial-time algorithm for the Lambek calculus with brackets of bounded order. (English) Zbl 1434.03076

Miller, Dale (ed.), 2nd international conference on formal structures for computation and deduction. FSCD 2017, Oxford, UK, September 3–9, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 84, Article 22, 17 p. (2017).
PDFBibTeX XMLCite
Full Text: DOI arXiv

On finite-index indexed grammars and their restrictions. (English) Zbl 1485.68127

Drewes, Frank (ed.) et al., Language and automata theory and applications. 11th international conference, LATA 2017, Umeå, Sweden, March 6–9, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10168, 287-298 (2017).
MSC:  68Q42 68Q45
PDFBibTeX XMLCite
Full Text: DOI arXiv

On bounded semilinear languages, counter machines, and finite-index ET0L. (English) Zbl 1475.68156

Han, Yo-Sub (ed.) et al., Implementation and application of automata. 21st international conference, CIAA 2016, Seoul, South Korea, July 19–22, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9705, 138-149 (2016).
MSC:  68Q45 68Q42
PDFBibTeX XMLCite
Full Text: DOI

Descriptional complexity of bounded regular languages. (English) Zbl 1476.68130

Câmpeanu, Cezar (ed.) et al., Descriptional complexity of formal systems. 18th IFIP WG 1.2 international conference, DCFS 2016, Bucharest, Romania, July 5–8, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9777, 138-152 (2016).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI HAL

On the formalization of some results of context-free language theory. (English) Zbl 1478.68133

Väänänen, Jouko (ed.) et al., Logic, language, information, and computation. 23rd international workshop, WoLLIC 2016, Puebla, Mexico, August 16–19th, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9803, 338-357 (2016).
MSC:  68Q45 68Q42 68V20
PDFBibTeX XMLCite
Full Text: DOI Link

On families of full trios containing counter machine languages. (English) Zbl 1436.68173

Brlek, Srečko (ed.) et al., Developments in language theory. 20th international conference, DLT 2016, Montréal, Canada, July 25–28, 2016. Proceedings. Berlin: Springer. Lect. Notes Comput. Sci. 9840, 216-228 (2016).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the density of context-free and counter languages. (English) Zbl 1386.68089

Potapov, Igor (ed.), Developments in language theory. 19th international conference, DLT 2015, Liverpool, UK, July 27–30, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-21499-3/pbk; 978-3-319-21500-6/ebook). Lecture Notes in Computer Science 9168, 228-239 (2015).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI arXiv

On the boundedness property of semilinear sets. (English) Zbl 1382.68135

Chan, T-H. Hubert (ed.) et al., Theory and applications of models of computation. 10th international conference, TAMC 2013, Hong Kong, China, May 20–22, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-38235-2/pbk). Lecture Notes in Computer Science 7876, 156-168 (2013).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

Descriptional complexity of two-way pushdown automata with restricted head reversals. (English) Zbl 1341.68100

Holzer, Markus (ed.) et al., Descriptional complexity of formal systems. 13th international workshop, DCFS 2011, Gießen/Limburg, Germany, July 25–27, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22599-4/pbk). Lecture Notes in Computer Science 6808, 248-260 (2011).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

Extensional uniformity for Boolean circuits. (English) Zbl 1157.68030

Kaminski, Michael (ed.) et al., Computer science logic. 22nd international workshop, CSL 2008, 17th annual conference of the EACSL, Bertinoro, Italy, September 16–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-87530-7/pbk). Lecture Notes in Computer Science 5213, 64-78 (2008).
MSC:  68Q15 68Q19 68Q45 94C10
PDFBibTeX XMLCite
Full Text: DOI arXiv

Finding the growth rate of a regular of context-free language in polynomial time. (English) Zbl 1161.68528

Ito, Masami (ed.) et al., Developments in language theory. 12th international conference, DLT 2008, Kyoto, Japan, September 16–19, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-85779-2/pbk). Lecture Notes in Computer Science 5257, 339-358 (2008).
MSC:  68Q45 68Q25 68Q42
PDFBibTeX XMLCite
Full Text: DOI

Tree automata for non-linear arithmetic. (English) Zbl 1155.68044

Voronkov, Andrei (ed.), Rewriting techniques and applications. 19th international conference, RTA 2008, Hagenberg, Austria, July 15–17, 2008. Proceedings. Berlin: Springer (ISBN 978-3-540-70588-8/pbk). Lecture Notes in Computer Science 5117, 291-305 (2008).
PDFBibTeX XMLCite
Full Text: DOI

Chomsky-Schützenberger type characterizations of poly-slender and Parikh slender context-free languages. (English) Zbl 1263.68099

Moss, Lawrence S. (ed.) et al., Proceedings of the joint meeting of the 6th conference on formal grammar and the 7th conference on mathematics of language, Helsinki, Finland, August 10–12, 2001. Proceedings. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 53, 137-145 (2004).
MSC:  68Q45 68Q70
PDFBibTeX XMLCite
Full Text: DOI

Filter Results by …

Document Type

all top 5

Author

all top 5

Year of Publication

all top 3

Main Field

all top 3

Software