×

Found 146 Documents (Results 1–100)

Operational complexity in subregular classes. (English) Zbl 07810931

Nagy, Benedek (ed.), Implementation and application of automata. 27th international conference, CIAA 2023, Famagusta, North Cyprus, September 19–22, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 14151, 153-165 (2023).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

Operational complexity: NFA-to-DFA trade-off. (English) Zbl 07729459

Bordihn, Henning (ed.) et al., Descriptional complexity of formal systems. 25th IFIP WG 1.02 international conference, DCFS 2023, Potsdam, Germany, July 4–6, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13918, 79-93 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Operational state complexity revisited: the contribution of monsters and modifiers. (English) Zbl 07729454

Bordihn, Henning (ed.) et al., Descriptional complexity of formal systems. 25th IFIP WG 1.02 international conference, DCFS 2023, Potsdam, Germany, July 4–6, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13918, 1-20 (2023).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI

Formal methods for NFA equivalence: QBFs, witness extraction, and encoding verification. (English) Zbl 07691303

Buzzard, Kevin (ed.) et al., Intelligent computer mathematics. 15th international conference, CICM 2022, Tbilisi, Georgia, September 19–23, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13467, 241-255 (2022).
MSC:  68Vxx
PDFBibTeX XMLCite
Full Text: DOI

State complexity investigations on commutative languages – the upward and downward closure, commutative aperiodic and commutative group languages. (English) Zbl 07614742

Han, Yo-Sub (ed.) et al., Descriptional complexity of formal systems. 23rd IFIP WG 1.02 international conference, DCFS 2021, virtual event, September 5, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13037, 64-75 (2021).
MSC:  68Qxx
PDFBibTeX XMLCite
Full Text: DOI arXiv

Complexity of proper prefix-convex regular languages. (English) Zbl 1429.68100

Carayol, Arnaud (ed.) et al., Implementation and application of automata. 22nd international conference, CIAA 2017, Marne-la-Vallée, France, June 27–30, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10329, 52-63 (2017).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI Link

The degree of irreversibility in deterministic finite automata. (English) Zbl 1379.68210

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 (ISBN 978-3-319-40945-0/pbk; 978-3-319-40946-7/ebook). Lecture Notes in Computer Science 9705, 15-26 (2016).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

The complexity of languages resulting from the concatenation operation. (English) Zbl 1476.68132

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, 153-167 (2016).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI HAL

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

Star-complement-star on prefix-free languages. (English) Zbl 1356.68134

Shallit, Jeffrey (ed.) et al., Descriptional complexity of formal systems. 17th international workshop, DCFS 2015, Waterloo, ON, Canada, June 25–27, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-19224-6/pbk; 978-3-319-19225-3/ebook). Lecture Notes in Computer Science 9118, 231-242 (2015).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

The state complexity of permutations on finite languages over binary alphabets. (English) Zbl 1432.68241

Shallit, Jeffrey (ed.) et al., Descriptional complexity of formal systems. 17th international workshop, DCFS 2015, Waterloo, ON, Canada, June 25–27, 2015. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9118, 220-230 (2015).
MSC:  68Q45
PDFBibTeX XMLCite
Full Text: DOI

On the state and computational complexity of the reverse of acyclic minimal DFAs. (English) Zbl 1297.68144

Moreira, Nelma (ed.) et al., Implementation and application of automata. 17th international conference, CIAA 2012, Porto, Portugal, July 17–20, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-31605-0/pbk). Lecture Notes in Computer Science 7381, 229-239 (2012).
MSC:  68Q45 68Q25
PDFBibTeX XMLCite
Full Text: DOI

State complexity of Kleene-star operations on trees. (English) Zbl 1353.68171

Dinneen, Michael J. (ed.) et al., Computation, physics and beyond. International workshop on theoretical computer science, WTCS 2012, dedicated to Cristian S. Calude on the occasion of his 60th birthday, Auckland, New Zealand, February 21–24, 2012. Revised selected and invited papers. Berlin: Springer (ISBN 978-3-642-27653-8/pbk). Lecture Notes in Computer Science 7160, 388-402 (2012).
MSC:  68Q45
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