Document Search Results

Conditional automatic complexity and its metrics. (English) Zbl 07900282

Wu, Weili (ed.) et al., Computing and combinatorics. 29th international conference, COCOON 2023, Hawaii, HI, USA, December 15–17, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 14422, 15-28 (2024).

MSC: 68Rxx

Cite Review PDF

Full Text: DOI arXiv

Kjos-Hanssen, Bjørn; Felix, Clyde James; Kim, Sun Young; Lamb, Ethan; Takahashi, Davin

VC-dimensions of nondeterministic finite automata for words of equal length. (English) Zbl 1533.68137

Ann. Math. Artif. Intell. 90, No. 1, 93-105 (2022).

MSC: 68Q45

Cite Review PDF

Full Text: DOI arXiv

Kjos-Hanssen, Bjørn

An incompressibility theorem for automatic complexity. (English) Zbl 1537.68075

Forum Math. Sigma 9, Paper No. e62, 7 p. (2021).

Reviewer: Véronica Becher (Buenos Aires)

MSC: 68Q45 68Q30

Cite Review PDF

Full Text: DOI arXiv

Backlinks: MO

OA License

Kozachinskiy, Alexander; Shen, Alexander

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. (English) Zbl 1505.68018

J. Comput. Syst. Sci. 118, 75-107 (2021).

Reviewer: Ludwig Staiger (Halle)

MSC: 68Q30 68Q45

Cite Review PDF

Full Text: DOI arXiv

Kjos-Hanssen, Bjørn

Automatic complexity of Fibonacci and tribonacci words. (English) Zbl 1477.68134

Discrete Appl. Math. 289, 446-454 (2021).

Reviewer: Vladik Ya. Kreinovich (El Paso)

MSC: 68Q30 68Q45 68R15

Cite Review PDF

Full Text: DOI arXiv

Beros, Achilles A.; Kjos-Hanssen, Bjørn; Yogi, Daylan Kaui

Planar digraphs for automatic complexity. (English) Zbl 1527.68153

Gopal, T. V. (ed.) et al., Theory and applications of models of computation. 15th annual conference, TAMC 2019, Kitakyushu, Japan, April 13–16, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11436, 59-73 (2019).

MSC: 68R10 68Q45

Cite Review PDF

Full Text: DOI arXiv

Becher, Verónica; Carton, Olivier; Heiber, Pablo Ariel

Finite-state independence. (English) Zbl 1404.68066

Theory Comput. Syst. 62, No. 7, 1555-1572 (2018).

Reviewer: Cristian S. Calude (Auckland)

MSC: 68Q45 68Q30

Cite Review PDF

Full Text: DOI arXiv

Kjos-Hanssen, Bjørn

Automatic complexity of shift register sequences. (English) Zbl 1422.94024

Discrete Math. 341, No. 9, 2409-2417 (2018).

MSC: 94A55

Cite Review PDF

Full Text: DOI arXiv

Kjos-Hanssen, Bjørn

On the complexity of automatic complexity. (English) Zbl 1387.68158

Theory Comput. Syst. 61, No. 4, 1427-1439 (2017).

MSC: 68Q45 68Q17 68Q25

Cite Review PDF

Full Text: DOI arXiv

Allender, Eric

The complexity of complexity. (English) Zbl 1370.68114

Day, Adam (ed.) et al., Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday. Cham: Springer (ISBN 978-3-319-50061-4/pbk; 978-3-319-50062-1/ebook). Lecture Notes in Computer Science 10010, 79-94 (2017).

MSC: 68Q25 03D15 68Q15 68-02

Cite Review PDF

Full Text: DOI

Kjos-Hanssen, Bjørn

Kolmogorov structure functions for automatic complexity. (English) Zbl 1332.68097

Theor. Comput. Sci. 607, Part 3, 435-445 (2015).

MSC: 68Q30 62B10 68Q45

Cite Review PDF

Full Text: DOI

Hyde, Kayleigh K.; Kjos-Hanssen, Bjørn

Nondeterministic automatic complexity of overlap-free and almost square-free words. (English) Zbl 1334.68173

Electron. J. Comb. 22, No. 3, Research Paper P3.22, 18 p. (2015).

MSC: 68R15 68Q30 68Q45

Cite Review PDF

Full Text: arXiv Link

Eberhard, Sebastian; Hetzl, Stefan

Compressibility of finite languages by grammars. (English) Zbl 1390.68388

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, 93-104 (2015).

MSC: 68Q45 03F20 68Q42

Cite Review PDF

Full Text: DOI

Kjos-Hanssen, Bjørn

Kolmogorov structure functions for automatic complexity in computational statistics. (English) Zbl 1332.68096

Zhang, Zhao (ed.) et al., Combinatorial optimization and applications. 8th international conference, COCOA 2014, Wailea, Maui, HI, USA, December 19–21, 2014. Proceedings. Cham: Springer (ISBN 978-3-319-12690-6/pbk; 978-3-319-12691-3/ebook). Lecture Notes in Computer Science 8881, 652-665 (2014).

MSC: 68Q30 62B10

Cite Review PDF

Full Text: DOI arXiv

Hetzl, Stefan; Leitsch, Alexander; Reis, Giselle; Weller, Daniel

Algorithmic introduction of quantified cuts. (English) Zbl 1393.03050

Theor. Comput. Sci. 549, 1-16 (2014).

MSC: 03F05

Cite Review PDF

Full Text: DOI arXiv

Becher, Verónica; Heiber, Pablo Ariel

A linearly computable measure of string complexity. (English) Zbl 1255.68117

Theor. Comput. Sci. 438, 62-73 (2012).

Reviewer: Francine Blanchet-Sadri (Greensboro)

MSC: 68R15 68W32

Cite Review PDF

Full Text: DOI

Calude, Cristian S.; Salomaa, Kai; Roblot, Tania K.

Finite state complexity. (English) Zbl 1235.68088

Theor. Comput. Sci. 412, No. 41, 5668-5677 (2011).

MSC: 68Q30 68Q15

Cite Review PDF

Full Text: DOI

Domaratzki, Michael; Pighizzini, Giovanni; Shallit, Jeffrey

Simulating finite automata with context-free grammars. (English) Zbl 1042.68060

Inf. Process. Lett. 84, No. 6, 339-344 (2002).

MSC: 68Q45 68Q42

Cite Review PDF

Full Text: DOI

Found 18 Documents (Results 1–18)

Conditional automatic complexity and its metrics. (English) Zbl 07900282

VC-dimensions of nondeterministic finite automata for words of equal length. (English) Zbl 1533.68137

An incompressibility theorem for automatic complexity. (English) Zbl 1537.68075

Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. (English) Zbl 1505.68018

Automatic complexity of Fibonacci and tribonacci words. (English) Zbl 1477.68134

Planar digraphs for automatic complexity. (English) Zbl 1527.68153

Finite-state independence. (English) Zbl 1404.68066

Automatic complexity of shift register sequences. (English) Zbl 1422.94024

On the complexity of automatic complexity. (English) Zbl 1387.68158

The complexity of complexity. (English) Zbl 1370.68114

Kolmogorov structure functions for automatic complexity. (English) Zbl 1332.68097

Nondeterministic automatic complexity of overlap-free and almost square-free words. (English) Zbl 1334.68173

Compressibility of finite languages by grammars. (English) Zbl 1390.68388

Kolmogorov structure functions for automatic complexity in computational statistics. (English) Zbl 1332.68096

Algorithmic introduction of quantified cuts. (English) Zbl 1393.03050

A linearly computable measure of string complexity. (English) Zbl 1255.68117

Finite state complexity. (English) Zbl 1235.68088

Simulating finite automata with context-free grammars. (English) Zbl 1042.68060

Filter Results by …

Document Type

Author

Serial

Year of Publication

Main Field

Software